Transport chemikálií

Zadání

Quido s Hugem odvážejí na lodi chemikálie z ostrovního skladu. Chemikálie jsou uskladněny v barelech a v každém barelu je jiný druh chemikálie. Některé dvojice chemikálií nesmějí být z bezpečnostních důvodů skladovány spolu v jedné budově, těmto dvojicím se říká kritické dvojice. Za běžných okolností se na lodi nesmí převážet žádná kritická dvojice. Naštěstí Hugo má licenci bezpečnostního inspektora a pravidla EU říkají, že pokud je na lodi přítomen bezpečnostní inspektor, může loď převážet celkem až D kritických dvojic. Parametr D se vždy určuje podle typu lodi, charakteru chemikálií, ročního období atd.

Za všech okolností ale platí další pravidlo, které říká, že nikdy, ani v přítomnosti bezpečnostního inspektora, nesmí loď převážet takovou trojici chemikálií, v níž je každá dvojice kritická.

Každý barel ma svou určenou známou cenu a Quido s Hugem chtějí při dodržení uvedených pravidel odvézt ze skladu náklad s maximalní cenou. Předpokládáme, že pojedou jen jednou. Chemikálie zůstanou ve svých barelech, žádná další manipulace s nimi se nepředpokládá.

Obrázek 1. Schémata a), b), c) odpovídají řešením příkladů 1, 2, 3, níže. Ceny barelů jsou napsány na světlém pozadí, čísla barelů jsou napsána na tmavém pozadí. Kritické dvojice jsou vyznačeny přerušovanými čarami mezi příslušnými barely. Barely, ktere jsou odváženy lodí, jsou zvýrazněny a též jsou zvýrazněny kritické dvojice převážených barelů. Hodnoty parametru D jsou postupně 3, 0, 2 ve schématech a), b), c).

Úloha

Je dána cena každého barelu s chemikálií a seznam kritických dvojic chemikálií. Určete maximální celkovou cenu za barely, které lze odvézt při jedné cestě lodí za podmínek popsaných výše.

Vstup

První řádek obsahuje tři celá čísla N, M, D oddělená mezerou. N představuje počet barelů ve skladu, M představuje počet kritických dvojic chemikálií ve skladu a D je počet povolených kritických dvojic na lodi za přítomnosti bezpečnostního inspektora. Na druhém řádku je uveden seznam cen jednotlivých barelů v pořadí podle rostoucích čísel barelů. Předpokládáme, že jednotlivé barely jsou očíslovány 0, 1, …, N−1. Dalších M řádků obsahuje seznam kritických dvojic chemikálií. Každá dvojice je uvedena na jednom řádku, každá chemikálie je identifikována číslem barelu, v němž je uskladněna. Všechny hodnoty na každém řádku jsou odděleny mezerou.
Platí 1 ≤ N ≤ 30, 0 ≤ D ≤ M. Ceny barelů jsou kladná celá čísla nejvýše rovná 10⁷.

Výstup

Výstup obsahuje jeden textový řádek s celým číslem udávajícím maximální celkovou cenu za barely, které lze odvézt při jedné cestě lodí za dodržení podmínek popsaných v textu úlohy.

Příklady

Příklad 1

Vstup

7 12 3
5 9 7 10 8 6 1
0 1
0 3
0 2
1 3
1 4
2 3
2 5
3 4
3 5
3 6
4 6
5 6

Výstup

Příklad 2

Vstup

7 7 0
1 2 1 4 5 4 2
0 1
1 2
2 3
3 4
4 5
5 6
6 0

Výstup

Příklad 3

Vstup

12 21 2
10 20 30 40 50 60 120 110 100 90 80 70
0 1
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
10 11
0 6
1 7
2 8
3 9
4 10
5 11
6 1
1 8
8 3
3 10
10 5

Výstup

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data