问题描述

你来到了一家奇特的酒吧。这家酒吧提供了 $N$ 种饮料，你会被给予 $N$ 杯酒。第 $i$ 杯酒对应第 $i$ 种饮料，只会倒入第 $i$ 种饮料。每种饮料都有一个对应的美味度 $w_i$。最开始，所有的杯子都是空的。

每种饮料都会在一些固定的时间进行补充。也就是说，如果第 $i$ 杯酒在时间 $t_{i,j}(1≦j≦M_i)$ 为空杯的话，那么第 $i$ 杯酒将会被倒入第 $i$ 种饮料。

你可以选择在任意一个奇数时间点，将所有的酒杯中的饮料喝完。但是禁止只喝其中的一部分饮料。请编写一个程序来求出喝掉的饮料美味度总和的最大值。注意，即使喝了同样的饮料多次，美味度也会计算重复。

约束条件

• $1 ≦ N ≦ 5\*10^5$
• $2 ≦ t_{i,j} ≦ 10^6$
• $t_{i,j} < t_{i,j+1}$
• $t_{i,j}$ 是偶数
• $Σ M_i ≦ 5\*10^5$
• $1 ≦ M_i$
• $\-10^9 ≦ w_i ≦ 10^9$

部分得分

• 如果满足 $t_{i,j} ≦ 1,000$ 和 $N ≦ 1,000$ 的所有测试用例，则可以获得 30 分的部分得分。

输入

输入以以下格式从标准输入中给出。

$N$ $w_1$ ... $w_N$ $M_1$ $t_{1,1}$ ... $t_{1,M_1}$ : $M_N$ $t_{N,1}$ ... $t_{N,M_N}$

输出

在第一行上输出美味度总和。

输入示例1

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

输出示例1

6

在时间点 $9$ 和 $11$ 将酒杯中的饮料喝完。在时间点 $9$，由于三种饮料都已经倒入了酒杯，所以可以得到美味度为 $2+5-6=1$。在时间点 $11$，只有第二种饮料被倒入，所以可以得到美味度为 $5$。总共得到的美味度为 $6$。

输入示例2

3
2 5 -6
2 2 8
2 4 10
2 4 10

输出示例2

3

输入示例3

3
3 5 -4
2 2 8
4 4 6 10 12
4 2 4 8 10

输出示例3

18

输入示例4

3
-2 -2 -2
2 2 8
4 4 6 10 12
4 2 4 8 10

输出示例4

0