时空限制

1S/512M

题目描述

作为一名策略卡牌游戏玩家，你正面临一场决战。你手中握有 $n$ 张卡牌，每张牌 $i$ 的信息由以下三个参数决定：

• 费用 $c_i$：打出该牌需要消耗的法力值。
• 类型 $t_i \in \{0, 1\}$：其中 $t_i = 0$ 表示该牌为伤害牌；$t_i = 1$ 表示该牌为强化牌。
• 参数 $x_i$。

你当前拥有 $C$ 点法力值上限。你需要选择若干张手牌（每张牌最多选择一次）并以任意顺序打出，选出的手牌总费用之和不能超过 $C$。

打出牌的效果如下：

• 强化牌：使你的法术强度永久增加 $x_i$。
• 伤害牌：造成 $x_i$ 次伤害，每次基础伤害为 $1$。每次伤害都会额外加上打出该伤害牌时的当前法术强度值。

游戏开始前，你的初始法术强度为 $0$。请你选择一种最优的卡牌组合与打出顺序，求能造成的最大总伤害。

格式

输入格式

第一行包含两个正整数 $n$ 和 $C$，分别表示手牌的总张数以及你拥有的最大法力值。

接下来的 $n$ 行，每行包含三个整数 $c_i, t_i, x_i$，分别代表第 $i$ 张牌的费用、类型以及参数。

输出格式

输出一行一个整数，代表能够造成的最大总伤害。

样例

样例输入 #1

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

样例输出 #1

18

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \le n, C \le 1000$，$1 \le c_i \le 1000$，$t_i \in \{0, 1\}$，$1 \le x_i \le 10^5$。