Xét một mảng $A$ có độ dài $N$. Bạn đang lên kế hoạch thực hiện một số truy vấn: với một đoạn $[i, j]$ của mảng, tìm giá trị lớn nhất trên đoạn đó. Truy vấn cho các chỉ số $i$ và $j$ sẽ được thực hiện $Q_{i,j}$ lần.

Tuy nhiên, mảng này chưa được cho trước và bạn sẽ phải xây dựng nó ngay bây giờ.

Với mỗi $i$ từ $1$ đến $N$, bạn có thể chọn một trong $K_i$ giá trị khác nhau $V_{i,j}$ làm giá trị của $A_i$, và chi phí tương ứng để chọn các giá trị này là $C_{i,j}$.

Sau tất cả các truy vấn, điểm số của bạn sẽ là tổng kết quả của tất cả các truy vấn đoạn mà bạn đã lên kế hoạch, trừ đi chi phí chọn các giá trị $A_i$. Hãy tìm điểm số tối đa có thể đạt được.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $N$ ($1 \le N \le 300$).

Tiếp theo là $N$ dòng. Dòng thứ $i$ chứa các số nguyên từ $Q_{i,i}$ đến $Q_{i,N}$ ($0 \le Q_{i,j} \le 999$). Truy vấn tìm phần tử lớn nhất trong mảng giữa $A_i$ và $A_j$ (bao gồm cả hai đầu) sẽ được thực hiện đúng $Q_{i,j}$ lần.

Sau đó, dữ liệu vào mô tả các giá trị có thể có của $A_i$ cho mỗi $i$ từ $1$ đến $N$. Mô tả thứ $i$ có định dạng sau:

• Dòng đầu tiên chứa một số nguyên dương $K_i$: số lượng giá trị có thể có cho $A_i$.
• Mỗi dòng trong $K_i$ dòng tiếp theo chứa hai số nguyên $V_{i,j}$ và $C_{i,j}$: một giá trị có thể có và chi phí để chọn giá trị đó ($0 \le V_{i,j} \le 10^8$, $0 \le C_{i,j} \le 10^{13}$).

Đảm bảo rằng tổng của $K_i$ không vượt quá $3 \cdot 10^5$.

Dữ liệu ra

In ra một số nguyên duy nhất: điểm số tối đa có thể đạt được.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

78

Dữ liệu vào 2

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

Dữ liệu ra 2

-145