题目描述

在Len之后，STI-LZ的人也开始接触《昨日圆车》这款游戏。而他们认为Len只会抢一件商品的行为太过铸币，于是要求你来帮助他们。

原来坎诺特在每关都会刷出一个商店，每次玩家都可以选择在商店购买和抢劫，而抢劫之后的战利品是整个商店里的藏品。而同样的，抢劫之后无法在商店购买任何东西。

由于数据丢失，现给出 $m,w$ 代表拥有的源石锭和物品数，$w_{i},v_{i},t_{i}$ 分别表示第i个物品的价格，价值和商店号。

简要题意

给定 $m$ 未排好序的物品和其价值和商店号 $v_{i},w_{i},t_{i}$，已知一共有$w$ 的背包容量，可以抢劫任意商店，获得该商店号的所有物品价值，但无法购买在此商店号之后的物品，求所能获得的最大价值 $v$

输入

第一行，两个整数 $m$ 和 $w$

第2~m+1行，三个整数$w_{i},v_{i},t_{i}$，表示价格，价值和商店号。

Output

一行一个整数，输出最大价值

样例

样例1

6 13
3 2 1
9 26 1
13 20 3
11 12 3
17 17 3
2 3 3

80

样例2

7 45
5 27 2
8 49 2
5 40 3
7 48 3
9 28 1
6 32 3
6 18 1

242

说明

一共有3组数据，第一组数据较小，占10分（忘了范围了），第二组适中占30分，第三组数据较大占60分，不需要较快的读入

神犇游戏，一共有2000个商店很合理吧

数据范围与约定

等一下写，先去打Atcoder