Harc az ezüstért

Piet Hein egy holland tengerész volt a Holland Egyesült Tartományok és Spanyolország között dúló nyolcvanéves háború idején. Leghíresebb győzelme a Zilvervloot („Ezüstflotta”) elfoglalása volt Kubánál 1628-ban, amikor is elfogott számos spanyol hajót, amelyek ezüstöt szállítottak az amerikai spanyol gyarmatokról Spanyolországba. Ennek a híres tengeri ütközetnek a részletei homályosak, ezért az alábbi leírás tartalmazhat néhány történelmi pontatlanságot.

Az Ezüstflotta ezüstpénzeket szállító hajókból állt. Piet Hein alapstratégiája egyszerű volt: elvontatni pár hajót a flottából, megszerezve a tartalmukat.

Hogy megakadályozzák a hollandokat a tervük végrehajtásában, a spanyolok hatalmas vasláncokkal összekötötték a flottájuk összes hajóját. A flotta minden hajója legalább egy másik hajóhoz volt rögzítve; bármely két hajó legfeljebb egy lánccal volt összekötve; és a spanyolok gondoskodtak róla, hogy a láncok ne keresztezzék egymást, nehogy összegubancolódjanak. Végeredményben a hajók és az őket összekötő láncok egy összefüggő, síkbeli gráfot alkottak.

A spanyolok megelőző intézkedései azonban csak rontottak a helyzetükön. Tapasztalt hajóstisztként Piet Hein tudta, hogy egy hajócsoportot akkor a legegyszerűbb elvontatni, ha a csoport bármely két hajója össze van egymással láncolva. Az ilyen csoportokat lánccsoportoknak hívta.

Piet Hein utasította az embereit, hogy vontassák el a legnagyobb zsákmányt tartalmazó lánccsoport összes hajóját, miután elválaszották őket a spanyol flotta többi hajójától néhány egészen pontos ágyúlövéssel. Az egy lánccsoportból származó teljes zsákmány a lánccsoportot alkotó hajókon tárolt ezüstpénzek összessége.

1. ábra: A második példa bemenet illusztrációja. Az Ezüstflotta gráfként reprezentálva. A pontok a flotta hajóit, a vonalak pedig a hajókat összekötő láncokat jelölik. Az ábrán szaggatott vonalakkal összekötött hajók alkotják azt a lánccsoportot, amelyik a legnagyobb értékben tartalmaz ezüstpénzeket. Ebben az esetben Piet Hein 4500 ezüstpénzt zsákmányol a flottától.

Az Ezüstflotta leírásának ismeretében határozd meg a legnagyobb zsákmányt ígérő lánccsoport értékét (azaz a lánccsoportot alkotó hajókon található ezüstpénzek darabszámát)!

A bemenet specifikációja

Minden tesztesetet az alábbi sorok írnak le:

• Egy két egész számot, v-t (2 ≤ v ≤ 450) és e-t (1 ≤ e ≤ 900) tartalmazó sor, ahol v a flotta hajóinak száma, e pedig a láncok száma.
• Ezután v darab sor, amelyek az S₁, S₂, …, S_v értékeket, az i-edik hajó által szállított ezüstpénzek számát adják meg (1 ≤ i ≤ v). Az S_i-k pozitív egész számok, melyekre 100 ≤ S_i ≤ 6000.
• Ezután minden lánchoz egy-egy sor, amelyben két egész szám, c_start és c_end, a lánc által összekötött két hajó sorszáma szerepel (1 ≤ c_start < c_end ≤ v).

Minden flotta egy összefüggő, síkbeli gráfot alkot.

A kimenet specifikációja

Minden tesztesetre egyetlen sort kell a kimenetre írni, amely pozitív egész számként a Piet Hein flottája által megszerzett ezüstpénzek számát tartalmazza.

Példa bemenet

1. 4 6
2. 100
3. 5000
4. 1000
5. 2000
6. 1 2
7. 1 3
8. 1 4
9. 2 3
10. 2 4
11. 3 4
12. 6 8
13. 1500
14. 1000
15. 100
16. 2000
17. 500
18. 300
19. 1 2
20. 1 3
21. 1 4
22. 2 4
23. 3 5
24. 4 5
25. 4 6
26. 5 6

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 8100
2. 4500

letöltés szöveges állományként