87. 雙重背包問題

0 Judge

Code: 0


雙重背包問題

個容量分別是$M$和$P$的背包和$N$個物品,第$i$個物品的體積是$a[i]$,價值是$b[i]$,選擇某些物品,每個物品放入其中一個背包內,兩個背包的總體積都不能超過背包容量,請問所選物品的總價值最大可以是多少?

輸入

第一行有三個正整數$N, M, P$。($1\leq N \leq 100, 1\leq M, P \leq 500$)

接下來有$N$行,第$i$行有兩個正整數$a[i]$和$b[i]$。($1\leq a[i] \leq 500, 1\leq b[i] \leq 10^7$)

輸出

最大的總價值。

子任務

子任務一(50%):$1\leq N \leq 10$

子任務二(50%):無特別限制

範例輸入1

4 3 7
2 5
6 9
4 10
3 3

範例輸出1

18

提示

第四個物品放入第一個背包內,第一和第三個物品放入第二個背包內。


Judge Setting

run-time limit: 1000 ms
memory limit: 512000000 byte
測資數量: 31