Cerința

Ne aflăm în primăvara anului 1941, în regiunea Libiei numită Tobruk. Zona constituie cea mai importantă sursă de combustibil fosil din Africa de Nord pentru armata nazistă, fiind dispusă sub forma unei configurații de n câmpuri petroliere interconectate prin m rute terestre bidirecționale.

Pentru a dobândi controlul decisiv asupra regiunii strategice din Nordul Africii, trupele aliate L.R.D.G. (Long Range Desert Group) desfășoară o amplă operațiune de sabotaj împotriva diviziei Afrika Korps a armatei naziste, cunoscută sub numele de cod “Furtună la Tobruk”. Aliații dispun de exact s trupe de commando, fiecare dintre acestea fiind caracterizată de o anumită putere de asalt a și o cantitate finită de combustibil f; în plus, fiecare echipă dintre cele s se află la începutul operațiunii pe un anumit câmp petrolier dintre cele n (x) și are asociat un cost operațional p.

Trupele L.R.D.G. îți desfășoară atacul asupra unei serii de b baze militare naziste, fiecare dintre acestea fiind plasată într-un anumit câmp petrolier y, și având o anumită putere defensivă împotriva asalturilor aliaților d, precum și o rezervă finită de petrol g, care este automat refăcută în urma oricărui atac asupra sa.

Se cunoaște că o echipă de asalt poate ataca o bază inamică dacă și numai dacă cantitatea de combustibil de care dispune este mai mare sau egală cu distanța dintre poziția sa inițială și cea a bazei și puterea sa de asalt este mai mare sau egală cu puterea defensivă a bazei naziste. În cazul în care o trupă de commando reușește să distrugă sistemul defensiv al unei baze militare inamice, profitul generat de aceasta se calculează ca diferența dintre cantitatea de petrol deținută de bază și costul operațional al echipei de asalt.

Scopul misiunii aliaților este de a maximiza profitul global al operațiunii, prin preselectarea acelor trupe de commando care pot aduce rezerve maxime de petrol, suferind costuri operaționale minime. Însă, având în vedere analizele strategice realizate de aliați asupra misiunii, s-a prestabilit un număr de k dependențe, nu neapărat reciproce, între echipele de asalt, care se definesc astfel: dacă echipa u depinde de echipa v, atunci u nu va putea interveni în operațiunea de asalt decât dacă v este deja angajată în aceasta.

Pentru a ajuta trupele aliate să înfrângă rezistența naziștilor din Africa de Nord, vi se solicită să determinați profitul maximal al operațiunii, care să respecte toate restricțiile și specificațiile anterioare. Succes!

Date de intrare

Pe prima linie a fișierului de intrare tobruk.in se află valorile n și m (numărul de câmpuri petroliere din regiunea Tobruk, respectiv numărul de rute bidirecționale dintre acestea), urmate de exact m linii pe care se află perechi de forma c d cu proprietatea că există rută de acces între câmpul c și d.

În continuare se vor citi s, b și k, care constituie numărul de echipe de asalt, numărul de baze inamice, respectiv numărul de dependențe dintre trupe. Pe următoarele s linii se află caracteristicile pentru fiecare echipă sub forma x a f p, cu proprietatea că trupa curentă se află inițial la poziția x, dispune de puterea de asalt a, cantitatea de combustibil f și generează costul operațional p. Pe următoarele b linii se află caracteristicile pentru fiecare bază nazistă sub forma y d g cu proprietatea că baza curentă se află în poziția y, dispune de o putere defensivă d și are în dotare o rezervă de g barili de petrol. Pe următoarele k linii se află dispuse perechi de forma u v ce definesc dependențele stabilite între echipele de commando.

Date de ieșire

În fișierul de ieșire tobruk.out se va afișa o singură valoare ce reprezintă profitul maximal total al misiunii.

Restricții și precizări

• 1 <= n <= 100, 0 <= m <= 10.000, 1 <= c, d <= n;
• 1 <= s, b <= 100.000, 0 <= k <= 100.000;
• 1 <= u, v <= s, 1 <= x, y <= n, 0 <= a, f, p, d, g <= 1.000.000.000;
• Pot exista multiple rute bidirecționale între aceleași două câmpuri petroliere (inclusiv între un câmp și el însuși)!
• Distanța dintre două câmpuri petroliere este egală cu numărul minim de rute ce compun lanțul elementar care le conectează.
• Rezerva de petrol a unei baze atacate de aliați se reface automat după asalt, astfel că o aceeași bază poate fi atacată de multiple echipe.
• Rezultatul final, cât și valorile intermediare, sunt reprezentabile pe tipul de dată întreg de 64 de biți.

Exemplu:

tobruk.in

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

tobruk.out

2

Explicație

Strategia optimă de atac implică angajarea în operațiune a echipelor 1, 2, și 4, care vor desfășura asalturi asupra bazelor 1, 1, respectiv 2.