2429: box

设有n种物品，记作A1、A2、…、An，对应于每个Ai（1≤i≤n）都有一个重量Awi和价值Avi（重量和价值都为正整数）。另外，对应于每个Ai，都有一件可代替它的"代用品"Bi，Bi的重量和价值分别为Bwi和Bvi。
本题的任务是：选择这n件物品或其代用品的一个子集装进背包，使总重量不超过给定重量TOT，同时使总价值VAL最高。装填的第I步，要么装入Ai，要么装入Bi，要么Ai和Bi都不装。

第一行：n TOT ，n≤100, TOT≤10000
第二行：AW1  A v1  B W1  Bv1
第三行：AW2  A v2  B W2  Bv2
……
第n+1行：AWn  A vn  B Wn  Bvn

只有一个数为最大的价值

4 20
8 20 12 31
2 3 9 20
13 31 11 12
8 9 13 36

40