g6-08119. 轮流促销 未做

便利店的促销规矩轮流换，每笔订单都写清楚了这次用哪种卖法：标号 $k=0$ 时每种商品只有一件，$k=1$ 时每种商品管够、想拿几件拿几件。一共 $t$ 笔订单，每笔订单有 $n$ 种商品，第 $i$ 种每件重 $w_i$、价值 $v_i$，购物袋最多装 $V$。请算出每笔订单最多能拿到的总价值。

第一行一个整数 $t$。

接下来 $t$ 组数据，每组格式为：

• 一行三个整数 $k$、$n$、$V$；
• 接下来 $n$ 行，每行两个整数 $w_i$、$v_i$。

输出 $t$ 行，每行一个整数，表示该组数据的最大总价值。

输入 1

2
0 1 6
2 3
1 1 6
2 3

输出 1

3
9

第一笔订单每种只有一件，只能拿一件价值 3 的商品；第二笔订单每种管够，拿三件重 2 的商品正好重 $2\times 3=6$，价值 $3\times 3=9$。

$1\le t\le 5$，$1\le n\le 30$，$0\le V\le 500$，$1\le w_i\le 60$，$0\le v_i\le 200$。答案在 64 位整数内。