tententen吃中饭

Time Limit: 1 s Memory Limit: 256 MB

Submission：150 AC：55 Score：0

Description

又到了吃中饭的时间，tententen大宝贝想要吃得开开心心的。
已知tententen的肚子空间容量为 $W$ ,餐桌上有 $n$ 种食物，每种食物都有且只有一份。对于第 $i$ 种食物，能使tententen开心值增加 $v_i$ ,并占用她的肚子容量 $w_i$ (tententen坚持光盘行动，选了一种食物就一定会吃光)
现在，请你帮助tententen挑选食物，使得她尽可能得开心。
输出tententen总开心值的最大值。

Input

第一行给定两个数字 $n$ , $W$ 。其中 $n$ 为餐桌上的食物种类数， $W$ 为tententen的肚子空间容量。 $（1 \leqslant n \leqslant 1000,1 \leqslant W \leqslant 3000)$
接下来 $n$ 行，分别给出第 $i$ 种食物的 $w_i$ 和 $v_i$ 。 $w_i$ 为占用空间， $v_i$ 为开心值
$(1 \leqslant w_i,v_i \leqslant 200)$

Output

输出一个正整数，代表tententen能达到的最大开心值。

Samples

input

2 10 7 99 6 98

output

input

3 13 7 99 6 98 8 144

output

197

Hint

一定要让tententen吃得最开心才行噢！！！也不能把她撑坏啦