Задача . C. Параллельный поиск

Допустим, у вас есть \(n\) коробок. В \(i\)-й коробке бесконечно много шариков цвета \(i\). Иногда вам нужно получить шарик какого-то определенного цвета; но вы слишком ленивы, чтобы брать шарик из коробки самостоятельно.

Вы купили двух роботов, которые будут приносить вам шарики. Теперь этих роботов надо запрограммировать. Для этого вы должны сформировать два списка \([a_1, a_2, \dots, a_k]\) и \([b_1, b_2, \dots, b_{n-k}]\), где список \(a\) — это список коробок, назначенных первому роботу, а список \(b\) — коробки, назначенные второму роботу. Каждое целое число от \(1\) до \(n\) должно принадлежать ровно одному из этих списков.

Когда вы даете роботам команду «принести шарик цвета \(x\)», они выполняют ее следующим образом. Каждый робот проходится по тому списку коробок, который был назначен этому роботу (в том порядке, в котором коробки находятся в списке), и просматривает содержимое каждой коробки. Первый робот тратит \(s_1\) секунд, чтобы просмотреть содержимое коробки; второй робот тратит \(s_2\) секунд. Как только какой-то робот найдет коробку с шарами цвета \(x\) и просмотрит ее содержимое, поиск завершается. Время поиска — это количество секунд, прошедшее от начала поиска до того, как один из роботов просмотрит содержимое коробки \(x\). Если робот просмотрел все коробки, назначенные ему, после этого он ничего не делает.

Например, пусть \(s_1 = 2\), \(s_2 = 3\), \(a = [4, 1, 5, 3, 7]\), \(b = [2, 6]\). Если вы запросите шарик цвета \(3\), произойдет следующее:

• сначала первый робот начнет просматривать коробку \(4\), а второй — коробку \(2\);
• в конце \(2\)-й секунды первый робот закончит просматривать коробку \(4\). Это не та коробка, которая нужна, поэтому робот начинает просматривать коробку \(1\);
• в конце \(3\)-й секунды второй робот закончит просматривать коробку \(2\). Это не та коробка, которая нужна, поэтому робот начинает просматривать коробку \(6\);
• в конце \(4\)-й секунды первый робот закончит просматривать коробку \(1\). Это не та коробка, которая нужна, поэтому робот начинает просматривать коробку \(5\);
• в конце \(6\)-й секунды первый робот закончит просматривать коробку \(5\). Это не та коробка, которая нужна, поэтому робот начинает просматривать коробку \(3\). В тот же самый момент второй робот закончит просматривать коробку \(6\). Это не та коробка, которая нужна, и второй робот закончил просматривать все назначенные ему коробки, поэтому больше он ничего не делает;
• в конце \(8\)-й секунды первый робот закончит просматривать коробку \(3\). Это та коробка, которая вам нужна, поэтому поиск завершается;
• итак, время поиска равно \(8\) секундам.

Вы планируете запросить шарик цвета \(1\) \(r_1\) раз, шарик цвета \(2\) — \(r_2\) раз, и так далее. Составьте списки \(a\) и \(b\) таким образом, чтобы суммарное время поиска было как можно меньше.