纪念品背包

题目描述

有 n 件纪念品，第 i 件重量为 w_i、价值为 v_i。背包容量为 V，每件纪念品最多选一次，求可获得的最大总价值。

输入格式

第一行两个整数 n,V。接下来 n 行，每行两个整数 w_i,v_i。

输出格式

输出一个整数，表示最大总价值。

数据范围

1 ≤ n ≤ 100，1 ≤ V ≤ 1000，1 ≤ w_i ≤ V，1 ≤ v_i ≤ 10^6。

样例输入

1 5
3 10

样例输出

10

第一行两个整数 n,V。接下来 n 行，每行两个整数 w_i,v_i。

输出一个整数，表示最大总价值。

1 ≤ n ≤ 100，1 ≤ V ≤ 1000，1 ≤ w_i ≤ V，1 ≤ v_i ≤ 10^6。