Рассмотрим массив $A$ длины $N$. Вы планируете выполнить несколько запросов: для отрезка $[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$). Запрос на поиск максимального элемента в массиве на отрезке от $A_i$ до $A_j$ включительно должен быть выполнен ровно $Q_{i,j}$ раз.

После этого во входных данных описываются возможные значения $A_i$ для каждого $i$ от $1$ до $N$. Описание для $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