题目描述

一个博物馆有一条线性走廊，由 $N$ 个房间组成，编号为 $1$ 到 $N$。第 $i$ 个房间中有无限多个同种金条，每根金条的价值为 $v_i$，重量为 $g_i$。

有 $K$ 个小偷从第 $1$ 个房间进入博物馆。每个小偷背着一个容量为 $G$ 的背包，初始为空。当一个小偷位于房间 $i$ 时，他可以偷任意多个该房间的金条放入背包，只要背包中金条总重量不超过 $G$。金条一旦被偷，就会一直留在背包中直到离开博物馆。

小偷们一起行动。在第 $i$ 步，所有小偷从房间 $i$ 走到房间 $i+1$，其中房间 $N+1$ 表示博物馆外部。也就是说，经过前 $i$ 步后，所有小偷都位于房间 $i+1$。

博物馆在每两个相邻房间之间都安装了报警器。报警器 $i$ 位于房间 $i$ 与房间 $i+1$ 之间，有一个参数 $x_i$。当小偷们经过这扇门时，如果此时存在至少 $x_i+1$ 个小偷的背包总重量完全相同，报警器就会响，小偷被抓。即使他们还什么都没偷，也可能触发报警。报警器 $N$ 位于房间 $N$ 与博物馆外部之间。

小偷们离开博物馆后，总收获定义为所有 $K$ 个背包中金条价值之和。

给定 $T$ 个场景。对于每个场景，求在不触发任何报警器的前提下，小偷们能获得的最大总价值；若无论如何都会被抓，则输出 $-1$。

输入格式

第一行输入一个整数 $T$，表示场景数。

接下来依次给出 $T$ 个场景。每个场景格式如下：

第一行输入三个整数 $N,K,G$。

接下来 $N$ 行，第 $i$ 行输入三个整数 $v_i,g_i,x_i$，表示房间 $i$ 的金条价值、重量以及房间 $i$ 与 $i+1$ 之间报警器的参数。

输出格式

输出 $T$ 行，按输入顺序输出每个场景的答案。

数据范围与约束

• $1\le T\le 900$；
• $1\le N\le 300$；
• $1\le K\le 50$；
• $1\le G\le 300$；
• $1\le v_i\le 300$；
• $1\le g_i\le 300$；
• $1\le x_i\le 50$；
• $1\le S_N\le 900$，其中 $S_N$ 表示所有场景中 $N$ 的总和。

子任务

样例

输入

3
2 1 3
10 2 1
9 1 2
2 2 3
10 2 1
9 1 2
2 3 3
10 2 1
9 1 2

输出

27
46
-1

样例解释

共有 $3$ 个场景。

第一个场景

$N=2,K=1,G=3$。房间 $1$ 中金条价值为 $10$、重量为 $2$；房间 $2$ 中金条价值为 $9$、重量为 $1$。报警器参数为 $x_1=1,x_2=2$。

只有一个小偷，因此不会触发报警。他最多可以从房间 $2$ 偷三根金条，价值为 $27$。

第二个场景

与第一个场景相同，但 $K=2$。如果两个小偷都从房间 $2$ 偷三根金条，总价值为 $54$，但他们在经过房间 $1$ 与房间 $2$ 之间的门时会被抓。事实上，即使什么都不偷，两人的背包重量也都为 $0$，也可能触发报警。

一种最优方案是：第一个小偷从两个房间各偷一根，价值 $19$；第二个小偷从房间 $2$ 偷三根，价值 $27$。总价值为 $46$。

第三个场景

与前两个场景类似，但 $K=3$。三个小偷无法安全通过第一道门，因此答案为 $-1$。