Задание 26 ЕГЭ по информатике

Петя играет в компьютерную игру "Кучи камней". Всего в игре есть $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.

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/11956_26.txt