#abc0154. [abc015_4]高橋くんの苦悩

[abc015_4]高橋くんの苦悩

题目大意

你有 NN 个物品,第 ii 个物品的重量为 AiA_i ,体积为 11 ,价值为 BiB_i ,你还有一个背包,背包的容积为 KK ,所能承受的最大重量为 WW ,现在你要将一些物品放入背包中,求放入背包的物品的最大价值。

输入格式

输入共三行。

第一行输入一个数 W(1W10000)W(1\le W\le10000) ,表示背包所能承受的最大重量。

第二行输入两个数 N,K(1KN50)N,K(1\le K\le N\le50) ,表示物品的数量和背包的容积。

剩下的 nn 行分别输入两个数 Ai,Bi(1Ai1000,1Bi100)A_i,B_i(1\le A_i\le1000,1\le B_i\le100) ,表示第 ii 个物品的重量和价值。

输出格式

一个数 ansans ,表示放入背包的物品的最大价值。