当前没有测试数据。

题目描述

Aki 有 $N$ 件物品，第 $i$ 件重量为 $w_i$，价值为 $v_i$。背包最大承重为 $W$。

请你求在总重量不超过 $W$ 的前提下，能得到的最大总价值。

输入格式

第一行两个整数 $N,W$。 接下来 $N$ 行，每行两个整数 $w_i,v_i$。

• $1\le N\le 100$
• $1\le W\le 10^9$
• $1\le w_i\le 10^9$
• $1\le v_i\le 1000$

输出格式

输出最大总价值。

3 8
3 30
4 50
5 60

90