题目描述

小胡有一个大小为 V 的背包，同时有 n 个物品，每个物品有两个属性 vi,wi，分别表示体积和价值。

每件物品都可以选或者不选，假设所选物品的体积之和为sumv，价值之和为sumw。请问在 sumv ≤ V 的情况下，sumw 最大是多少？

输入格式

有 t组输入

有 n件物品和一个容量是 v的背包。每件物品只能使用一次。


第 i件物品的体积是 vi，价值是 wi。


求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。


0

0

0

-1e18≤vi*wi≤0

输出格式

输出最大价值

2
1 3
0 2
2 5
0 5
5 0

2
5

提示

这题真的是背包么？？？