№542548715

(PRO100 ЕГЭ) Петя играет в компьютерную игру "Кучи камней". Всего в игре есть N уровней. Для каждого уровня известно, какой нужен skill для его прохождения. Кроме того, после прохождения каждого уровня skill Пети увеличивается. Для каждого уровня указано, на сколько увеличится skill, после его прохождения. Уровни можно проходить в любом порядке.

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

Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 10000) - количество уровней в игре и натуральное число K (K ≤ 1000) - начальный skill Пети. Следующие N строк содержат пары чисел, первое число обозначает skill необходимый для прохождения уровня, а второе число - на сколько увеличится skill Пети, после прохождения этого уровня. Каждое из чисел натуральное, не превосходящее 100000.

Запишите в ответе два числа: максимальное количество уровней, которые Петя сможет пройти, и его финальный skill.

Типовой пример организации данных во входном файле
5 6
10 15
8 1
1 2
27 10
9 2
При таких исходных данных Петя сможет пройти четыре уровня:, (10, 15), (8, 1), (1, 2) и (9, 2). Его финальный skill будет равен 26.