print1758. Решение задач

printРешение задач

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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 учебный год
loading