Supposons que tu sois Li Hua.

En tant qu'excellent étudiant en sciences humaines, tu as récemment étudié l'électricité.

Tu disposes d'une infinité de charges ponctuelles de charge $+e$ avec une énergie cinétique initiale suffisamment grande. Tu dois en faire passer une partie dans une machine et en faire ressortir une quantité égale. L'objectif est de maximiser la somme des énergies cinétiques des charges après leur passage dans la machine.

La machine peut être vue comme un ensemble de $n$ nœuds, où le potentiel électrique du $i$-ième nœud est $h_i \,\mathrm{V}$.

Le $i$-ième nœud possède $p_i$ conduits permettant d'introduire une charge ponctuelle dans ce nœud. Chaque conduit ne peut être utilisé qu'une seule fois au cours du processus. L'introduction d'une charge ponctuelle via le $j$-ième conduit nécessite de fournir un travail contre les forces extérieures égal à $a_{i,j} \,\mathrm{eV}$.

Le $i$-ième nœud possède $q_i$ conduits permettant d'extraire une charge ponctuelle de ce nœud. Chaque conduit ne peut être utilisé qu'une seule fois au cours du processus. L'extraction d'une charge ponctuelle via le $j$-ième conduit nécessite de fournir un travail contre les forces extérieures égal à $b_{i,j} \,\mathrm{eV}$.

La machine contient $m$ conduits unidirectionnels reliant les nœuds. Le $i$-ième conduit relie $u_i$ et $v_i$, ce qui signifie qu'une charge ponctuelle peut être transportée de $u_i$ vers $v_i$ (sans limite de nombre d'utilisations). On suppose que les autres forces à l'intérieur de la machine ne travaillent pas, et que tu peux contrôler la trajectoire de chaque charge ponctuelle à travers la machine.

Chaque charge ponctuelle introduite doit être extraite, et les autres forces à l'intérieur de la machine ne doivent pas travailler. Ainsi, si une charge ponctuelle entre par le $i$-ième conduit du nœud $x$ et sort par le $j$-ième conduit du nœud $y$, le travail effectué par la machine sur cette charge est $(h_x - h_y - a_{x,i} - b_{y,j}) \,\mathrm{eV}$.

Calcule la somme maximale de l'augmentation de l'énergie cinétique (unité : $\mathrm{eV}$).

Entrée

La première ligne contient deux entiers positifs $n, m$.

La ligne suivante contient $n$ entiers, où le $i$-ième nombre est $h_i$.

Les $m$ lignes suivantes contiennent chacune deux entiers positifs $u_i, v_i$ décrivant un conduit unidirectionnel.

Les $n$ lignes suivantes contiennent chacune un entier positif $p_i$, suivi de $p_i$ entiers non négatifs représentant $a_{i,j}$.

Les $n$ lignes suivantes contiennent chacune un entier positif $q_i$, suivi de $q_i$ entiers non négatifs représentant $b_{i,j}$.

Sortie

Affiche un entier non négatif représentant la réponse.

Exemples

Entrée 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

Sortie 1

6

Contraintes

Pour $100\%$ des données, on garantit $1 \le u_i, v_i \le n$ et $0 \le m, p_i, q_i, a_{i,j}, b_{i,j}, h_i$. Les valeurs $a_{i,j}, b_{i,j}, h_i$ sont générées aléatoirement de manière uniforme dans leurs plages respectives, et les autres valeurs sont générées de manière aléatoire sans cibler spécifiquement des algorithmes comme SPFA.

| :---: | :---: | :---: | :---: | :---: | :---: | :---: | | Numéro du test | $n \le$ | $m \le$ | $p_i, q_i \le$ | $a_{i,j}, b_{i,j} <$ | $h_i <$ | Propriété spéciale | | $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$ | | | |

Propriété spéciale A : $|u_i - v_i| = 1$

Propriété spéciale B : $m = n - 1, u_i < v_i, v_i = i + 1$

Propriété spéciale C : $\min \{u_i, v_i\} \le 4$

Fichiers fournis

En raison de la taille importante des entrées et sorties de ce problème, un modèle d'E/S est fourni.

Ce fichier compressé contient cinq exemples et un modèle d'E/S.