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

Изначально у Кости нет конфет, а у мамы их \(N\) (они пронумерованы от 1 до \(N\)). На каждой конфете мама написала два числа \(A_i\) и \(C_i\). Мама очень следит за уровеня вредности конфет, который получает ее сын. Изначально этот уровень равен 0. На каждом ходу игры Костя может взять одну конфету. Если Костя возьмет конфету с номером \(i\), то уровеня вредности увеличивается на \(A_i\). Если сразу после этого уровеня вредности становится большей \(C_i\), то брать эту конфету запрещается.

Брать конфеты можно в произвольном порядке, но одну и ту же можно брать не более одного раза.

Помогите Косте взять как можно больше конфет (вне зависимости от финального уровеня вредности).

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

Глубина ямы равна \(H\). Каждый школьник знает свой рост по плечи \(h_i\) и длину своих рук \(l_i\). Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте \(h_i + l_i\) от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником \(i\) стоят школьники \(j_1, j_2, \ldots, j_k\), то он может дотянуться до уровня \(h_{j1} + h_{j2} + \ldots + h_{jk} + h_i + l_i\).

Если школьник может дотянуться до края ямы (то есть \(h_{j1} + h_{j2} + \ldots + h_{jk} + h_i + l_i \geq H\)), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся.

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

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

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

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

Есть N шариков, висящих в воздухе вдоль одной линии слева направо. Девочка Перика хочет поиграть со стрелами и проверить свои навыки охотника. Она стреляет в линию шариков слева, запуская стрелу на некоторой высот. Стрела летит вдоль линии слева направо до тех пор, пока не попадет в шарик. В тот момент, когда она его касается, шарик лопается, а стрела летит дальше на высоте, уменьшенной на 1. То есть, если стрела летела на высоте H , то после столкновения она будет лететь на высоте H - 1 . Цель нашего героя - сбить все шарики, использовав минимальное количество стрел.

Совсем скоро начнётся чемпионат Хорватии по хорватскому хоккею. В хорватском хоккее каждая игра длится по M минут и в каждый момент времени на поле находятся ровно 6 игроков. Так как игра может длиться очень долго, не все игроки могут находится на поле на протяжении всей игры. Поэтому каждая команда привезла на чемпионат большое число запасных игроков.

Сегодня мы будем помогать Анте, тренеру команды Загреба. Анте привёз N игроков на чемпионат, причём у каждого игрока есть своя сила p _i и своя выносливость d _i . Для каждого игрока известно, что его «суммарное игровое время» не превышает величину его выносливости. «Суммарное игровое время» игрока — это суммарное количество времени, которое игрок провёл на поле. То есть, если игрок сначала провёл на поле X минут, а потом Y минут, то его «суммарное игровое время» равно X + Y минут.

В каждой момент времени у команды есть её сила — сумма сил всех шестерых игроков, находящихся на поле. Общая сила команды Z — это сумма сил команды во все минуты игры. То есть, если игра длилась 3 минуты и в первую минуту сила команды была 15 , во вторую — 12 , а в третью — 14 , то общая сила команды — 15 + 12 + 14 = 41 . Анте знает, что чтобы победить, надо максимизировать общую силу команды. Но Анте — не очень талантливый тренер, поэтому он просит вас помочь ему составить оптимальное расписание выхода команд, чтобы Z было максимально. Гарантируестя, что можно составить расписание так, чтобы в каждый момент на поле было по 6 игроков.

Обратите внимание, что в хорватском хоккее все игроки могут заменять друг друга, и вратаря нет, ведь так игра становиться гораздо веселее.