TIEROPE  Tie the Rope
Sailor Crow'nbeard has many pieces of rope. Every piece has a different value and it is well known that money equals quality. Crow'nbeard 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'nbeard 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
Riddhi:
20160213 05:30:36
The sum of lengths of ropes is <=10^6 

Mitch Schwartz:
20130910 01:47:16
As the problem setter is not responding, I've updated the problem description, adding important info and cleaning up in general. The constraints are a little silly because I don't want to waste my time finding out sharper constraints by experimentation. And I removed the sentence "All of them are worthless, but when tied together they can form a useful rope" because it could be interpreted to mean that a solution has to use at least two pieces of rope, when in fact there is no such requirement. Last edit: 20130910 02:00:16 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130824 20:45:01
@Mitch Schwartz: Thanks for your experiment :)


Laurens:
20130814 17:42:31
@Kevin the answer would be 4. Since length 6 cannot be made, the first length that can is 7, and for 7 the optimal value is 4. 

Kevin Sebastian:
20130814 04:28:29
please explain for example if I have three ropes of length 2,3,5 and values 1,2,3 and desired length 6 then what would the answer be? 

Mitch Schwartz:
20130812 17:56:27
@maradona: If you have two pieces of rope with lengths 2 and 3, and the desired length is 4, then you will end up exceeding it and taking 5. 

maradona:
20130812 17:56:27
How it's possible exceed the desired length?


Mitch Schwartz:
20130812 17:56:27
Please give constraints for the length and value of a piece of rope.


Laurens:
20130812 17:56:27
@Mitch, the latter. @raunak see Mitch question, it also applies to your submission after i took a quick glance at your code. 

raunakrocks:
20130812 17:56:27
why wa again n again!! sub id:9821720 plz. help :( 
Added by:  Laurens 
Date:  20130811 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 