Problem Description

You have come to a peculiar bar. This bar has $ N $ types of drinks, and you are initially given $ N $ glasses. The $ i $-th glass corresponds to the $ i $-th drink and will only be filled with the $ i $-th drink. Each drink has a tastiness value $ w_i $. Initially, all glasses are empty.

Each drink is replenished at certain times. That is, if the $ i $-th glass is empty at time $ t_{i,j} (1 ≦ j ≦ M_i) $, the $ i $-th drink will be poured into the $ i $-th glass.

You can drink all the contents of all glasses at any odd time. Drinking only some of the drinks is prohibited. Write a program to find the maximum sum of tastiness values of the drinks you have consumed. Note that the tastiness of the same drink consumed multiple times is counted repeatedly.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the sum of tastiness values in one line.

Sample Input and Output

Sample Input #1

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

Sample Output #1

6

Sample Input #2

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

Sample Output #2

3

Sample Input #3

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

Sample Output #3

18

Sample Input #4

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

Sample Output #4

0

Notes/Hints

Constraints

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

Partial Points

• If you correctly solve all test cases where $ t_{i,j} ≦ 1,000 $ and $ N ≦ 1,000 $, you will be awarded 30 points as partial credit.

Sample Explanation 1

Drink all the contents of the glasses at times $ 9 $ and $ 11 $. At time $ 9 $, all three drinks are poured, giving a tastiness of $ 2+5-6=1 $. At time $ 11 $, only the second drink is poured, giving a tastiness of $ 5 $. The total is $ 6 $.

见题面 Input 部分

见题面 Output 部分