gather

Gather

h2. Date de intrare

Fisierul de intrare $gather.in$ contine pe prima linie trei numere naturale {$K$}, {$N$}, {$M$}. Pe urmatoarele {$K$} linii se afla cate un numar reprezentand celulele in care se afla initial detinutii. In continuare vor urma {$M$} linii fiecare continand cate patru numere naturale $A$ $B$ $C$ $D$ cu urmatoare semnificatie: intre celulele $A$ si $B$ se afla un coridor de lungime $C$ pe care nu pot merge mai mult de $D$ detinuti.

Fisierul de intrare $gather.in$ contine pe prima linie trei numere naturale {$K$}, {$N$}, {$M$}. Pe urmatoarele {$K$} linii se afla cate un numar reprezentand celulele in care se afla initial detinutii. In continuare vor urma {$M$} linii fiecare continand cate patru numere naturale $A$ $B$ $C$ $D$ cu urmatoare semnificatie: intre celulele $A$ si $B$ se afla un coridor de lungime $C$ pe care nu pot merge mai mult de $D$ detinuti({*exceptandu-l pe Gigel*}).

h2. Date de iesire

* $1 ≤ N ≤ 750$
* $1 ≤ K ≤ 15$
* $1 ≤ M ≤ 1250$

* $C$ si $D$ se vor incadra pe 32 de biti pentru fiecare muchie
* Rezultatul se va incadra pe 32 de biti
* Nu vor exista mai multi detinuti in aceeasi celula
* Gigel poate trece prin celule cu prizonieri fara a le spune de planul sau in acest moment, urmand sa ii viziteze din nou mai tarziu
* Va exista mereu solutie

h2. Exemplu

2 4 25 1
3 4 100 2
3 1 10 2

| 400

| 100

|
h3. Explicatie
Gigel merge din celula $1$ in celula $2$ parcurgand o distanta de {$50$}. Aici ii spune detinutului $2$ de planul sau.

Gigel merge apoi impreuna cu detinutul $2$ in celula $3$ parcurgand impreuna distanta {$2*75$}.
Gigel merge apoi impreuna cu detinutul $2$ in celula $4$ parcurgand impreuna distanta {$2*100$}. Aici este informat si detinutul $2$ de plan.

Gigel merge apoi impreuna cu detinutul $2$ in celula $4$ parcurgand impreuna distanta {$2*25$}. Aici este informat si detinutul $1$ de plan.

== include(page="template/taskfooter" task_id="gather") ==

2494