解题思路

本题是一个典型的二维费用分组背包问题。

一共有 $n$ 个任务，每个任务最多只能选择一种执行方式：

• 不执行该任务
• 使用常规模式，消耗 $a_i$ 个 $token$ 和 $b_i$ 的时间
• 使用降耗模式，消耗 $c_i$ 个 $token$ 和 $d_i$ 的时间

题目内容

多多有 $n$ 个任务需要完成。每个任务有两种执行模式，多多对于每个任务最多只能选择一种模式执行，也可以选择不执行：

1. 常规模式：花费 $a_i$ 个 $token$ 和 $b_i$ 的时间。

2. 降耗模式：通过增加时间成本来降低 $token$ 消耗，总共花费 $c_i$ 个$token$ 和 $d_i$ 的时间。

多多目前拥有的总 $token$ 预算为 $m$，总时间预算为 $t$。 请问在不超过 $token$ 和时间预算的前提下，多多最多可以完成多少个任务？

输入描述

第一行包含三个整数 $n$、$m$ 和 $t$，分别表示任务总数、总 $token$ 预算和总时间预算。

接下来的 $n$ 行，每行包含四个整数 $a_i$、$b_i$、$c_i$ 和 $d_i$，分别表示第 $i$ 个任务的：

• $a_i$：常规模式下的 $token$ 消耗

• $b_i$：常规模式下的时间消耗

• $c_i$：降耗模式下的 $token$ 消耗

• $d_i$：降耗模式下的时间消耗

• $1 \le n \le 50$

• $1 \le m, t \le 200$

• $1 \le c_i < a_i \le 100$

• $1 \le b_i < d_i \le 100$

输出描述

输出一个整数，表示在预算范围内最多能够完成的任务数量。

样例1

输入

3 10 10
5 5 2 8
4 3 3 5
8 2 4 6

输出

2

说明

不执行第$1$个任务。

以常规模式执行第$2$个任务，花费$4$个$token$，$3$的时间。

以降耗模式执行第$3$个任务，花费$4$个$token$，$6$的时间。