一队 $$$n$$$ 战士正在保卫一座城堡免受龙的攻击。城堡和龙之间有$$$m$$$路障。
战士的编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 个战士知道 $$$k_i$$$ 攻击:其中第 $$$j$$$ 对龙造成 $$$a_{i,j}$$$ 伤害,并且只有在城堡和龙之间正好有 $$$b_{i,j}$$$ 路障时才能应用。
战士们从$$$1$$$开始依次轮流。战士 $$$n$$$ 轮到他后,计算对龙的总伤害。第 $$$i$$$ 个战士在他的回合中执行三种可能的动作之一:
1. 摧毁一个路障(如果还有的话);
2. 部署他的 $$$k_i$$$ 攻击之一;
3. 跳过一个回合。
总伤害是轮流选择发动攻击的战士所造成伤害的总和。战士们可以对龙造成的最大总伤害是多少?
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$) — 战士的数量和路障的初始数量。
然后是每个战士的攻击描述。第 $$$i$$$ 描述由三行组成。
第一行包含一个整数 $$$k_i$$$ ($$$1 \le k_i \le m + 1$$$) — 第 $$$i$$$ 个战士知道的攻击次数。
第二行包含 $$$k_i$$$ 整数 $$$a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) - 每次攻击的伤害。
第三行包含 $$$k_i$$$ 整数 $$$b_{i,1}, b_{i,2}, \dots, b_{i,k_i}$$$ ($$$0 \le b_{i,j} \le m$$$) - 每次攻击所需的路障数量。第 $$$i$$$ 个战士的 $$$b_{i,j}$$$ 是两两不同的。攻击按照路障要求的升序排列,因此 $$$b_{i,1} < b_{i,2} < \dots < b_{i,k_i}$$$。
所有战士的 $$$k_i$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
打印一个整数——战士可以对龙造成的最大总伤害。
示例
输入 #1
2 4 1 2 4 2 10 5 3 4
输出 #1
10
输入 #2
3 3 1 1 0 1 20 2 1 100 3
输出 #2
100
输入 #3
2 1 2 10 10 0 1 2 30 20 0 1
输出 #3
30
注意
在第一个示例中,最佳选择如下:
- 战士 $$$1$$$ 摧毁了一个路障,现在还剩下 $$$3$$$ 路障;
- 战士$$$2$$$部署了他的第一次攻击(他可以这样做,因为$$$b_{1,1}=3$$$,这是当前的路障数量)。
总伤害为 $$$10$$$。
如果第一个战士使用了他的攻击或跳过了他的回合,那么第二个战士将只能部署他的第二次攻击。因此,总伤害将为 $$$2+5=7$$$ 或 $$$5$$$。
在第二个示例中,第一个战士跳过他的移动,第二个战士跳过他的移动,第三个战士部署他唯一的攻击。
在第三个示例中,两个等效选项是:
- 双方战士都部署了第二次攻击;
- 第一个战士摧毁了一个路障,第二个战士部署了他的第一次攻击。
两个选项都会产生 $$$30$$$ 总伤害。