eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Майстер "Ворміксу"

Майстер "Ворміксу"

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Василько просто у захваті від гри "Вормікс". Він досягнув вже значного рівня, тож може відкривати бій із босом. Щоб відкрити новий бій, йому потрібно набрати не менше, ніж K очок за місії. Відомо, що всього є N місій. Для кожної місії відомо скільки часу триватиме її проходження і скільки за неї буде нараховано очок. Також відомо, що Василько є дуже добрим гравцем, а отже він з легкістю зможе пройти будь-яку місію.

На жаль, він немає часу, щоб пройти всі місії, але дуже хоче відкрити бій з босом, тож він хоче дізнатися за який мінімальний проміжок часу він зможе набрати не менше K очок.

Вхідні дані

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

Вихідні дані

Виведіть мінімальний час, за який Василько зможе набрати не менше K очок, або "-1" якщо цього зробити неможливо.

Приклад

Вхідні дані #1
4 10
5 5
3 1
10 10
7 6
Вихідні дані #1
7