Страница: << 1 2 3 Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В сверхсекретную военную часть под командованием полковника Зуева скоро приедет комиссия из министерства обороны. Согласно уставу, в каждой сверхсекретной военной части должна быть сверхсекретная рота, которая должна заниматься... а чем именно — не скажем, на то она и сверхсекретная. Проблема заключается в том, что в части Зуева такой роты почему-то нет.

Полковник решил разобраться с этой проблемой незамедлительно и приказал построить на плацу в одну шеренгу всех n солдат вверенной ему части. Известно, что болтливость i -го слева солдата равна q i . Зуев хочет, чтобы сверхсекретная рота состояла из k первых солдат шеренги, а их суммарная болтливость была как можно меньше (чтобы рота оставалсь сверхсекретной). Для этого он собирается не более s раз поменять местами двух соседних солдат. Заметим, что любой солдат может участовать в таком обмене позициями сколько угодно раз. Задача оказалась нетривиальной, и полковник Зуев обратился к вам за помощью. Определите, какую минимальную суммарную болтливость первых k солдат шеренги можно достичь, если провести не более s операций обмена соседних солдат.

Входные данные

В первой строке входных данных записаны три целых положительных числа n , k , s ( 1 ≤ k n ≤ 150 , 1 ≤ s ≤ 10 9 ) — количество построенных в шеренгу солдат, предполагаемый размер сверхсекретной роты и максимальное возможное количество операций обмена соседних солдат соответственно.

Во второй строке входных данных записано n целых чисел q i ( 1 ≤ q i ≤ 10 6 ) — значения болтливости солдат в порядке следования солдат в шеренге.

Выходные данные

Выведите единственное целое число — минимальную возможную суммарную болтливость сверхсекретной роты.

Примечание

В первом примере полковнику достаточно поменять местами второго и третьего солдата и не использовать второй обмен. Итоговое положение солдат: ( 2 , 1 , 4 ). Минимальная возможная суммарная болтливость сверхсекретной роты равна 3 .

Во втором примере полковник будет производить обмены в следующей последовательности :

  1. (10, 1, 6 ftrightarrow 2 , 5)
  2. (10, 1, 2, 6 ftrightarrow 5 )

Итоговое положение солдат (10, 1, 2, 5, 6).

Минимальная суммарная болтливость роты равна 18 .

Примеры
Входные данные
3 2 2
2 4 1
Выходные данные
3
Входные данные
5 4 2
10 1 6 2 5
Выходные данные
18
Входные данные
5 2 3
3 1 4 2 5
Выходные данные
3
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
512 megabytes

У маленькой Даши сегодня день рождения — ей исполнилось целых 8 лет! По такому случаю каждый из n её родственников и друзей подарил ей ленточку с праздничным поздравлением, причём, как оказалось, все поздравления отличаются друг от друга. Даша собрала все ленточки вместе и решила выкинуть некоторые из них так, чтобы оставшийся набор стал стильным . Именинница считает набор стильным, если ни одно поздравление не является подстрокой другого. Напомним, что подстрокой строки s называется непрерывный отрезок букв строки s .

Помогите Даше оставить как можно больше ленточек, чтобы она могла хвастаться ими всем своим друзьям. Ленточки не разрешается поворачивать и переворачивать, то есть каждое поздравление может быть прочитано единственным способом.

Входные данные

Первая строка входных данных содержит целое число n ( 1 ≤ n ≤ 750 ) — количество родственников и друзей Даши.

Каждая из следующих n строк содержит ровно одно поздравление. Каждое поздравление состоит только из строчных английских букв ' a ' и ' b '.

Суммарная длина всех поздравлений не превышает 10 000 000 символов.

Выходные данные

В первой строке выведите максимальный размер стильного набора. Во второй строке выведите номера участвующих в нём лент, считая, что они нумеруются с единицы в порядке следования во входных данных. Если стильных наборов максимального размера несколько, то выведите любой из них.

Примечание

В примере можно было также оставить ленты 3 и 4.

Примеры
Входные данные
5
abab
aba
aabab
ababb
bab
Выходные данные
2
2 5

Страница: << 1 2 3 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест