题目描述

有 $n$ 种物品，每种物品都有其重量，体积，价值和数量，有的物品会有无数种，或没有体积或没有重量。 你有一个最大承重为 $m$，最大体积为 $s$ 的背包，求能获得的最大价值。

输入格式

第一行 $n,m,s$，表示物品的种类，背包承重和最大体积。 下面 $n$ 行分别是 $w_{i},v_{i},c_{i},p_{i}$，分别表示第 $i$ 种物品的重量，体积，价值，数量。 如果 $p_{i}$ 等于 $0$ 意味着这种物品有无数个。

输出格式

能获得的最大价值。

样例 #1

样例输入 #1

5 10 10
2 1 2 0
3 2 1 2
0 4 2 2
3 3 2 3
3 4 3 0

样例输出 #1

12

提示

$0\le n\le1000$。