Bob is going shopping now! From the previous question, he figured out he has cents to spend. At the store, he spots items that catch his interest, each of which having its own value. Since he doesn't make the best financial decisions, if he is able to buy the current item with the amount of money he has left, he will always buy it. Please find the total value of the items he will purchase at the store! Note that he cannot skip items if he has the money to purchase it, and if he cannot purchase it, he will move onto the next item. Note that this means that he will always try to purchase every item in order.
Input Specification
The first line of input will contain two space-separated integers , representing the number of items that caught his interest and the number of cents he has to spend, respectively.
The next lines will contain values and , indicating the cost and value of the item, respectively.
Output Specification
Output one integer, representing the value of the items he will purchase.
Subtasks
Subtask 1 [10%]
Subtask 2 [90%]
Sample Input 1
1 10
8 15
Sample Output 1
15
Sample Explanation 1
Bob has cents, so he is able to purchase the one item with cost cents, which gives a value of .
Sample Input 2
5 50
5 10
45 1
5 10
5 10
5 10
Sample Output 2
11
Sample Explanation 2
Bob can buy the first item, leaving him with cents and a total value of . He spots the second item, and he has enough money to purchase it, so he instantly buys it (even though it gives less value than skipping this item and buying the last three), which gives him a total value of .
Comments