Transport chemik�li�

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� 107.

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��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
30

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
10

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
480

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