SP15621 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 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**.

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.