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

题目背景

公元 2147 年，L 国与 I 国之间的信息战已进入白热化阶段。L 国情报总局截获了一段被“幽灵协议”加密的绝密通信：I 国正在秘密建设名为“天穹之眼”的全球监控阵列。该阵列一旦完全激活，L 国所有潜伏在 I 国的特工都将在 $72$ 小时内被精准定位并清除。

为了阻止“天穹之眼”计划，L 国最高议会召开紧急会议，决定启动最高机密行动——“镜渊”。你被任命为“镜渊”行动总指挥，必须从一批候选特工中挑选若干人，潜入 I 国核心网络节点，窃取关键情报。

每名候选特工都有一份绝密档案。档案中包含三项评估数据：

• $A_i$：该特工成功潜入后能带回的核心情报量；
• $B_i$：该特工身份伪装的“可疑度”，I 国“猎隼”反谍系统会累加所有派遣特工的可疑度；
• $C_i$：派遣该特工需要支付的加密星币工资。

I 国“猎隼”反谍系统的总容忍可疑度为 $M$。如果所有被派遣特工的可疑度之和超过 $M$，行动就会被发现，所有特工将陷入危险。

L 国情报总局当前可支配的加密星币总数为 $X$。所有被派遣特工的工资之和不能超过 $X$，否则金库无法完成支付，行动同样会被迫中止。

每名候选特工最多只能被派遣一次，也可以选择不派遣。特工之间没有协同加成，也没有相互暴露风险。I 国反谍系统只会简单累加每名特工的可疑度，L 国金库也只会简单累加每名特工的工资。

你的任务，是在满足“可疑度之和不超过 $M$”且“工资之和不超过 $X$”的前提下，选择若干名特工派遣，使得能够带回的核心情报总量最大。

任务简报

设最终被选中的特工集合为 $S$。
对于每名特工 $i$，只有两种选择：

1. 派遣：付出工资 $C_i$，增加可疑度 $B_i$，获得情报量 $A_i$；
2. 不派遣：不付出工资，不增加可疑度，不获得情报量。

行动必须满足：

$\sum_{i \in S} B_i \le M$

$\sum_{i \in S} C_i \le X$

目标为最大化：

$\sum_{i \in S} A_i$

如果一名特工都不派遣，也是合法方案，此时总可疑度为 $0$，总工资为 $0$，总情报量为 $0$。

输入格式

第一行包含三个整数 $N, M, X$，分别表示候选特工数量、I 国“猎隼”反谍系统总容忍可疑度、L 国可支配加密星币总数。

接下来 $N$ 行，每行包含三个整数 $A_i, B_i, C_i$，分别表示第 $i$ 名候选特工能带回的情报量、可疑度和所需工资。

输出格式

输出一行一个整数，表示在满足所有限制的前提下，能获得的最大核心情报总量。

样例

输入

3 10 12
10 1 11
1 9 1
7 10 12

输出

11

样例解释

选择第 $1$ 名特工和第 $2$ 名特工：

• 总可疑度：$1 + 9 = 10 \le 10$
• 总工资：$11 + 1 = 12 \le 12$
• 总情报量：$10 + 1 = 11$

其他可行方案获得的情报量都不超过 $11$，因此答案为 $11$。

数据范围与约定

对于 $30\%$ 的数据：

• $1 \le N \le 20$
• $1 \le M, X \le 200$

对于 $60\%$ 的数据：

• $1 \le N \le 60$
• $1 \le M, X \le 600$

对于 $100\%$ 的数据：

• $1 \le N \le 100$
• $1 \le M \le 1000$
• $1 \le X \le 1000$
• $1 \le A_i, B_i, C_i \le 1000$