← 返回题目列表

AtCoder · arc056_d

D. 鲑鱼跳蚤

中文机器翻译题面 查看原题

問題文

你在一家古怪的酒吧。在这个酒吧里,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