考虑一个长度为 $N$ 的数组 $A$。你计划进行若干次查询：对于数组的一个区间 $[i, j]$，找出该区间内的最大值。对于索引 $i$ 和 $j$ 的查询将执行 $Q_{i,j}$ 次。

但数组尚未给出，你需要现在构建它。

对于每个 $i$ 从 $1$ 到 $N$，你可以从 $K_i$ 个不同的值 $V_{i,j}$ 中选择一个作为 $A_i$ 的值，选择这些值的相应成本为 $C_{i,j}$。

在所有查询之后，你的得分将是所有计划进行的区间查询结果之和，减去选择值 $A_i$ 的成本。求出可能达到的最大得分。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 300$)。

接下来 $N$ 行。第 $i$ 行包含从 $Q_{i,i}$ 到 $Q_{i,N}$ 的整数 ($0 \le Q_{i,j} \le 999$)。表示在数组中索引 $i$ 到 $j$（包含边界）之间的最大值查询将恰好执行 $Q_{i,j}$ 次。

此后，输入描述了每个 $i$（从 $1$ 到 $N$）对应的 $A_i$ 的可能取值。第 $i$ 个描述格式如下：

• 第一行包含一个正整数 $K_i$：$A_i$ 的可能取值数量。
• 接下来的 $K_i$ 行，每行包含两个整数 $V_{i,j}$ 和 $C_{i,j}$：分别表示一个可能的值及其对应的选择成本 ($0 \le V_{i,j} \le 10^8$, $0 \le C_{i,j} \le 10^{13}$)。

保证 $K_i$ 的总和不超过 $3 \cdot 10^5$。

输出格式

输出一个整数：最大可能的得分。

样例

样例输入 1

5
1 0 2 2 0
0 2 2 0
2 2 2
1 2
0
2
0 27
1 19
2
7 25
1 1
2
8 7
4 18
2
8 7
4 4
2
0 25
4 26

样例输出 1

78

样例输入 2

2
1 1
1
2
1 100
2 50
1
1 100

样例输出 2

-145