Маркетплейс с оптового склада каждый день отправляет заказанные товары в точки выдачи. Маркетплейс имеет множество видов различных товаров, каждый из которых имеет какой-то вес. Для отправки склад выделяет транспорт таким образом, чтобы отправить как можно больше товара каждого типа, но вес товаров одного типа не должен превышать S. Нужно определить, сколько всего товаров останется на складе и тип товара с самым большим остатком. Если таких товаров несколько, вывести товар с наименьшим кодом.
Входные данные представлены в файле
26-71.txt следующим образом. В первой строке входного файла записаны два числа, разделённые пробелом пробел: число N – количество доступных товаров (натуральное число, не превышающее 10000) и число S – вес, не более которого можно отправить каждый тип товара (натуральное число, не превышающее 10
8). В каждой из следующих N строк записаны по два числа, разделённые пробелом: код товара (натуральное число, не превышающее 10
9) и его вес (натуральное число, не превышающее 10
5). Известно, что количество различных кодов товаров в файле не превышает тысячи.
Запишите в ответе два числа: сначала количество товаров, оставшихся на складе, а затем код товара с самым большим остатком.
Пример входного файла::
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.