Задача #6688

(Д. Ушаков) Маркетплейс с оптового склада каждый день отправляет заказанные товары в точки выдачи. Маркетплейс имеет множество видов различных товаров, каждый из которых имеет какой-то вес. Для отправки склад выделяет транспорт таким образом, чтобы отправить все возможные типы товаров и при этом отправить как можно больше каждого из них, но не более, чем определённый вес S. Нужно определить, сколько всего товаров останется на складе и тип товара с самым большим остатком. Если таких товаров несколько, вывести товар с наименьшим кодом.

Входные данные:

В первой строке входного файла находится два числа через пробел: число N - количество доступных товаров (натуральное число, не превышающее 10000) и число S - вес, не более которого можно отправить каждый тип товара (натуральное число, не превышающее 10⁸). В следующих N строках находятся по два числа через пробел: тип товара (натуральное число, не превышающее 10⁹) и его вес (натуральное число, не превышающее 10⁵).

Известно, что видов товаров не бывает более тысячи.

Запишите в ответе два числа: сколько всего товаров останется на складе и тип товара с самым большим остатком.

Пример входного файла:

8 13

150 8

237 3

237 6

150 4

237 5

237 6

150 3

150 3

При таких исходных данных имеется всего два вида товаров ("150" и "237")

Товаров вида "150" можно погрузить три штуки (3, 3 и 4), останется 1 штука (8)

Товаров вида "237" можно погрузить две штуки (за 3 и 5), останется 2 штуки (6 и 6)

Поэтому ответ для приведённого примера: 3 237