考慮一個長度為 $N$ 的陣列 $A$。你計畫進行數次查詢：對於陣列的一個區間 $[i, j]$，找出該區間內的最大值。針對索引 $i$ 和 $j$ 的查詢將會執行 $Q_{i,j}$ 次。

然而，陣列尚未給定，你需要現在就建構它。

對於每個從 $1$ 到 $N$ 的 $i$，你可以從 $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$)。針對陣列中包含 $A_i$ 到 $A_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

78

範例 2

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

-145