Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1758. Решение задач
Быстрая сортировкаОлимпиадные задачи на русском языке
| 25/06/2012 | Лето 2012 - дорешивание ( 5C) |
| 29/06/2012 | Лето 2012 - 5 (C) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В этой задаче Вася готовится к олимпиаде. Учитель дал ему `N` задач для тренировки.
Для каждой из этих задач известно, каким умением `a_i` нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения `i`-й задачи Васино умение увеличивается на число `b_i`.
Исходное умение Васи равно `A`. Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения?
Сначала вводятся два целых числа `N`, `A` (`1\ ≤\ N\ ≤\ 100\ 000`, `0\ ≤\ A\ ≤\ 10^9`) – количество задач и исходное умение.
Далее идут `N` пар целых чисел `a_i`, `b_i` (`1\ ≤\ a_i\ ≤\ 10^9`, `1\ ≤\ b_i\ ≤\ 10^9`) – соответственно сколько умения нужно для решения `i`-й задачи и сколько умения прибавится после её решения.
Выведите одно число – максимальное количество задач, которое Вася сможет решить.
Пример ввода 1
3 2 3 1 2 1 1 1
Пример вывода 1
3
Пример ввода 2
4 1 1 10 21 5 1 10 100 100
Пример вывода 2
3
В первом тесте Вася сможет решить все задачи, выбрав, например, порядок 2, 1, 3.
Во втором тесте ему необходимо сначала разобраться с 1 и 3 задачами, после чего он осилит 2.
Источник: Московская олимпиада школьников по информатике, 2010/11 учебный год
