#P3048. 奥奥购物

奥奥购物

Description

当前有N件物品和一个容积为V的背包。已知第i件物品的体积是ci​,价值是wi​。每种物品有且仅有一件,并且体积不可分割。现在你需要选出若干件物品,在它们的重量之和不超过V的条件下,使得价值总和尽可能大。

Input Format

输入 n+1 行

第一行输入两个整数 VN,分别表示背包容积以及物品数量。

第 2~n+1 行,每行输入两个变量,分别是表示物品的价值和体积。

Output Format

输出一行,表示N件物品中,在背包容积V内能够挑选的物品的最大价值。

10 5 
2 1
3 5
2 5
3 4
4 3
15

Source

信奥星OJ http://127.0.0.1