题目描述

扶苏有一个容量为 $m$ 的背包，她还有 $n$ 种物品，每种物品要么只有一个，要么有无限多个。

一个第 $i$ 种物品的大小为 $w_i$，价值为 $v_i$。用 $c_i$ 表示第 $i$ 种物品的数量，则 $c_i = 1$ 表示该物品只有一个，$c_i = -1$ 表示该物品有无限多个。

现在扶苏想从这些物品中选择若干个装进背包，满足：

• 所选物品的总大小不超过背包容量。
• 可以任意地选择只有一个的物品，但是有无限多的物品只能挑选至多一种（可以是任意多个）放进背包。

她想知道满足上述要求的情况下，所选物品的总价值最大可以是多少？

输入格式

本题单个测试点有多组测试数据。第一行是一个正整数，表示测试数据数量 $T$。对每组数据，按如下格式读入：

第一行是两个整数，表示物品种类数 $n$ 和背包容量 $m$。
接下来 $n$ 行，每行三个整数 $w_i, v_i, c_i$ 表示第 $i$ 种物品的大小、价值和数量。

输出格式

对每组数据，输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

1
3 10
3 5 1
4 6 1
2 3 -1

输出 #1

15

输入输出样例 #2

输入 #2

1
3 5
2 5 1
3 6 1
3 4 -1

输出 #2

11

输入输出样例 #3

输入 #3

1
3 5
2 5 1
3 6 1
1 1 1

输出 #3

11

说明/提示

样例 1 解释

一种最优方案是全部都选择第三种物品放进背包，共可以放 $5$ 个。

样例 2 解释

一种最优方案是第一种和第二种物品各放一个在背包里。

数据规模与约定

用 $N$ 表示单个测试点内 $n$ 的和，保证 $1 \leq n \leq N$。

• 对 $30\%$ 的数据，$T \leq 10$，$n \leq 10$。
• 另有 $20\%$ 的数据，$c_i \neq -1$。
• 另有 $20\%$ 的数据，仅存在一种有无限多个的物品。
• 对 $100\%$ 的数据，$1 \leq N, m \leq 5000$，$1 \leq w_i \leq m$，$1 \leq v_i \leq 10^9$，$c_i \in \{-1, 1\}$。