e-olymp
Problems

Мастер "Вормикса"

Мастер "Вормикса"

Вася в восхищении от ит игры "Вормикс". Он достиг уже значительного уровня, поэтому может открывать бой с боссом. Чтобы открыть новый бой, ему нужно набрать не менее, чем K очков за миссии. Известно, что всего есть N миссий. Для каждой миссии известно сколько времени будет продолжаться её прохождение и сколько за ней будет начислено очков. Также известно, что Вася является очень хорошим игроком, а значит он с лёгкостью сможет пройти любую миссию.

К сожалению, у него нет времени, чтобы пройти все миссии, но очень хочется открыть бой с боссом, поэтому он хочет узнать за какой минимальный промежуток времени он сможет набрать не менее K очков.

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

В первой строке заданы два целых числа N и K (1N100 – количество миссий, 0K10000 – количество очков, которое нужно набрать, чтобы открыть бой с боссом). В последующих N строках задано по два целых числа: a[i] – количество очков, которые можно получить за прохождение i-й миссии и t[i] – время, нужное для её прохождения, 0 < a[i], t[i]100.

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

Виведите минимальное время, за которое Вася сможет набрать не менее K очков, или "-1" если это сделать невозможно.

Time limit 1 second
Memory limit 64 MiB
Input example
Sample 1
4 10
5 5
3 1
10 10
7 6

Sample 2
5 12
6 2
5 5
1 5
10 10
4 4
Output example
Sample 1
7

Sample 2
11