Supongamos que eres Li Hua.
Como un excelente estudiante de humanidades, recientemente has aprendido sobre electricidad.
Tienes $\infty$ cargas puntuales con carga $+e$ y energía cinética suficientemente grande. Debes introducir una parte de ellas en una máquina y extraer la misma cantidad de cargas puntuales. Maximiza la suma de la energía cinética de las cargas después de que la máquina funcione.
La máquina puede verse como $n$ nodos, donde el potencial eléctrico del nodo $i$ es $h_i \,\mathrm{V}$.
El nodo $i$ tiene $p_i$ tuberías a través de las cuales se pueden introducir cargas puntuales. Durante todo el proceso, cada tubería puede admitir como máximo una carga puntual. La carga puntual introducida a través de la $j$-ésima tubería realiza un trabajo de $a_{i,j} \,\mathrm{eV}$ para vencer fuerzas externas.
El nodo $i$ tiene $q_i$ tuberías a través de las cuales se pueden extraer cargas puntuales. Durante todo el proceso, cada tubería puede extraer como máximo una carga puntual. La carga puntual extraída a través de la $j$-ésima tubería realiza un trabajo de $b_{i,j} \,\mathrm{eV}$ para vencer fuerzas externas.
La máquina tiene $m$ tuberías unidireccionales conectadas internamente. La $i$-ésima tubería conecta $u_i$ y $v_i$, lo que significa que una carga puntual puede ser transportada de $u_i$ a $v_i$ (sin límite de veces). Se asume que otras fuerzas dentro de la máquina no realizan trabajo, y puedes controlar la trayectoria de movimiento de cada carga puntual a través de la máquina.
Cada carga puntual introducida debe ser extraída, y otras fuerzas dentro de la máquina no realizan trabajo. Es decir, si una carga puntual entra por la $i$-ésima tubería del nodo $x$ y sale por la $j$-ésima tubería del nodo $y$, el trabajo realizado por la máquina sobre ella es $(h_x - h_y - a_{x,i} - b_{y,j}) \,\mathrm{eV}$.
Calcula la suma máxima del aumento de energía cinética (en unidades de $\mathrm{eV}$).
Entrada
La primera línea contiene dos enteros positivos $n, m$.
La siguiente línea contiene $n$ enteros, donde el $i$-ésimo número es $h_i$.
Las siguientes $m$ líneas contienen cada una dos enteros positivos $u_i, v_i$ que describen una tubería unidireccional.
Las siguientes $n$ líneas contienen, cada una, el primer entero positivo $p_i$, seguido de $p_i$ enteros no negativos, donde el $j$-ésimo representa $a_{i,j}$.
Las siguientes $n$ líneas contienen, cada una, el primer entero positivo $q_i$, seguido de $q_i$ enteros no negativos, donde el $j$-ésimo representa $b_{i,j}$.
Salida
Imprime un entero no negativo que represente la respuesta.
Ejemplos
Entrada 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
Salida 1
6
Entrada 2
(input data)
Salida 2
(output data)
Entrada 3
(input data)
Salida 3
(output data)
Entrada 4
(input data)
Salida 4
(output data)
Entrada 5
(input data)
Salida 5
(output data)
Restricciones
Para el $100\%$ de los datos, se garantiza que $1\le u_i,v_i\le n$ y $0\le m,p_i,q_i,a_{i,j},b_{i,j},h_i$. Donde $a_{i,j},b_{i,j},h_i$ se generan aleatoriamente con distribución uniforme dentro de sus rangos correspondientes, y el resto se genera de alguna manera aleatoria, sin estar diseñados específicamente para bloquear algoritmos como SPFA.
| Número de caso | $n\le$ | $m\le$ | $p_i,q_i\le$ | $a_{i,j},b_{i,j}<$ | $h_i<$ | Propiedad especial |
|---|---|---|---|---|---|---|
| $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$ |
Propiedad especial A: $|u_i-v_i|=1$
Propiedad especial B: $m=n-1, u_i < v_i, v_i=i+1$
Propiedad especial C: $\min \{u_i,v_i\} \le 4$
Archivos proporcionados
Debido a que la escala de entrada y salida de este problema es grande, se proporciona una plantilla de E/S adicional.
Este archivo comprimido contiene cinco ejemplos y una plantilla de E/S.