Задача D1. Марфа Геннадьевна в столовой

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:1  

Условие

Однажды Марфа Геннадьевна пришла в столовую. В меню было N блюд. Блюдо с номером i стоит ci рублей. Для каждого блюда известен также коэффициент сытости блюда — ai.

Марфа Геннадьевна знает, что для того, чтобы наесться, нужно, чтобы сумма коэффициентов сытости съеденных блюд была не меньше A.

Какие блюда нужно взять в столовой, чтобы наесться и потратить как можно меньше денег? Обратите внимание, что Марфа Геннадьевна может взять более одной порции блюда (любое целое неотрицательное число порций).

Формат входного файла

Входной файл содержит целые числа N A.

Далее следуют N пар целых чисел ci ai.

Формат выходного файла

Выходной файл должен содержать минимальную сумму денег, которую нужно потратить, чтобы наесться.

Ограничения

1 ≤ N ≤ 100

1 ≤ A ≤ 1000

1 ≤ ci ≤ 500

1 ≤ ai ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 10
2 1
5 4
6 6
11
2
4 32
1 8
2 4
3 2
4 1
4

0.073s 0.008s 13