Description

You are a theif sneaking into a house that contains N items. You carry a bag and want to steal some valuable items from the house. Unfortunately, your bag can hold at most K kilograms. As a smart theif, you know exactly the value Vi and the weight Wi of each item.
Since your bag is not strong enough to carry over the limit of K (the sum of weight Wi you carry must be less then K).
What is the highest value you can carry out from this house?

Input

The first line contains two integers N and K, representing the number of items in the house and how much can the bag hold.

Each of the following N lines contain two integers Vi and Wi, describing the value and weight of the i-th item.

It is guaranteed that :

• 0 ≤ Vi, Wi ≤ 10³
• For test case #1~9: 1 ≤ N ≤ 20, 0 ≤ K ≤ 10³
• For test case #10: 1 ≤ N ≤ 100, 0 ≤ K ≤ 10³

Output

Print the most value the thief can get.

(you need to print a newline '\n' right following your answer)

For the sample test case, we can choose the third item (6,3) and the fifth (5,4) item. The maximum value the thief can get would be 11.

Sample Input  Download

Sample Output  Download

Discuss