K. 背包问题·改

在 $n$ 个分属于总共 $m$ 类的物品中，第 $i$ 号物品的重量为 $w_i$，价值为 $v_i$，归属于第 $t_i$ 类, 保证对于任意 $1\leq i \leq m$ 有 $t_i=i$。 且对于第 $i$ 类物品，物品 $i$ 为必选物品。

请选择一定数量的物品，使得这些物品的 $v_i$ 和在满足以下条件的同时尽可能大：

• 这些物品的 $w_i$ 和不超过给定值 $W$。
• 如果选择了任意一个归属于第 $i$ 类的物品，则选择中必须存在第 $i$ 号物品。

请输出这一最大值。

输入数据的第一行一个整数 $T(1\leq T\leq 5)$，表示测试数据组数。

接下来每个测试数据第一行两个整数 $n,m,W(1\leq n\leq 10^3,1\leq m\leq n,0\leq W\leq 10^4)$。

接下来 $n$ 行，每行有三个整数，第 $i$ 行的三个数字分别为 $w_{i},v_{i},t_i(1\leq w_i,v_i\leq 10^9,1\leq t_i\leq m)$。

对于每组测试数据请输出一行一个整数表示所求最大值。

样例输入

1
1 1 5
5 8 1

样例输出

8