問題文
你在一家古怪的酒吧。在这个酒吧里,N有不同种类的饮料,你可以从 您将获得N眼镜。 第i块玻璃是 它对应于第i次饮料, 只会倒第i杯饮料。此外,每种饮料的味道都很鲜美。w_i已修复。最初,所有杯子都是空的。
每杯饮料都会在固定时间补充多次。 也就是说, 时间t_{i,j}(1≦j≦M_i)至 如果第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第 1 行,输出美味度之和。
入力例1
3 2 5 -6 1 2 2 4 10 2 4 8
出力例1
6
時刻9和11喝掉玻璃杯里的所有饮料。 时间9所以,3因为饮料都是倒出来的,所以味道鲜美。 您将得到2+5-6=1。 时间 只倒了11所以,2饮料,所以味道鲜美。 您将得到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