题目描述

暑假打工：小明放暑假了，想赚点零花钱，于是想去打工，现在有n份零工，每份零工的时间花费是t1…tn小时，每份零工的工钱是w1…wn元，小明想每天只工作k小时，问小明该如何选择这些零工，才能使得自己的每天收入最高？

输入

输入第一行为n(n<=10)和k(k<=300)，表示有n份工作，工作总时间为k小时，接下来有n行，每行两个整数ti和wi，表示第i项工作的时间花费和工钱

输出

输出为一行，即小明每天所能拿到的最多工钱

样例

3 10
8 8
4 3
6 5

8