26299번 - Glomazna Gužva 다국어

Zagreb je u posljednje vrijeme postao popularna destinacija za održavanje raznih diplomatskih susreta. Predsjednici, premijeri, patrijarsi, kraljevi, vojvode i generali naprosto uživaju vozeći se pustim zagrebačkim ulicama pod policijskom pratnjom.

Zagreb možemo (pojednostavljeno) predstaviti pravokutnom mrežom ulica, gdje se svako križanje nalazi na cjelobrojnim koordinatama. Da biste (direktno) proputovali od križanja A na koordinatama (x_A, y_A) do križanja B na koordinatama (x_B, y_B), morate se provozati kroz točno |x_A − x_B| + |y_A − y_B| blokova. U normalnim uvjetima (bez gužve), putovanje kroz jedan blok traje točno 10 minuta.

Međutim, svaki diplomatski posjet rezultira glomaznom gužvom na nekom pravokutnom području grada. Sve ceste koje se nalaze strogo unutar tog područja jednako su zahvaćene gužvom, a njihova prohodnost (vrijeme prolaska bloka) ovisi o važnosti tog specifičnog diplomatskog posjeta. Dakako, više se diplomatskih posjeta može događati istovremeno, ali niti jedna dva pravokutna područja nikad se ne sijeku niti diraju.

Za dano stanje u prometu u gradu Zagrebu, odredite najkraće vrijeme potrebno da se proputuje od zadanog početnog do zadanog završnog križanja.

U prvom su retku četiri cijela broja x_A, y_A, x_B i y_B koji predstavljaju koordinate početnog i završnog križanja, te su po apsolutnoj vrijednosti manji ili jednaki 10⁸.

U drugom se retku nalazi prirodan broj n (0 ≤ n ≤ 1 000) koji predstavlja broj diplomatskih posjeta koji se trenutno odvijaju u Zagrebu.

Idućih n redaka opisuju glomazne gužve, i to tako da i-ti redak sadrži brojeve x_1,i, y_1,i, x_2,i, y_2,i i t_i. Prva četiri broja predstavljaju koordinate donjeg-lijevog i gornjeg-desnog ruba gužvom zahvaćenog područja (x_1,i < x_2,i, y_1,i < y_2,i), dok broj t_i (10 < t_i ≤ 10⁸) predstavlja vrijeme potrebno da se proputuje jednim blokom unutar tog područja.

Pravokutna područja iz ulaza neće se sijeći niti dirati, a lokacije početnog i završnog križanja bit će različite i neće se nalaziti unutar niti na rubu nekog pravokutnog područja.

U jedinom se retku nalazi prirodan broj koji označava najkraće vrijeme potrebno da se proputuje od križanja A do križanja B.

Pojašnjenje prvog probnog primjera: primjer odgovara skici iz zadatka.