Алекс выбирает приборы для экспедиции. У него есть n разных приборов. Каждый существует в единственном экземпляре и имеет массу wᵢ и научную ценность vᵢ. Массы и ценности выбранных приборов складываются.
В рюкзак помещается груз общей массой не более W. Алекс хочет получить максимальную суммарную ценность. Среди всех наборов с такой ценностью он выбирает набор наименьшей общей массы. Можно не брать ни одного прибора.
Найдите максимальную ценность и соответствующую минимальную массу.
Входные данные
Первая строка содержит целые числа n и W (1 ≤ n ≤ 200, 1 ≤ W ≤ 10 000). Следующие n строк содержат wᵢ и vᵢ (1 ≤ wᵢ ≤ 20 000, 1 ≤ vᵢ ≤ 109).
Выходные данные
Выведите два целых числа: максимальную ценность и минимальную массу набора с этой ценностью.
Пояснения к примерам
Пример 1. Нужно взять третий и четвёртый приборы: ценность 6 + 12 = 18, масса 2 + 5 = 7.
Пример 2. Ценность обоих одиночных наборов равна 5, поэтому выбираем более лёгкий.
| № | Входные данные | Выходные данные |
|
1
|
4 7
4 8
3 6
2 6
5 12
|
18 7
|
|
2
|
2 3
2 5
3 5
|
5 2
|