在 nnn 个分属于总共 mmm 类的物品中，第 iii 号物品的重量为 wiw_iwi，价值为 viv_ivi，归属于第 tit_iti 类, 保证对于任意 1≤i≤m1\leq i \leq m1≤i≤m 有 ti=it_i=iti=i。 且对于第 iii 类物品，物品 iii 为必选物品。
请选择一定数量的物品，使得这些物品的 viv_ivi 和在满足以下条件的同时尽可能大：
请输出这一最大值。
输入数据的第一行一个整数 T(1≤T≤5)T(1\leq T\leq 5)T(1≤T≤5)，表示测试数据组数。
接下来每个测试数据第一行两个整数 n,m,W(1≤n≤103,1≤m≤n,0≤W≤104)n,m,W(1\leq n\leq 10^3,1\leq m\leq n,0\leq W\leq 10^4)n,m,W(1≤n≤103,1≤m≤n,0≤W≤104)。
接下来 nnn 行，每行有三个整数，第 iii 行的三个数字分别为 wi,vi,ti(1≤wi,vi≤109,1≤ti≤m)w_{i},v_{i},t_i(1\leq w_i,v_i\leq 10^9,1\leq t_i\leq m)wi,vi,ti(1≤wi,vi≤109,1≤ti≤m)。
对于每组测试数据请输出一行一个整数表示所求最大值。
1 1 1 5 5 8 1
8
