题目描述

皇室战争（Clash Royale）是一款实时策略卡牌游戏。每张卡牌具有攻击力和等级。每位玩家选择 8 张卡牌组成一副战斗牌组；牌组的总攻击力是其每张卡牌攻击力之和。玩家通过将战斗牌组中的卡牌放置到竞技场中进行对战。战斗的胜者会获得金币，金币可用于升级卡牌。升级卡牌会增加其攻击力。

经过多日的竞技场战斗，Little Shawn 已经积累了共计 $M$ 枚金币。他决定升级他的一些卡牌。Little Shawn 拥有 $N$ 张卡牌。第 $i$ 张卡牌的等级可以是 1 到 $K_i$ 之间的任意值；第 $j$ 级对应的攻击力为 $A_{i,j}$。卡牌必须逐级升级；将第 $i$ 张卡牌从等级 $j$ 提升到等级 $j+1$ 需要花费 $C_{i,j}$ 枚金币。在 Little Shawn 进行任何升级之前，第 $i$ 张卡牌当前的等级为 $L_i$。

Little Shawn 希望使用部分或全部的金币来升级卡牌，然后组成恰好包含 8 张卡牌的牌组，使得牌组的总攻击力尽可能大。你能帮助他实现这一目标吗？只要金币足够，他可以多次升级同一张卡牌，而且不一定要升级每一张卡牌。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例以两个整数 $M$ 和 $N$ 开头，分别表示金币数量和 Little Shawn 拥有的卡牌数量。随后有 $N$ 个数据块。第 $i$ 个数据块由 3 行组成，用于描述第 $i$ 张卡牌。第一行包含两个整数 $K_i$ 和 $L_i$，表示该卡牌的最大可能等级和当前等级。第二行包含 $K_i$ 个整数 $A_{i,1}, A_{i,2}, \dots, A_{i,K_i}$，表示每个等级的攻击力。第三行包含 $K_i - 1$ 个整数 $C_{i,1}, C_{i,2}, \dots, C_{i,K_i-1}$，表示将当前等级为 1, 2, …, $K_i-1$ 的卡牌提升一级所需花费的金币数。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Little Shawn 使用他拥有的金币所能组成的牌组的最大可能总攻击力。

2
20 8
3 1
1 10 100
1 2
3 1
1 10 100
1 3
3 1
1 10 100
1 4
3 1
1 10 100
1 5
3 1
1 10 100
1 6
3 1
1 10 100
1 7
3 1
1 10 100
1 8
3 1
1 10 100
1 9
30 10
4 1
1 10 100 200
1 2 3
3 1
1 10 100
2 4
3 1
1 10 100
3 6
4 2
1 10 100 200
4 8 16
3 1
1 10 100
5 10
3 1
1 10 100
6 12
3 1
1 10 100
7 14
3 1
1 10 100
8 16
3 1
1 10 100
9 18
3 1
1 10 100
10 20

Case #1: 422
Case #2: 504

提示

在样例 #1 中，你可以将前 4 张卡牌升级到等级 3，将第 5 和第 6 张卡牌升级到等级 2，最后 2 张卡牌保持等级 1。这样花费的金币为 $(1+2)+(1+3)+(1+4)+(1+5)+1+1 = 20$，总攻击力为 $100+100+100+100+10+10+1+1 = 422$，这是所能获得的最大值。

样例 #2 仅会出现在大数据集中。

限制条件

$1 \le T \le 100$。

$1 \le K_i \le 10$。

$1 \le L_i \le K_i$。

$A_{i,j} < A_{i,j+1}$。

小数据集（测试集 1 – 可见）

$1 \le M \le 1,000$。

$N = 8$。

$1 \le A_{i,j} \le 1,000$。

$1 \le C_{i,j} \le 1,000$。

大数据集（测试集 2 – 隐藏）

$1 \le M \le 1,000,000,000$。

$8 \le N \le 12$。

$1 \le A_{i,j} \le 1,000,000,000$。

$1 \le C_{i,j} \le 1,000,000,000$。

翻译由 DeepSeek V4 Pro 完成