#1222. 零件回收

零件回收

救治伤员

本题是纪念 12·14 北京地铁昌平线事故所作。

Background

121214141919 时左右,北京地铁昌平线西二旗站 - 生命科学园站上行区段一列车车厢脱离,迫停区间。

Description

医术高超的小核桃去现场搜集车厢掉落的零件。

NN 个零件,小核桃有 VV 小时的时间。

ii 个零件送达车辆段的时间是 viv_i,价值是 wiw_i

求解在时间足够的情况下,被送回车辆段的零件价值最大。

输出最大价值。

Format

Input

第一行两个正整数,NNVV,用空格隔开,分别表示物品数量和背包容积。

接下来有 NN 行,每行两个整数 viv_iwiw_i,分别表示第 ii 件物品的体积和价值。

题目中所有变量均 1000\leq 1000

Output

一个整数,代表能救治的最大的身价总和

Samples

4 5
1 2
2 4
3 4
4 5
8