Вне конкурса

Соревнование завершилось 15.04.18 в 16:00

A. Тындекс музыка

Ограничение по времени: 1 с.
Ограничение по памяти: 256 МБ

Юля любит слушать музыку через интернет сервис «Тындекс Музыка». Это очень удобно — огромное количество музыкальных композиций в прямой доступности. Но вот проблема, у Юли осталось совсем немного трафика мобильного интернета, а она обязательно хочет скачать ещё одну песню на внутреннюю память телефона.

Всего в плейлисте Юли — n песен. Какие-то уже скачаны, а какие-то — ещё нет. Каждая песня характеризуется так называемой «прЕкольностью». Так вот Юля хочет скачать одну, еще не скачанную, песню из своего плейлиста так, чтобы сумма «прЕкольностей» всех скачанных песен была максимально близка к заданному её настроением целому числу k.

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

Первая строка входных данных содержит два целых числа разделенных пробелом: n и k — количество песен в плейлисте и число заданное настроением Юли соответственно (1 \leqslant n \leqslant 1000, -10^{9} \leqslant k \leqslant 10^{9}).

Последующие n строк содержат по два целых числа, разделённых пробелом: p_{i} — «прЕкольность» i-й песни и d_{i} — статус закачки i-й песни: 0 — не скачана, 1 — скачана (-1000 \leqslant p_{i} \leqslant 1000, 1 \leqslant i \leqslant n).

Гарантируется, что хотя бы одна песня в плейлисте не скачана.

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

В единственной строке выходных данных требуется вывести два целых числа через пробел: максимально близкую к числу k сумму «прЕкольностей» скачанных песен, если скачать еще одну песню и «прЕкольность» этой скачанной песни.

Если существует несколько правильных ответов, то среди них требуется выбрать ответ с максимальной суммой «прЕкольностей».

Примеры
Стандартный вводСтандартный вывод
4 1
1 0
2 0
3 0
4 1
5 1