题目描述

设有 $n$ 种物品，记作 $A_1$、$A_2$、$\dots$、$A_n$，对应于每个 $A_i$（$1 \le i \le n$）都有一个重量 $Aw_i$ 和价值 $Av_i$（重量和价值都为正整数）。另外，对应于每个 $A_i$，都有一件可代替它的"代用品" $B_i$，$B_i$ 的重量和价值分别为 $Bw_i$ 和 $Bv_i$。

本题的任务是：选择这 $n$ 件物品或其代用品的一个子集装进背包，使总重量不超过给定重量 $TOT$，同时使总价值 $VAL$ 最高。装填的第 $i$ 步，要么装入 $A_i$，要么装入 $B_i$，要么 $A_i$ 和 $B_i$ 都不装。

输入格式

第一行：$n,TOT$

第二行：$Aw_1,Av_1,BW_1,Bv_1$

第三行：$Aw_2,Av_2,Bw_2,Bv_2$

$\dots$

第 $n+1$ 行：$Aw_n,Av_n,Bw_n,Bv_n$

输出格式

只有一个数为最大的价值

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

40

数据范围

$n \le 100$

$TOT \le 10000$