题目描述

小 i 喜欢背包。

小 i 有 $n$ 个物品和一个容量为 $m$ 的背包，每个物品仅有一个，但是，与普通背包不同的是，有一些物品是可以切割的，即你不需要放进去一整个物品，你可以放进去一部分这个物品，物品每一部分的价值都是相等的。

每个物品都有一个重量和一个价值，小 i 想知道他背包可以装下的最大物品价值之和是多少。

输入格式

第一行包含三个整数 $n, m$。

接下来 $n$ 行，其中第 $i$ 行包含三个整数 $w_i, v_i, t_i$，分别表示第 $i$ 个物品的重量，第 $i$ 个物品每单位重量的价值，若 $t_i = 1$ 则说明这个物品是可分割的，否则说明这个物体不可分割。

$1 \\leq n \\leq 5 \ imes 10^3$

$1 \\leq m \\leq 5 \ imes 10^3$

$1 \\leq w_i \\leq m$

$1 \\leq v_i \\leq 10^9$

$0 \\leq t_i \\leq 1$

输出格式

一行一个整数代表最大价值。

样例

5 5 
3 1000000000 1 
3 100000000 1 
3 10000000 1 
3 1000000 1 
3 100000 1

3200000000

5 5 
3 100000000 1 
3 10000000 0 
3 1000000 0 
3 100000 1 
3 10000 1

300200000