Динамическое программирование

Популярная сеть быстрого питания «McDuck's» открыла новый филиал в Берляндии. В ресторане установлено k плит. Для того чтобы приготовить бургер, надо жарить котлету в течение минуты на одной из плит, поэтому ресторан может готовить не более k бургеров в минуту.

Известно, что в «McDuck's» придут n клиентов. i-й из них придёт в момент времени t_i, закажет x_i бургеров и будет готов заплатить за них c_i бурлей. Каждый клиент готов ждать заказ в течение w минут и, если через w минут после прихода он не получил x_i бургеров, он не заплатит ничего. При этом каждый клиент готов получать только свежие бургеры, то есть только те, котлеты для которых были поджарены не раньше времени t_i. Из-за таких сложных требований ресторан не всегда сможет выполнить все заказы всех клиентов.

Менеджеров ресторана заинтересовало, какую максимальную прибыль может получить «McDuck's». Помогите им ответить на этот непростой вопрос. Можно считать, что на готовку бургеров не расходуется никаких денег.

Входные данные
В первой строке содержатся три целых числа n, k и w (1 ≤ n ≤ 100000, 1 ≤ k ≤ 10, 1 ≤ w ≤ 60) — число клиентов, число плит и время ожидания клиента, соответственно.

Следующие n строк содержат описания клиентов, состоящие из трёх целых чисел — t_i, x_i, c_i (1 ≤ t_i, x_i, c_i ≤ 10⁹) — время (в минутах) прихода i-го клиента, число бургеров, которые он закажет и число бурлей, которые он готов заплатить, соответственно. Клиенты перечислены в порядке возрастания времени прихода, то есть для любого i > 1 верно, что t_i−1 ≤ t_i.

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

Примечание
В первом тестовом примере первую котлету можно поставить жариться в момент времени 0 и тогда в момент времени 1 она будет готова и её можно будет дать в бургере первому клиенту. В момент времени 1 можно поставить жариться ещё одну котлету, она будет готова в момент времени 2 и её можно будет дать в бургере второму клиенту.
 

Примеры

№	Входные данные	Выходные данные
1	2 1 1 1 1 5 1 1 7	12
2	3 2 2 1 6 8 2 5 10 3 4 4	12

Примечание:

 

Примеры

№	Входные данные	Выходные данные
1	??2?4+9?=355	00264+91=355

Скоро в Соединенных Штатах Берляндии пройдут выборы президента. На эту ответственную должность претендуют два кандидата: Дядя Сэм и Дядя Фродо. Вы работаете аналитиком в пред- выборном штабе Дяди Сэма, и вам поручено помочь ему победить конкурента. Раздуть газетный скандал из одержимости оппонента бросанием колец в жерла вулканов не получилось, так что при- дётся воспользоваться математикой.

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

Как вы знаете, Соединенные Штаты Берляндии разделены на несколько административных ре- гионов первого уровня — штатов. Сначала в каждом из штатов проходят местные выборы, по итогам которых каждый штат отдаёт свой голос за одного из кандидатов. Если не менее половины штатов выбрало Дядю Сэма, то выигрывает он (в случае равенства голосов Дядя Сэм имеет преимущество как действующий президент), иначе побеждает Дядя Фродо. Все штаты, в свою очередь, состоят из административных регионов второго уровня, каждый из которых представлен выборщиком из административных регионов третьего уровня и так далее. Последний уровень состоит из отдельных жителей Берляндии. Всего в Берляндии N жителей и K уровней административных единиц. Одним из ключевых принципов этой страны является равенство, так что любой регион i-го уровня делится на одинаковое число регионов следущего уровня (в том числе содержит одинаковое число граждан).

Так получилось, что делением на регионы поручили заняться именно вам, то есть в ваших руках назначить, на сколько именно административных единиц i-го уровня делится (i−1)-ая администра- тивная единица.

Также у вас есть сильный инструмент влияния на выбор людей — нефтяные бурли. Чтобы заста- вить одного избирателя отдать свой голос за Дядю Сэма, достаточно дать ему скромный подарок в размере одного нефтяного бурля.

К несчастью, изначально все N жителей Соединённых Штатов Берляндии собираются отдать свой голос за Дядю Фродо. Требуется определить минимальное количество нефтяных бурлей, ко- торое достаточно потратить для победы на выборах.

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

В единственной строке ввода находятся два целых числа N и K (1 <= N <= 10¹⁵ , 1 <= K <= 10).

Формат выходных данных
Требуется вывести единственное число — минимальное количество нефтяных бурлей, которое придётся потратить на предвыборные подарки при наилучшем разбиении на регионы.

Примеры

Ввод	Вывод
9 2	4
12 3	2

Замечание
Берляндские законы не запрещают, чтобы страна состояла из одного штата, а город — одного жителя. Аналогично с остальными типами регионов.

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

В процессе ремонта в Лаборатории Информационных Технологий строителям необходимо заменить поврежденные напольные плитки в коридоре лаборатории, который имеет размер 2 × n метров. В распоряжении строителей есть неограниченный запас плиток двух размеров: 1 × 2 метра и 1 × 1 метр. При этом плитки размером 1 × 2 метра перед укладкой разрешается поворачивать на 90 градусов и размещать как вдоль, так и поперек коридора.

Строители уже начали ремонт и уложили в некоторых местах пола коридора k плиток размером 1 × 1. Для завершения ремонта прорабу необходимо подготовить план дальнейших работ. Для этого ему надо решить, каким образом уложить плитки на места, где они еще не уложены. Это можно сделать различными способами и прораб хочет перебрать все варианты и выбрать самый удачный. Перед тем как это сделать, прораб хочет знать, какое количество вариантов ему придется рассмотреть. Это число требуется найти по модулю 10⁹ + 7.

Требуется написать программу, которая по заданной длине коридора n и расположению плиток, которые уже уложены, определяет количество способов укладки плиток на оставшиеся места. Ответ необходимо вывести по модулю 10⁹ + 7.

Формат входного файла
Первая строка входного файла содержит два целых числа: n — длину коридора и k — количество уже уложенных единичных плиток (1 ≤ n ≤ 100 000, 0 ≤ k < 2n). Последующие k строк содержат по два целых числа xi и yi , которые задают позиции уже уложенных единичных плиток, i-я плитка уложена на xi-м метре коридора в yi-м ряду (1 ≤ xi ≤ n, 1 ≤ yi ≤ 2).

Формат выходного файла
Выходной файл должен содержать одно целое число — количество способов укладки плиток в коридоре, взятое по модулю 10⁹ + 7.

Ввод	Вывод
2 0	7
3 0	22
3 1 2 1	8

Дана блок-схема алгоритма, реализованного в виде рекурсивно вызываемой функции:

Известно, что 𝐴, 𝐵 и 𝐶 - натуральные числа и что 𝐴 < 𝐵 < 𝐶.
Петя вызывает эту функцию, передавая ей в качестве входного параметра натуральное число. Известно, что для некоторого 𝑘 функция возвращает следующие значения:
𝐹(𝑘) = 50890368413;
𝐹(𝑘 + 1) = 93601980590;
𝐹(𝑘 + 2) = 172160883161.
Определите значения 𝐴, 𝐵 и 𝐶, при которых это возможно. Если таких вариантов несколько, выберите вариант с наименьшей суммой 𝐴, 𝐵 и 𝐶. В ответе введите в указанном порядке значения 𝐴, 𝐵 и 𝐶, разделённые пробелом.
 

Для поиска полезных ископаемых ученые разработали специальный сканер.

Представим область для поисков как таблицу из \(k\) строк и \(n\) столбцов. Нумерация строк идет от \(1\) до \(k\) сверху вниз, нумерация столбцов от \(1\) до \(n\) слева направо. В каждой клетке таблицы могут находиться полезные ископаемые.

Сканер работает следующим образом: он может быть запущен в столбце \(p\) и возвращает количество клеток в зоне сканирования, которые содержат полезные ископаемые. Зона сканирования включает все клетки столбца \(p\), верхние \(k-1\) клетку столбца \(p-1\), верхние \(k-2\) клетки столбца \(p-2\), и так далее. На рисунке показана зона сканирования для поля с \(k = 3\), \(n=5\) и всех значений \(p\).

Вам даны значения, которые вернул сканер для всех \(p\), обозначим за \(b_p\) значение в столбце \(p\). Будем называть таблицу, где для каждой клетки определено, находятся ли в ней полезные ископаемые, корректной, если для нее сканер возвращает верные значения. Например, если в примере выше сканер вернул значения \([2, 1, 2, 3, 2]\), то одна из корректных таблиц может выглядеть следующим образом (клетки, содержащие ископаемые, обозначены черным треугольником):

По заданным значениям, которые вернул сканер, определите количество корректных таблиц и выведите остаток от деления этого количества на число \(10^9+7\). Обратите внимание, что, возможно, сканер неисправен, и корректных таблиц вообще нет, тогда необходимо вывести \(0\).

Формат входных данных
В первой строке даны два числа \(n\), \(k\) — количество столбцов и строк, соответственно (\(1 \le n \le 200\), \(1 \le k \le 7\)).

Во второй строке даны \(n\) чисел \(b_1, b_2, \ldots, b_n\) — значения, которые вернул сканер (\(0 \le b_i \le k^2\)).

Формат выходных данных
Выведите единственное число — остаток от деления количества различных корректных таблиц на \(10^9 + 7\).

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

Как оказалось, голубые ели бывают M различных сортов. Для ели каждого сорта известна максимальная длина ее тени в течение дня в западном и в восточном направлении (W_i и E_i соответственно). При этом известно, что ели растут гораздо лучше, если в течение дня они не оказываются в тени других елей.

Координатная ось направлена вдоль аллеи с запада на восток.

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

Входные данные
Во входном файле записано сначала натуральное число M — количество сортов елей (1<M<100). Затем идет M пар чисел W_i, E_i, описывающих максимальную длину тени в западном и восточном направлении в течение дня для каждого сорта ели (числа W_i, E_i — целые, из диапазона от 0 до 30000). Далее идет натуральное число N — количество клумб, в которых можно сажать ели (1<N<100). Далее идет N чисел, задающих координаты клумб (координаты — целые числа, по модулю не превышающие 30000). Клумбы перечислены с запада на восток (в порядке возрастания их координат).

Примечание

Если на клумбе с координатой X мы посадили ель, максимальная тень которой в восточном направлении равна E, то все клумбы с координатами от X+1 до X+E–1 попадают в тень от этой ели, а клумба с координатами X+E — уже нет. Аналогично для тени в западном направлении.

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

Сообщения SMS сотового телефона MOBILA составлены из прописных латинских букв. Если буква первая на кнопке, нужно нажать эту кнопку один раз, чтобы добавить букву в сообщение. Если буква вторая - нужно нажать кнопку дважды и т.д. Так, чтобы набрать слово "SMS", нужно нажать

(PQRS)(PQRS)(PQRS)(PQRS)(MNO)(PQRS)(PQRS)(PQRS)(PQRS)

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

(ABC)(пауза)(ABC)

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

(ABC)(ABC)(ABC)(ABC)(пауза)(ABC)

соответствует сообщению "CAA". К сожалению, сотовые телефоны этой модели давно не производятся, и остался только один такой телефон. Он может произвольно вставлять и игнорировать паузы во время ввода сообщения, что может привести к некоторым изменениям в сообщениях. Например, введя MOSCOWQUARTERFINAL, можно получить вместо этого OMSCMNWQTTARTERPDEINAL. Вы получили SMS-сообщение и знаете, что оригинальное сообщение содержало N букв. Чтобы определить вероятность угадывания оригинального сообщения, найдите число возможных сообщений, которые могли превратиться в то, которое Вы получили.



Входные данные
В первой строке задана длина оригинального сообщения N. Вторая строка содержит полученное SMS-сообщение. 1 <= N <= 80, полученное сообщение состоит только из прописных латинских букв, длина полученного сообщения - от 1 до 80 букв.

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

На окружности отметили N точек и пронумеровали их последовательно числами от 1 до N. Требуется найти количество различных простых ломаных с вершинами в некоторых из отмеченных точек и с концами в точках с номерами i и j.

Ломаная называется простой, если она не проходит дважды через одну точку (и не содержит самокасаний и самопересечений).

Входные данные
Вводятся три натуральных числа N, i, j (2 ≤ N ≤ 2 000, 1 ≤ i < j ≤ N).

Выходные данные
Требуется вывести остаток от деления количества ломаных на 10⁹.

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

Входные данные
В первой строке входных данных содержатся два натуральных числа: N (1 <= N <= 10000) - значение выражения и K (1 <= K <= 10000) - наибольшее число, которое разрешается использовать в выражении.

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

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

Сережа - большой любитель игр на сотовом телефоне. Недавно он скачал из интернета новую игру "Пузырьки 1D". Опишем правила игры.

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

За один ход разрешается выбрать любую группу, состоящую хотя бы из двух пузырьков, и взорвать ее. За взрыв группы, содержащей K пузырьков, игрок получает K² очков. После взрыва группы пузырьки, которые находились сверху, опускаются вниз.

Например, ниже на рисунке показана позиция, содержащая 10 пузырьков. В ней четыре группы, содержащие 3, 2, 4 и 1 пузырек, соответственно. Если взорвать группу, содержащую четыре пузырька, то игрок получит 16 очков, и верхние 5 пузырьков опустятся вниз. В получившейся позиции 6 пузырьков, и две группы по 3 пузырька в каждой.


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

Входные данные
На вход программы поступает одна строка, состоящая из букв "R", "G", "B и "Y", описывающая начальную позицию. Буквы задают цвета пузырьков в порядке просмотра сверху вниз ("R" означает красный пузырек, "G" – зеленый, "B" – синий, а "Y" – желтый). В заданной позиции не менее двух и не более 100 пузырьков.

Выходные данные
Выведите одно число – максимальное количество очков, которое сможет заработать Сережа. Если уничтожить все пузырьки невозможно, выведите 0.

Пояснения
В первом примере следует действовать следующим образом: сначала надо взорвать группу из четырех красных пузырьков, получив 16 очков. Затем надо взорвать в любом порядке получившиеся две группы по 3 пузырька, получив по 9 очков за каждую.

Поле для детской игры представляет собой последовательность кружков, первый из которых является стартом, а последний – финишем. На некоторых из кружков указано действие, которое нужно совершить фишке, попавшей на этот кружок: передвинуть фишку на несколько кружков вперед или назад, или сделать еще один ход. Изначально фишки всех K игроков ставятся на старт. Затем они по очереди делают ходы, которые заключаются в следующем. Игрок получает очередное "случайное" число, используя генератор псевдослучайных чисел, описанный ниже, и передвигает свою фишку на столько кружков вперед, какое число он получил (если это число больше количества кружков до финиша, то игрок останавливается на финише). Если на кружке, куда он попал в результате своего хода, написано, что требуется совершить некоторое действие, то игрок совершает это действие. После этого он совершает действие, указанное на кружке, куда он попал в результате предыдущего действия и т. д. до тех пор, пока он не попадет на кружок, на котором не указано никакого действия.

Игра заканчивается, как только фишка одного из игроков достигнет финиша. Этот игрок и считается победителем. Требуется написать программу, которая по описанию поля и по данным параметрам генератора псевдослучайных чисел определит, кто выиграет в данной игре.

Генератор псевдослучайных чисел устроен следующим образом. Его параметрами являются натуральные числа a, b, c и x0. Генератор порождает последовательность натуральных чисел x₁, x₂, x₃, … по следующему правилу: xn+1 равно остатку от деления (ax_n+ b) на c (при n = 0, 1, 2, …). Для игры используются числа x₁, x₂, x₃, … именно в этом порядке (число x0 не используется). Все игроки используют общий датчик, то есть, если, например, первый игрок использовал число x1 и передал ход второму, то тот будет использовать число x₂, а если ему потребуется повторить ход, то x₃ и т. д.

Входные данные
В первой строке входных данных содержатся числа a, b, c, x0, описывающие генератор псевдослучайных чисел. Все числа целые неотрицательные и не превосходят 1000; c > 0. В следующей строке записаны числа K – количество игроков и L – количество кружков поля, включая старт и финиш (1 ≤ K, L ≤ 1000). В следующих L–2 строках записаны команды во втором, третьем, …, L–1-м кружке (в кружках старта и финиша никаких команд нет и при попадании туда ничего делать не нужно). Каждая команда записывается парой чисел.

Если первое число равно единице, то это означает, что нужно сделать дополнительный ход. При этом, если второе число равно T и T > 0, то нужно сделать ход на T кружков вперед, если T < 0 – то на |T| кружков назад, а если T = 0, то нужно снова воспользоваться датчиком псевдослучайных чисел и сделать указанное им количество шагов вперед.

Если первое число равно нулю, то ничего делать не нужно. (Если первое число равно нулю, то второе число также равно нулю.)

Другие значения первое число принимать не может.

Число T целое, и всегда таково, что при соответствующем ходе фишка не окажется за пределами доски (но может оказаться на клетке Старт или Финиш). Если же T = 0 и очередное "случайное" число больше, чем количество кружков до финиша, то фишка останавливается на финише.

Выходные данные
Выведите одно число – номер игрока-победителя. Гарантируется, что одна из фишек обязательно достигнет финиша, причем за время игры будет совершено не более миллиона перемещений (на "случайное" число или число, указанное в кружке).

Сегодня на страницах газеты <<Математический досуг>> была опубликована необычная математическая головоломка. Одна из страниц газеты полностью занята прямоугольной таблицей, состоящей из \(m\) строк и \(n\) столбцов. В каждой ячейке таблицы записано некоторое целое число.

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

Безуспешно потратив несколько часов на решение головоломки, Саша решил написать программу, которая сделала бы это за него. Но и тут его постигла неудача. Теперь ему ничего не остается, как обратиться за помощью к вам.

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

Формат входных данных
На первой строке записаны два целых числа \(m\) и \(n\) (\(2 \le m, n \le 300\)). Далее следует описание таблицы — \(m\) строк, каждая из которых содержит по \(n\) целых чисел \(a_{i,j}\) (\(-10^4 \le a_{i,j} \le 10^4\)).

Формат выходных данных
На первой строке выведите целое число \(s\) — максимальную сумму чисел на границе искомого прямоугольника. На второй строке выведите четыре натуральных числа: \(x_1, y_1, x_2, y_2\) — координаты левой верхней и правой нижней ячейки выбранного прямоугольника, соответственно (здесь \(x\) — номер строки, а \(y\) — номер столбца, строки нумеруются сверху вниз, начиная с единицы, столбцы нумеруются слева направо, начиная с единицы). Если оптимальных решений несколько, выведите любое.

Знаменитый писатель Велепин очень продуктивен. Совсем недавно он подписал контракт с известным изданием, и теперь за \(i\)-й год ему нужно написать \(k_i\) романов. Для него это вообще не проблема: он может сколько угодно писать о самураях, космосе, пустоте, насекомых и оборотнях.

У него есть \(n\) постоянных читателей, каждый из которых в \(i\)-й год прочитает один из \(k_i\) романов, выпущенных Велепиным. Читатели очень любят обсуждать новинки, поэтому \(j\)-й из них будет доволен в течение года, если такой же роман, как и он, прочитают как минимум \(a_j\) человек, включая его самого.

Издание, с которым подписал контракт Велепин, очень современно: у него есть возможность контролировать, какое произведение прочитает каждый из поклонников. Оно не хочет издавать романы просто так, поэтому хотя бы один экземпляр каждого романа должен попасть в руки читателя. Издание надеется выиграть награду <<Издание \(q\)-летия>>, поэтому отдел маркетинга хочет узнать, какое максимальное количество постоянных читателей можно сделать довольными в течение каждого года, оптимально распределяя романы между ними. Так как в отделе маркетинга нет никого, кто мог бы это сделать, он обратился к вам за помощью.

Формат входных данных
В первой строке дано одно целое число \(n\) \((2 \leqslant n \leqslant 300\,000)\) — количество постоянных читателей Велепина.

Во второй строке дано \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) \((1 \leqslant a_j \leqslant n)\) — количество людей, которые должны читать тот же роман, что и \(j\)-й, чтобы он был доволен.

В третьей строке дано одно целое число \(q\) (\(1 \leqslant q \leqslant 300\,000\)) — количество лет, которые нужно проанализировать.

В каждой из следующих \(q\) строк дано по одному целому числу \(k_i\) \((2 \leqslant k_i \leqslant n)\) — количество романов, которые Велепин должен написать в \(i\)-й год.

Формат выходных данных
Выведите \(q\) строк, в каждой из них ровно одно число — максимальное количество человек, которые могут быть довольны в \(i\)-й год, если Велепин выпустит \(k_i\) романов.

В первом примере в первый год оптимальным является разделение \(1, 1, 1, 2, 2\) (первый роман читают первые три человека, а два последних — второй). Во второй год оптимальным решением является \(1, 1, 2, 2, 3\) (первый роман читает первый и второй человек, второй роман читает третий и четвертый человек, третий роман читает пятый человек). В третий год оптимальным будет разбиение \(1, 2, 2, 4, 3\). Соответственно количество довольных людей по годам будет \(5, 5, 3\).

Всего во Флатландии \(n\) городов, пронумерованных от \(1\) до \(n\), столица Флатландии имеет номер \(1\). Компьютерная сеть Флатландии устроена следующим образом: в каждом городе есть один центр подключения, который может быть связан с некоторыми другими центрами с помощью проводных каналов связи. При этом между любыми двумя городами есть ровно один маршрут по каналам связи, иначе говоря, сеть представляет собой дерево. Для города \(i\), где \(i > 1\), обозначим первый город на маршруте от города \(i\) до столицы как \(p_i\).

Запланирована модернизация сети Флатландии, в результате которой некоторые каналы связи будут заменены на более современные оптические. Оптические каналы могут быть проложены только вместо существующих проводных. Стоимость замены канала, который соединяет город \(i\) с городом \(p_i\), равна \(w_i\). Из-за ограничений технологии любой центр подключения может быть подключен оптическими каналами не более чем к \(k\) другим центрам.

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

Помогите специалистам министерства выбрать каналы для модернизации.

Формат входных данных
На первой строке ввода находятся два целых числа \(n\) и \(k\) (\(2 \le n \le 10^5\), \(1 \le k \le 100\)).

На следующих \(n - 1\) строках заданы описания каналов, \((i-1)\)-я из этих строк содержит два целых числа: \(p_i\) и \(w_i\) (\(1 \le p_i \le i\), \(0 \le w_i \le 10^9\)).

Формат выходных данных
Выведите два целых числа \(cnt\) и \(cost\): максимальное число каналов, которое удастся модернизировать и минимальную стоимость, за которую можно модернизировать такое число каналов.

Замечание
Конфигурация сети в первом примере до и после модернизации показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно \(4\). Стоимость модернизации любого канала равна \(0\) и не показана.

Есть и другие подходящие решения, в которых модернизируется \(4\) канала.

Конфигурация сети во втором примере до и после модернизациии показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно \(6\). Стоимость модернизации канала показана рядом с каналом, суммарная стоимость модернизации каналов в оптимальном решении равна \(27\).

Даны два целых числа \(x\) и \(y\). Назовем последовательность \(a\) длины \(n\) модообразной, если \(a_1=x\), и для всех \(1 < i \le n\) значение \(a_{i}\) равно либо \(a_{i-1} + y\), либо \(a_{i-1} \bmod y\). Здесь \(x \bmod y\) обозначает остаток от деления \(x\) на \(y\).

Определите, существует ли модообразная последовательность длины \(n\), сумма элементов которой равна \(S\), и если существует, то найдите любую такую последовательность.

Формат входных данных
Первая и единственная строка содержит четыре целых числа \(n\), \(x\), \(y\) и \(S\) (\(1 \le n \le 200\,000\), \(0 \le x \le 200\,000\), \(1 \le y \le 200\,000\), \(0 \le S \le 200\,000\)) — длина последовательности, параметры \(x\) и \(y\), и необходимая сумма элементов последовательности.

Формат выходных данных
Если искомая последовательность существует, выведите в первой строке <<Yes>> (без кавычек). Далее, во второй строке выведите \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) через пробел — элементы последовательности \(a\). Если подходящих последовательностей несколько, выведите любую из них.

Если же последовательность не существует, выведите в единственной строке <<No>>.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки <<yEs>>, <<yes>>, <<Yes>> и <<YES>> будут приняты как положительный ответ.

Замечание
В первом примере условиям удовлетворяет последовательность \([8, 11, 2, 5, 2]\). Таким образом, \(a_1 = 8 = x\), \(a_2 = 11 = a_1 + 3\), \(a_3 = 2 = a_2 \bmod 3\), \(a_4 = 5 = a_3 + 3\), \(a_5 = 2 = a_4 \bmod 3\).

Во втором примере первый элемент последовательности должен равняться \(5\), поэтому последовательность \([2, 2, 2]\) не подходит.

Теплым весенним днем группа из 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, то во второй строке в произвольном порядке выведите их номера, разделяя их пробелами. Школьники нумеруются с единицы в том порядке, в котором они заданы во входных данных. Если существует несколько решений, выведите любое.