Hide

Problem D
Påskris

Nu när påsken nalkas har Anna-Lisa bestämt sig för att gå och köpa påskris för att liva upp hemmet lite. När hon kommer till affären inser hon dock ett stort problem – affären har slut på påsar, det är påskris! Anna-Lena älskar påskris, så egentligen vill hon köpa alla, men nu kan hon inte frakta hem dem så hon får göra det bästa av situationen och bara köpa ett. Som tur är visar det sig att en del påskris har blivit intrasslade i varann, så om hon tar ett påskris kommer hon nu att få med sig alla påskris som det sitter ihop med (även de som det inte sitter ihop direkt med). Det är också så att alla påskris är olika fina och Anna-Lisa vill att hennes påskris ska ha så stor sammanlagd finhet som möjligt. Hur fint kan Anna-Lisas påskris maximalt bli?

Indata

Första raden innehåller två heltal N och M (N,M100000), antalet påskris som finns och antalet intrasslade par av påskris. De följande N raderna innehåller ett tal ai (1ai100), som beskriver hur fint det i:te påskriset är. Påskrisen är indexerade från 0 till N1. De följande M raderna innehåller två tal bj och cj som betyder att påskrisen med de indexen är intrasslade i varandra.

Utdata

Skriv ut ett tal, den maximala finheten som Anna-Lisas påskris kan ha.

Poängsättning

Din lösning kommer att testas på fyra olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Begränsningar

1

25

N100,M200

2

25

N5000,M20000

3

25

N20000,M100000

4

25

Inga ytterligare begränsningar

Förklaring

I exempelfallet är påskrisen hoptrasslade till två grupper. Den ena har risen med index 0 och 4, medan det andra har indexen 1,2,3 och 5. Summan av finheten i den första gruppen är 12, vilket är större än den andra gruppens 11. Alltså är den maximala finheten 12.

Sample Input 1 Sample Output 1
6 5
7
1
1
6
5
3
1 2
2 3
1 5
0 4
1 3
12
Hide

Please log in to submit a solution to this problem

Log in