mm要搬寝室了，作为一个吃货，她认为和室友tt、cc饯别的最好方式是大吃一顿，于是她们来到点评还不错的悦阅西餐厅。
看到菜单后，mm十分忧愁，她胃口是有限的，可是什么都想吃！餐单上有 nnn 份菜，她给每份菜定义了饱腹度 xix_ixi 和美味度 yiy_iyi ，她的胃容量只有有限的 mmm 。
另外，有的菜mm认为比较健康比如蔬菜沙拉，无论吃多少份都没有问题；然而对于油荤的披萨和牛排，mm认为一餐吃超过一份会发胖，这是她不能接受的。
mm想知道自己在既不被撑死也不发胖的情况下能吃到的菜的美味度之和为多少？
第一行两个正整数 n, mn,\ mn, m 。
接下来 nnn 行，每行三个数 xi, yi, kix_i,\ y_i,\ k_ixi, yi, ki ，表示每种菜的饱腹度、美味度、最高份数量。其中 ki∈{−1, 1}k_i \in \{-1,\ 1\}ki∈{−1, 1} ，当 ki=−1k_i = -1ki=−1 时表示份数无限制，当 ki=1k_i = 1ki=1 时表示只能吃一份。
输出一行一个整数，表示mm吃到的菜的美味度之和。
2 10 3 7 1 2 4 -1
20
1≤n≤2001 \le n \le 2001≤n≤200
1≤m≤2⋅1051 \le m \le 2 \cdot 10^51≤m≤2⋅105
1≤xi≤2⋅1051 \le x_i \le 2 \cdot 10^51≤xi≤2⋅105
1≤yi≤1051 \le y_i \le 10^51≤yi≤105
ki∈{−1, 1}k_i \in \{-1,\ 1\}ki∈{−1, 1}