Предположим, вы — Ли Хуа.
Как выдающийся студент гуманитарного профиля, вы недавно изучали электричество.
У вас есть $\infty$ точечных зарядов величиной $+e$ с достаточно большой кинетической энергией. Вам нужно пропустить часть из них через машину и получить на выходе такое же количество зарядов. Максимизируйте суммарную кинетическую энергию зарядов после работы машины.
Машину можно представить как $n$ узлов, электрический потенциал $i$-го узла равен $h_i \,\mathrm{V}$.
В $i$-м узле есть $p_i$ каналов, через которые можно подать точечный заряд в этот узел. Через каждый канал за всё время работы можно пропустить не более одного заряда. При подаче заряда через $j$-й канал совершается работа против внешних сил в размере $a_{i,j} \,\mathrm{eV}$.
В $i$-м узле есть $q_i$ каналов, через которые можно вывести точечный заряд из этого узла. Через каждый канал за всё время работы можно вывести не более одного заряда. При выводе заряда через $j$-й канал совершается работа против внешних сил в размере $b_{i,j} \,\mathrm{eV}$.
Внутри машины есть $m$ однонаправленных каналов. $i$-й канал соединяет $u_i$ и $v_i$, что означает возможность перемещения заряда из $u_i$ в $v_i$ (количество использований не ограничено). Предполагается, что другие силы внутри машины работу не совершают, и вы можете управлять траекторией движения каждого заряда через машину.
Каждый поданный в машину заряд должен быть выведен из неё, при этом другие силы внутри машины работу не совершают. То есть, если заряд входит через $i$-й канал узла $x$ и выходит через $j$-й канал узла $y$, работа, совершаемая машиной над ним, составляет $(h_x - h_y - a_{x,i} - b_{y,j}) \,\mathrm{eV}$.
Найдите максимальное суммарное увеличение кинетической энергии (в единицах $\mathrm{eV}$).
Входные данные
Первая строка содержит два целых положительных числа $n, m$.
Следующая строка содержит $n$ целых чисел, $i$-е число — $h_i$.
Следующие $m$ строк содержат по два целых положительных числа $u_i, v_i$, описывающих однонаправленный канал.
Следующие $n$ строк: $i$-я строка начинается с целого положительного числа $p_i$, за которым следуют $p_i$ неотрицательных целых чисел, $j$-е из которых обозначает $a_{i,j}$.
Следующие $n$ строк: $i$-я строка начинается с целого положительного числа $q_i$, за которым следуют $q_i$ неотрицательных целых чисел, $j$-е из которых обозначает $b_{i,j}$.
Выходные данные
Выведите одно неотрицательное целое число — ответ на задачу.
Примеры
Входные данные 1
3 4 3 9 2 1 1 2 3 3 3 3 2 1 2 1 0 1 2 1 1 1 2 1 1
Выходные данные 1
6
Ограничения
Для $100\%$ данных гарантируется $1 \le u_i, v_i \le n$, $0 \le m, p_i, q_i, a_{i,j}, b_{i,j}, h_i$. Значения $a_{i,j}, b_{i,j}, h_i$ распределены равномерно случайно в соответствующих диапазонах, остальные параметры сгенерированы случайным образом и не направлены на блокировку алгоритмов типа SPFA.
| Номер теста | $n \le$ | $m \le$ | $p_i, q_i \le$ | $a_{i,j}, b_{i,j} <$ | $h_i <$ | Особое свойство |
|---|---|---|---|---|---|---|
| $1, 2$ | $50$ | $200$ | $10$ | $10$ | $30$ | |
| $3, 4$ | $70$ | $300$ | $100$ | $100$ | $2000$ | |
| $5, 6, 7, 8$ | $100$ | $500$ | $200$ | $200$ | $10^4$ | |
| $9, 10$ | $2000$ | $5000$ | $500$ | $10^4$ | $10^6$ | A |
| $11, 12, 13, 14$ | $n-1$ | B | ||||
| $15, 16, 17, 18$ | $10^4$ | C | ||||
| $19, 20, 21$ | $700$ | $5000$ | $1000$ | $10^6$ | $10^8$ | |
| $22, 23, 24, 25$ | $2000$ | $2\times 10^4$ | $2000$ |
Особое свойство A: $|u_i - v_i| = 1$
Особое свойство B: $m = n - 1, u_i < v_i, v_i = i + 1$
Особое свойство C: $\min \{u_i, v_i\} \le 4$
Примечание
В связи с большим объемом входных и выходных данных для этой задачи предоставляется дополнительный шаблон ввода-вывода.
Архив содержит пять примеров и шаблон ввода-вывода.