“Timp de milenii întregi, omenirea a continuat explorarea și colonizarea galaxiei noastre, stabilindu-și supremația asupra a sute de mii de sisteme solare care formează în prezent arhicunoscuta Federație Galactică.”

Colonizarea timpurie a Constelației Taurului, desfășurată începând cu anii 8700, a marcat un important salt în evoluția civilizație umane, prin construirea primelor Sfere Dyson – megastructuri colosale ce înglobează stele întregi pentru a exploata la maximum plasma emanată de acestea și oferind, practic, rezerve inepuizabile de energie necesară pentru atingerea vitezei warp în zborurile prin hiperspațiu, pentru proiectarea găurilor de vierme și pentru terraformarea planetelor colonizate.

O astfel de Sferă Dyson a fost construită în jurul gigantei roșii Alfa Tauri/Aldebaran de către Federație, structura fiind dispusă sub forma unei configurații de n terminale energetice, unde terminalul 1 este punctul de absorbție plasat în proximitatea suprafeței stelare, iar terminalul n este punctul de emergență, prin care se realizează colectarea fluxului de plasmă.

Cele n terminale sunt conectate între ele la început prin m conductoare plasmatice unidirecționale, fiecare având o capacitate specifică calculată în terajouli – w. Analizând rata de pulsație a stelei, se constată că este posibilă o maximizare suplimentară a fluxului energetic captat de Sfera Dyson prin substituirea a k conductoare cu o serie de condensatoare fotonice, care să stocheze și să ejecteze controlat plasma, aceste dispozitive având de asemenea un debit maxim măsurat în ordinul terajoulilor.

Pentru ușurința substituției s-a decis să fie alese primele k conductoare din cele m existente, acestea având inițial capacitatea nulă. În plus, pentru a crește fiabilitatea structurii, se vor efectua q astfel de substituții, pentru fiecare fiind specificate în ordine debitele maxime ale condensatoarelor curente.

Cerința

Scopul vostru este să calculați pentru fiecare substituție fluxul maxim energetic asimilat de Sfera Dyson, plasând condensatoarele în locurile specificate și ajutând astfel Federația Galactică să se extindă permanent în sistemul solar Aldebaran. Succes!

Date de intrare

Pe prima linie a fișierului de intrare dyson.in se află valorile n – numărul de terminale, m – numărul total de conductoare, k – numărul de conductoare care trebuie înlocuite cu condensatoare și q – numărul de substituții realizate.

Pe următoarele m linii se află triplete de forma u v w cu proprietatea că există un conductor de plasmă ce unește terminalul u cu terminalul v, având capacitatea de w terajouli(pentru primele k, w este nul).

Ultimele q linii conțin șiruri de k valori ce desemnează în ordine debitele maxime pentru condensatoarele folosite în substituția curentă.

Date de ieșire

În fișierul de ieșire dyson.out se vor afișa q valori, fiecare pe câte o linie separată, desemnând fluxul maxim asimilat de Sfera Dyson pentru substituția curentă.

Restricții și precizări

• 1 ≤ n ≤ 6000, 1 ≤ m ≤ 10000, 1 ≤ k ≤ min(7, m);
• 1 ≤ u, v ≤ n, 1 ≤ w ≤ 10000, 1 ≤ q ≤ 10000;
• Pentru fiecare teste se garantează existența unui flux energetic între terminalele 1 și n.
• Primele k conductoare din cele m au inițial capacitatea vidă.

Exemplu:

dyson.in

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

dyson.out

0
1
5
6
7

Explicație

Imaginea de mai sus reprezintă primele două substituții de la stânga la dreapta. Vârfurile reprezintă terminalele, iar arcele sunt conductoarele, fiecare având atașată o pereche flux/capacitate. Conductoarele care trebuie substituite sunt colorate în roșu.

După cum se observă, pentru prima rețea fluxul maxim de la terminalul 1 la terminalul 4 este egal cu 0, iar pentru cea de-a doua este 1.