Steve 发现了一款他非常想玩的全新 RPG 电子游戏。这款游戏非常独特：能够以最优方式通关的玩家可以获得全额退款！这对 Steve 来说真是个大好消息！

游戏共有 $n$ 个关卡。玩家从关卡 1 开始，初始等级为 1，并拥有自选的初始生命值（HP）。

每个关卡都有若干只怪物，每只怪物都有特定的攻击力。在每个关卡中，玩家必须选择与该关卡中现存怪物的一个非空子集进行交战。战斗采用回合制系统：

• 首先，所有存活的怪物发动攻击，每只怪物对玩家造成的伤害等于其攻击力。
• 然后，玩家选择一只已交战的怪物并将其消灭（该怪物此后将不再攻击玩家）。
• 每次消灭怪物都会使玩家提升 1 级（最高可升至 $m$ 级）。

一旦关卡 $i$ 中所有选定交战的怪物都被消灭，玩家将恢复 $h_l$ 点生命值（其中 $l$ 是消灭所有这些怪物后的玩家等级），并进入关卡 $i + 1$。通过关卡 $n$ 后游戏结束。玩家在游戏过程中拥有的生命值没有上限。

Steve 的目标是在不曾使生命值降至 0 或更低的情况下，以最高等级 $m$ 通关。Steve 会采取最优策略，这意味着他需要选择最小的可能初始生命值，以便能够以最高等级通关。

输入格式

输入的第一行包含两个整数 $n$（$1 \le n \le 100$）和 $m$（$1 \le m \le 50\,000$），分别表示关卡数量和游戏中可以达到的最高等级。

第二行包含 $m$ 个整数 $h_1, h_2, \dots, h_m$（$1 \le h_1 \le h_2 \le \dots \le h_m \le 10^6$），表示玩家根据其等级获得的生命值恢复量。

接下来的 $n$ 行描述这 $n$ 个关卡。其中第 $i$ 行包含一个整数 $k_i$（$1 \le k_i \le 2000$），表示关卡 $i$ 中的怪物数量，随后是 $k_i$ 个整数 $s_{i,1}, s_{i,2}, \dots, s_{i,k_i}$，表示这 $k_i$ 只怪物中每只的攻击力。

所有怪物的攻击力均在 $1$ 到 $10^4$ 之间（含边界）。此外，保证整个游戏中至少有 $m - 1$ 只怪物。

输出格式

输出一个正整数，表示所需的最小初始生命值。

样例

输入样例 1

3 4
1 2 10 11
3 6 2 3
2 11 12
4 9 11 10 5

输出样例 1

9

说明

Steve 以 9 点 HP 进入第一个关卡。他选择与攻击力为 2 和 3 的怪物交战。

他开始战斗，首先承受 $2 + 3 = 5$ 点伤害，然后消灭攻击力为 3 的怪物；接着承受剩下的 2 点伤害，并消灭最后一只怪物。在此过程中，他的等级提升到 3，获得 $h_3 = 10$ 点 HP 的恢复，并以总共 12 点 HP 进入下一关（$9 - 5 - 2 + 10 = 12$）。

在第二个关卡中，Steve 选择与攻击力为 11 的怪物交战，承受 11 点伤害并将其消灭。他现在达到了等级 4，因此获得 $h_4 = 11$ 点 HP 的恢复，并以总共 12 点 HP 进入下一关（$12 - 11 + 11 = 12$）。

在第三个关卡中，Steve 选择与其中一只怪物交战（无论是哪一只），承受伤害并将其消灭（由于已达到最高等级，此时不再升级），最终以最高等级 4 结束游戏。