太空舱的物资装载

题目描述

深空救援队要为一艘太空舱装载物资。货舱容量为 $W$，有 $n$ 件物资，每件物资的体积和价值已知。每件物资只能选择装或不装，不能分割。请你帮助队伍在不超过容量的前提下，让舱内物资总价值最大。

输入格式

第一行包含两个整数 $n,W$。

接下来 $n$ 行，每行包含两个整数，依次表示一件物资的体积与价值。

输出格式

输出一个整数，表示可以获得的最大总价值。

输入输出样例 #1

输入 #1

4 8
3 6
2 4
4 5
3 6

输出 #1

16

数据范围

对于 $100\%$ 的数据，$1 \le n \le 200$，$1 \le W \le 2000$，体积与价值均在 $[1,10^4]$。EOF