1854: box
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：0
解决：0
题目描述
设有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，同时使总价值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
第二行：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