你有 N 个物品,第 i 个物品的重量为 Ai ,体积为 1 ,价值为 Bi ,你还有一个背包,背包的容积为 K ,所能承受的最大重量为 W ,现在你要将一些物品放入背包中,求放入背包的物品的最大价值。
输入共三行。
第一行输入一个数 W(1≤W≤10000) ,表示背包所能承受的最大重量。
第二行输入两个数 N,K(1≤K≤N≤50) ,表示物品的数量和背包的容积。
剩下的 n 行分别输入两个数 Ai,Bi(1≤Ai≤1000,1≤Bi≤100) ,表示第 i 个物品的重量和价值。
一个数 ans ,表示放入背包的物品的最大价值。