Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Mika sikeresen összegyűjtötte a szükséges 256 pontot, és jogot szerzett a körzeti versenyen való részvételre. Mint általában a programozókra, Mikára is érvényes, hogy ez a verseny egyike azoknak a ritka alkalmaknak, amikor barátokat szerezhet. Úgy döntött, ismét felkeresi Miljanát, a jósnőt, akitől majd megtudja, hogyan köttetnek barátságok a körzeti versenyen.

A Körzeti versenyre \(N\) tanuló kap meghívást. Sorszámaik \(1, 2, …, N\). A tanulók nem egyformán barátkozó kedvűek, ám mindegyikükre definiálható az, hogy mennyire szeret barátkozni. Feltételezzük, hogy az \(i\) - edik tanuló barátkozó kedve \(A_i\). A versenyzők között \(M\) ismerős pár található. Minden ismerős tanuló párra vonatkozik, hogy lehetnek barátok vagy ellenségek. Az \(i\) - edik tanuló boldogságát megkapjuk, ha összeszorozzuk az adott tanuló barátkozó kedvét a barátai és ellenségei számának különbségével. Például, ha egy tanuló barátkozó kedve 2, és van három barátja és egy ellensége, akkor az ő boldogsága \(2*(3-1)=4\). Egyes tanulóknak a barátkozó kedve lehet negatív érték. Ebben az esetben ezek a tanulók akkor boldogabbak, ha több az ellenségük, mint a barátjuk. Az egész verseny összboldogsága egyenlő az összes versenyző boldogságának összegével.

A jósnő Mikának azt elárulta ugyan, hogy kik az ismerős párok a versenyzők között, ám azt nem mondta meg, mely párok barátok, és melyek ellenségek. Mika azt szeretné megtudni, mekkora a verseny lehető legnagyobb összboldogsága. Ő maga rendkívül elfoglalt, mert készül a körzeti versenyre, ezért titeket kért meg arra, segítsetek ebben neki.

Bemenet

A bemenet első sorában az \(N\) és \(M\) számok állnak. Ezután \(N\) sor következik úgy, hogy az \((i+1)\)-edik sorban az \(i\)-edik versenyző barátkozó kedve, az \(A_i\) érték áll. Ezután még \(M\) sor következik, amelyek a versenyzők közötti ismeretséget írja le úgy, hogy az \((N+1+i)\)-edik sorban az \(X_i, Y_i\) ismerős pár található.

Kimenet

A kimenet első és egyetlen sorában kiíratni az egész verseny lehető legnagyobb boldogságát!

Korlátozások

A tesztpéldák 3 független csoportba oszthatók:

Példák

1. példa

Bemenet

3 2
1
1
1
1 2
2 3

Kimenet

4

Magyarázat

Minden tanuló ugyanannyira barátkozó kedvű, így a legnagyobb boldogság akkor érhető el, ha mindannyian barátok. Ekkor az \(1\)-es számú versenyző boldogsága \(1\), a \(2\) -es számú versenyző boldogsága \(2\) és a \(3\) -as számú versenyző boldogsága pedig \(1\). Tehát a verseny legnagyobb boldogsága \(4\).

2. példa

Bemenet

3 2
2
-5
5
1 2
2 3

Kimenet

3

Magyarázat

A boldogság akkor lesz legnagyobb, ha minden ismerős ellenség. Ekkor a boldogság értéke:

\(2\cdot(0-1)+(-5)\cdot(0-2)+5\cdot(0-1) = 3\).