TIEROPE - Tie the Rope


Sailor Crow'n-beard has many pieces of rope. Every piece has a different value and it is well known that money equals quality. Crow'n-beard wants you to create a program that given pieces of rope, creates a rope with the length as close as possible to his desired length (but never too short) while maximizing the quality.

Input

Input describes a single test case. The first line contains two integers N (1 ≤ N ≤ 80) and L (1 ≤ L ≤ 10000): the number of rope pieces Crow'n-beard and the desired length respectively. Then N lines will follow, each with two integers: the length Li (0 ≤ Li < 2^31) followed by the value Vi (0 ≤ Vi ≤ 26843545) of the piece of rope. It is guaranteed that the sum of Li is never less than L.

Output

You should output the maximal total quality you can reach. Remember that the priority is to get the smallest total length that is still at least equal to L. Only then output the best total quality amongst equal length solutions.

Sample

Input:
4 4
20 2
1 4
3 4
4 7

Output:
8

hide comments
raunakrocks: 2013-08-12 17:56:27

why wa again n again!! sub id:9821720 plz. help :(

Mitch Schwartz: 2013-08-12 17:56:27

"Note that the desired length can always be reached." -- Does that mean it's always possible to reach the desired length exactly, or that it's always possible to reach or exceed the desired length?

Edit: Thanks for the reply.

Last edit: 2013-08-11 19:28:29

Added by:Laurens
Date:2013-08-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem