商店中有 $n$ 件商品，你有 $m$ 元钱。第 $i$ 件商品有三个属性：价格 $p_i$、价值 $v_i$ 和优先级 $c_i$。

你需要按照如下规则确定购买商品的顺序：

1. 优先级较高的商品排在前面，优先级数字越大表示优先级越高；
2. 如果两件商品优先级相同，则性价比更高的商品排在前面；
3. 如果优先级和性价比均相同，则编号较小的商品排在前面。

商品的性价比定义为 $\dfrac{v_i}{p_i}$，商品编号为其在输入中出现的顺序，从 $1$ 开始编号。

确定顺序后，依次考虑每一件商品。如果当前剩余的钱足够购买该商品，就购买它，并扣除相应的钱；否则跳过该商品，继续考虑下一件。

求最终购买到的所有商品的价值之和。

输入格式

第一行包含两个整数 $n,m$，分别表示商品数量和初始拥有的钱。

接下来 $n$ 行，每行三个整数 $p_i,v_i,c_i$，分别表示商品的价格、价值和优先级。

输出格式

输出一个整数，表示最终购买到的商品价值总和。

样例 1

输入：

5 20
8 16 2
10 30 1
5 8 2
7 14 3
6 12 2

输出：

38

提示与约束

数据范围

对于所有数据：

• $1\le n\le 100000$；
• $1\le m\le 10^9$；
• $1\le p_i,v_i\le 10^6$；
• $1\le c_i\le 100$。

来源：Luogu_U719052。本站使用重新构建的测试数据。