该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

设有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

输入数据：

只有一个数为最大的价值

样例

输入文件：box.in

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

输出文件：box.out

40