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
hello_world123: 2018-07-03 19:27:39

Awesome problem !!!

Riddhi: 2016-02-13 05:30:36

The sum of lengths of ropes is <=10^6

Mitch Schwartz: 2013-09-10 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: 2013-09-10 02:00:16
(Tjandra Satria Gunawan)(曾毅昆): 2013-08-24 20:45:01

@Mitch Schwartz: Thanks for your experiment :-)
@Laurens: Please fix problem description: "both N and L can be zero"

Laurens: 2013-08-14 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: 2013-08-14 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: 2013-08-12 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: 2013-08-12 17:56:27

How it's possible exceed the desired length?
pls explain.....

(Edit) @Mitch Schwartz : Thanks for reply.

Last edit: 2013-08-11 20:55:03
Mitch Schwartz: 2013-08-12 17:56:27

Please give constraints for the length and value of a piece of rope.

Edit: From experimentation, the length and value of a piece of rope can both be zero, there are no negative integers in the input, and everything can be done with signed 32-bit integers.

Last edit: 2013-08-11 20:50:11
Laurens: 2013-08-12 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.


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