给定 件物品与一只最大可承重为 的背包。所有物品被划分为 个组别（组编号 ），同一组中的物品互斥：在最终方案中，每组至多选取 一件 物品。 第 件物品具有如下属性： 重量 ； 价值 ； 所属组别 。 请你在不超过背包承重 的前提下，选择若干物品使得总价值最大。

输入描述:

第一行输入两个整数 ——物品数量与背包容量。接下来 行，第 行输入三个整数 ，描述第 件物品的重量、价值与所属组别。

输出描述:

输出一个整数，表示在约束条件下可以获得的最大价值。