T217220 [FTLOI R1]幻想

上课的幻想总是很奇妙的，特别是物理课。 cgy在上物理课时幻想到了一个美妙的故事。。。

魔法扫帚不停地往前飞。它有两个属性：魔法值和魔力值（用 $p$ 表示）。它的初始魔法值为 $0$，魔力值为 $k$ 。它现在要在一条路上不回头地飞。这条路上依次有 $n$ 间房屋。每间房屋会有一个给定的类型。对于每间房屋，它可以选择进与不进。如果他进入第 $i$ 间则，则： + 若该房间为魔法型，那么扫帚的魔法值将会加上 $a_i\times p$，然后 $p$ 减少 $d_i$。 + 若该房间为魔力型，那么扫帚的魔法值将会减去 $a_i\times p$，然后 $p$ 增加 $d_i$。 注意，魔法值和魔力值可以在某个时候是负的。 请问魔法扫帚最后魔法值最多可以是多少。

第一行两个整数 $n$ 和 $k$。 接下来 $n$ 行，每行三个整数 $t_i,a_i,d_i$ 依次表示道路上的 $n$ 个房间。若 $t_i$ 为 $1$，则该房间为魔法型，若 $t_i$ 为 $2$，则该房间为魔力型。

一个整数表示魔法扫帚最后魔法值最大值。

#### 样例解释 每个房间都进去。 #### 数据范围 **本题采用捆绑测试** 对于 $100\%$ 的数据，$1\le n\le2\times10^3$，$1\le t_i\le2$，$1\le a_i\le5$，$1\le k,d_i\le10^9$。 **Subtask1(15pts):** $1\le n\le20$，$1\le t_i\le2$，$1\le a_i\le5$，$1\le k,d_i\le10^9$。 **Subtask2(35pts):** $1\le n\le2\times10^3$，$1\le t_i\le2$，$1\le a_i\le5$，$1\le k,d_i\le5$。 **Subtask3(50pts):** $1\le n\le2\times10^3$，$1\le t_i\le2$，$1\le a_i\le5$，$1\le k,d_i\le10^9$。