By Ricardo Oliveira, UFPR Brazil
You are going very well in your great quest as a wizard in the fantasy land. However, a new challenge has just appeared: a demogorgon, prince of demons, arised in front of you! To continue your quest, you must defeat it!
To defeat the demogorgon, you must take all of its P health points (HP). There are N spells available, numbered from 1 to N. Spell i causes Di damage points, i.e., Di health points (HP) are taken from the monster when spell i is used. To use spell i, you need to spend Mi mana (a certain amount of magic energy). Each spell can be used at most once.
Given the health points of the demogorgon and the spells you can use, determine the minimum amount of mana needed to defeat the monster.
The first line of each test case contains two integers N and P (1 ≤ N ≤ 1000, 1 ≤ P ≤ 2000), the number of spells available and the health points (HP) of the monster, respectively. Each of the next N lines describes a spell. Each line contains two integers Di and Mi (1 ≤ Di, Mi ≤ 1000), the damage caused by the spell and the amount of mana needed to use it, respectively. The input ends with end-of-file (EOF).
For each test case, if it is impossible to defeat the monster, print a line containing -1. Otherwise, print a line containing the minimum amount of mana needed to defeat the monster.
|Input Sample||Output Sample|