Главный герой игры Cut the Rope — монстрик Ом Ном, который очень любит конфеты. По случайному совпадению, он же главный герой этой задачи.
Как-то раз Ом Ном зашел в гости к своему другу Эвану. В доме Эвана есть n конфет двух типов (леденцы и карамельки), i-я конфета висит на высоте hi сантиметров от пола дома и имеет массу mi. Ом Ном хочет съесть как можно больше конфет. В начале Ом Ном может прыгать не более, чем на x сантиметров в высоту. Когда Ом Ном съедает конфету массы y, он становится сильнее, и высота его прыжка увеличивается на y сантиметров.
Какое максимальное количество конфет сможет съесть Ом Ном, если он никогда не будет есть подряд две конфеты одного и того же типа (Ом Ном считает, что это слишком скучно)?
Выходные данные
Выведите единственное целое число — максимальное количество конфет, которое сможет съесть Ом Ном.
Примечание
Один из возможных способов съесть 4 конфеты — есть конфеты в порядке: 1, 5, 3, 2. Рассмотрим подробнее такое развитие событий:
- Изначально высота прыжка Ом Нома равна 3. Он может допрыгнуть до конфет 1 и 2. Допустим, что он съест конфету 1. Так как масса этой конфеты равна 4, высота его прыжка станет равна 3 + 4 = 7.
- Теперь Ом Ном может допрыгнуть до конфет 2 и 5. Допустим, что он съест конфету 5. Тогда высота его прыжка станет равна 7 + 5 = 12.
- В данный момент Ом Ном может допрыгнуть до двух конфет: 2 и 3. Есть конфету 2 он не будет, так как ее тип совпадает с предыдущей съеденной конфетой. Ом Ном съедает конфету 3, высота его прыжка становится равна 12 + 3 = 15.
- Ом Ном съедает конфету 2, высота его прыжка становится равна 15 + 1 = 16. До конфеты 4 он допрыгнуть не может.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
0 2 4
1 3 1
0 8 3
0 20 10
1 5 5
|
4
|