Мика је успешно сакупио 256 поена на квалификацијама и тако се квалификовао за Окружно такмичење. Као и сваком другом програмеру, Мики је ово једна од ретких прилика да стекне нове пријатеље. Зато је одлучио да сврати до врачаре Миљане која ће га упутити у то како се стварају пријатељства на Окружном такмичењу.

На Окружно такмичење је позвано \(N\) ученика, нумерисаних бројевима \(1, 2, …, N\). Како нису сви ученици подједнако дружељубиви, за сваког ученика могуће је дефинисати колико воли дружење. Тако ћемо претпоставити да ученик \(i\) има одређену дружељубивост \(A_i\). Међу такмичарима постоји \(M\) парова познаника, при чему свака два ученика која се познају могу бити пријатељи или непријатељи. Срећу такмичара \(i\) можемо дефинисати као производ његове дружељубивости и разлике броја његових пријатеља и непријатеља. На пример, ако такмичар има дружељубивост \(2\), има три пријатеља и једног непријатеља, његова срећа износи \(2*(3-1)=4\). При томе, неки такмичари могу имати негативну дружељубивост, у ком случају су срећнији када имају више непријатеља, а мање пријатеља. Укупну срећу целог такмичења дефинишемо као збир срећа свих такмичара.

Врачара је Малом Мики открила који су парови учесника познаници, али му није рекла да ли су ти парови пријатељи или непријатељи. Сада Мику интересује која је највећа могућа укупна срећа целог такмичења? Како је Мика веома заузет припремама за Окружно такмичење, замолио вас је да му помогнете.

Опис улаза

У првој линији улаза налазе се бројеви \(N\) и \(M\). Затим следи \(N\) линија, тако да се у \((i+1)\)-ој линији налази дружељубивост \(i\)-тог такмичара, \(A_i\). Затим следи још \(M\) линија које описују познанства међу такмичарима, тако да се у \((N+1+i)\)-ом реду налази пар познаника \(X_i, Y_i\).

Опис излаза

У прву и једину линију излаза треба исписати највећу могућу срећу читавог такмичења.

Ограничења

• \(1 \leq N \leq 100\ 000\)
• \(1 \leq M \leq 100\ 000\)
• $ A_i$
• $ 1X_i, Y_iN$
• \(X_i\neq Y_i\), за \(i\in [1, M]\)
• \(\{X_i, Y_i\}\neq \{X_j, Y_j\}\), за \(i, j\in [1, M], i\neq j\)

Тест примери су подељени у 3 дисјунктнe групe:

• У тест примерима вредним \(20\) поена важи \(N, M \leq 10\).
• У тест примерима вредним \(20\) поена важи \(A_i=1\) за све \(i\in [1, N]\).
• У тест примерима вредним \(60\) поена нема додатних органичења.

Примери

Пример 1

Улаз

3 2
1
1
1
1 2
2 3

Излаз

4

Објашњење

Сви такмичари су подједнако дружељубиви, па се максимална срећа постиже када су сви такмичари пријатељи. Тада је срећа такмичара \(1\) једнака \(1\), срећа такмичара \(2\) је \(2\) и срећа такмичара \(3\) је \(1\). Дакле, највећа могућа укупна срећа такмичења је \(4\).

Пример 2

Улаз

3 2
2
-5
5
1 2
2 3

Излаз

3

Објашњење

Максимална срећа постиже се када су сви познаници непријатељи. Тада срећа износи \(2\cdot(0-1)+(-5)\cdot(0-2)+5\cdot(0-1) = 3\).