Жадный алгоритм

Теплым весенним днем группа из N школьников-программистов гуляла в окрестностях города Кисловодска. К несчастью, они набрели на большую и довольно глубокую яму. Как это случилось — непонятно, но вся компания оказалась в этой яме.

Глубина ямы равна H. Каждый школьник знает свой рост по плечи h_i и длину своих рук l_i. Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте h_i + l_i от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником i стоят школьники j₁, j₂, …, j_k, то он может дотянуться до уровня h_j1 + h_j2 + … + h_jk + h_i + l_i.

Если школьник может дотянуться до края ямы (то есть h_j1 + h_j2 + … + h_jk + h_i + l_i ≥ H), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся.

Найдите наибольшее количество школьников, которые смогут выбраться из ямы до прибытия помощи, и перечислите их номера.

Формат входных данных
В первой строке входных данных задается натуральное число N (1 ≤ N ≤ 2000) — количество школьников, попавших в яму.

Далее в N строках содержится по два целых числа: рост i-го школьника по плечи h_i (1 ≤ h_i ≤ 10⁵) и длина его рук l_i (1 ≤ l_i ≤ 10⁵).

В последней строке указано целое число — глубина ямы H (1 ≤ H ≤ 10⁵).

Формат выходных данных
В первой строке выведите K — максимальное количество школьников, которые смогут выбраться из ямы. Если K > 0, то во второй строке в произвольном порядке выведите их номера, разделяя их пробелами. Школьники нумеруются с единицы в том порядке, в котором они заданы во входных данных. Если существует несколько решений, выведите любое.

Юный художник Вася нарисовал плакат с очень большим числом и решил повесить его на самую длинную стену школы. К сожалению, даже самая длинная стена оказалась недостаточно длинной, поэтому ему придется укорачивать плакат до нужной длины. Вася — максималист, поэтому он хочет, чтобы число, получившееся после всех правок, было как можно больше. Васе нужно вырезать из плаката любые K цифр, но он ни за что не согласится переставлять получившиеся кусочки местами, так как это нарушит цветовой баланс плаката. Помогите Васе переделать плакат.

Входные данные
В первой строке входных данных записано целое число N, записанное на изначальном длинном плакате. Гарантируется, что в N не менее двух и не более 200 000 цифр (10 ≤ N < 10^{200 000}).
Во второй строке содержится целое число K — количество цифр, которые необходимо вырезать из плаката. Гарантируется, что K не меньше одного и строго меньше количества цифр числа N (1 ≤ K, 10^K ≤ N).
Выходные данные
Выведите максимальное число, которое может получиться на плакате после его укорачивания

Примеры

№	Входные данные	Выходные данные
1	2023 1	223

Замечание
В примере из условия на плакате записано число 2023, из него нужно вырезать одну цифру.
Максимально число, которое можно при этом получить, равно 223.

Код Эвана содержит n переменных. Каждая переменная имеет уникальное имя, состоящее только из английских строчных (маленьких) букв. Однажды Эван решил укоротить свой код.

Он хочет заменить имя каждой переменной его непустым префиксом таким образом, что новые имена останутся попарно различными (но новое имя какой-либо переменной может совпадать со старым именем этой или другой переменной). Среди всех таких возможных замен он хочет найти такую, для которой суммарная длина названий переменных будет минимальной.

Строка a является префиксом строки b, если вы можете удалить несколько (возможно, ни одного) символа с конца строки b и получить a.

Найдите минимальную возможную суммарную длину новых имён.

Входные данные:
В первой строке содержится одно целое число n (1 ≤ n ≤ 10⁵) — число переменных в коде Эвана.

Следующие n строк содержат названия переменных по одному на строку. Каждое название не является пустой строкой и содержит только лишь строчные (маленькие) английские буквы. Суммарная длина всех этих строк не больше 10⁵. Все названия переменных различны.

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

Примеры:
 

Входные данные	Выходные данные
3 codeforces codehorses code	6
5 abba abb ab aa aacada	11
3 telegram digital resistance	3

Пояснения:
В первом примере одним из наилучших вариантов будет сокращение имён в порядке их ввода до "cod", "co", "c".
Во втором примере можно укоротить последнее имя до "aac" и первое имя до "a" без изменения других имён переменных.

В целях улучшения ландшафтной архитектуры и экологической обстановки управление городского хозяйства разработало проект программы озеленения центрального проспекта. Согласно проекту, с одной стороны проспекта планируется высадить в ряд деревья K различных видов, для чего были закуплены саженцы деревьев, причем i-го вида было закуплено a_i саженцев.

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

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

Входные данные
В первой строке вводятся два целых числа: K — количество различных видов деревьев (1 ≤ K ≤ 100 000), и P — требуемое количество подряд идущих деревьев разных видов (2 ≤ P ≤ K). Последующие K строк  входных данных содержат целые числа ai, задающие количество закупленных саженцев деревьев i-го вида  (1 ≤ a_i ≤ 10⁹), по одному числу в каждой строке.

Выходные данные
Выведите единственное число — максимальное количество деревьев, посадка которых в ряд в некотором порядке достигает эстетического совершенства.

 

Примеры

№	Входные данные	Выходные данные
1	3 3 1 200  1	4

 

Ввод	Вывод
15 15 5 2 2 5 10 6 4 11 3	44

Формат ввода

Формат вывода

Пример

Ввод	Вывод
3 1 2 1 3 3 1	2 3 1 2