長さ $N$ の配列 $A$ を考えます。あなたはいくつかのクエリを計画しています。配列の区間 $[i, j]$ に対して、その区間内の最大値を求めるというものです。インデックス $i$ と $j$ に対するクエリは $Q_{i,j}$ 回行われます。

しかし、配列はまだ与えられておらず、今からあなたが構築することになります。 $1$ から $N$ までの各 $i$ について、$A_i$ の値として $K_i$ 個の異なる値 $V_{i,j}$ の中から一つを選択でき、それぞれの値を選択するコストは $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}$ 回行われます。

その後、入力は $1$ から $N$ までの各 $i$ について、$A_i$ の取り得る値を記述します。$i$ 番目の記述は以下の形式です。

• 最初の行には正の整数 $K_i$ が含まれます：$A_i$ の取り得る値の数。
• 続く $K_i$ 行のそれぞれには、2つの整数 $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つ出力してください：最大スコア。

入出力例

入力 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