==Include(page="template/taskheader" task_id="demolish")==
==Include(page="template/raw")==
Demolish
Patratel a strans profit serios din afacerile cu struti si acum doreste sa se extinda. Cu banii pe care ii are intentioneaza sa isi construiasca o ferma in regiune. Regiunea este de forma dreptunghiulara si are M kilometri lungime si N kilometri latime, iar ferma trebuie sa fie si ea dreptunghiulara si sa aiba laturile paralele cu ale regiunii. In regiune sunt insa construite alte F ferme ale unor oameni la fel de bogati ca si Patratel, ferme tot dreptunghiulare si tot cu laturile paralele cu ale regiunii. Patratel este om pretentios ( ca si strutii sai, de altfel ), si doreste o ferma de DX kilometri lungime si DY kilometri latime. Constructia unei astfel de ferme nu este intotdeauna posibila pentru ca depinde de asezarea celorlalte F ferme. Fiecare ferma are un cost de demolare ( costul pe care Patratel trebuie sa il plateasca sa demoleze ferma respectiva ). El doreste sa isi plaseze ferma proprie in regiune astfel incat suma costurilor de demolare ale fermelor intersectate de ferma sa fie minima.
Doua ferme se intersecteaza daca si numai daca un punct de pe laturile primei ferme se gaseste strict in interiorul celei de a doua ferme ( adica ele nu se intersecteaza daca se ating doar laturile ).
h2. Cerinta
Sa se determina costul minim pe care il plateste Patratel pentru a-si construi ferma.
h2. Date de Intrare
Prima linie a fisierului demolish.in contine cinci numere naturale M, N, F, DX si DY ( in aceasta ordine ), cu semnificatia din enunt. Fiecare din urmatoarele F linii contine tot cate cinci numere, (x1 y1 x2 y2 C), unde (x1 y1) reprezinta coordonatele coltului stanga-jos ale unei ferme din regiune, (x2 y2) coordonatele dreapta-sus ale aceleiasi ferme, iar C costul de demolare al fermei respective. Pentru un astfel de set avem intotdeauna 0 <= x1 < x2 <= M, 0 <= y1 < y2 <= N si 0 <= C <= 200 000.
h2. Date de Iesire
Prima linie a fisierului demolish.out contine COST, costul minim cerut. A doua linie contine patru numere intregi separate de cate un spatiu, (x1 y1 x2 y2), reprezentand pozitionarea fermei in regiune: (x1 y1) - coordonatele coltului stanga-jos si (x2 y2) - coordonatele dreapta-sus a fermei construite de Patratel pentru a obtine costul minim COST. Daca sunt mai multe posibilitati de amplasare, se va afisa cea care are x1 minim, iar daca si in acest caz sunt mai multe posibilitati, se va afisa cea care are y1 minim.
h2. Restrictii si precizari
o 4 < M, N < 500 001
o 0 < DX < M + 1, 0 < DY < N + 1
o F < 30 001
o Evident, fermele deja construite in regiune nu se intersecteaza
o Oricare doua ferme nu se intersecteaza daca se ating doar laturile
o Pot exista doua ferme din cele F care au acelasi cost de demolare
h2. Exemplu
demolish.in demolish.out
12 10 6 7 8 14
2 3 5 8 3 1 0 8 8
5 7 7 9 7
8 4 12 8 22
7 1 9 2 4
0 0 1 2 10
1 9 2 10 6
==Include(page="template/taskheader" task_id="demolish")==
Patratel a strans profit serios din afacerile cu struti si acum doreste sa se extinda. Cu banii pe care ii are intentioneaza sa isi construiasca o ferma in regiune. Regiunea este de forma dreptunghiulara si are $M$ kilometri lungime si $N$ kilometri latime, iar ferma trebuie sa fie si ea dreptunghiulara si sa aiba laturile paralele cu ale regiunii. In regiune sunt insa construite alte $F$ ferme ale unor oameni la fel de bogati ca si Patratel, ferme tot dreptunghiulare si tot cu laturile paralele cu ale regiunii. Patratel este om pretentios ( ca si strutii sai, de altfel ), si doreste o ferma de $DX$ kilometri lungime si $DY$ kilometri latime. Constructia unei astfel de ferme nu este intotdeauna posibila pentru ca depinde de asezarea celorlalte $F$ ferme. Fiecare ferma are un cost de demolare ( costul pe care Patratel trebuie sa il plateasca sa demoleze ferma respectiva ). El doreste sa isi plaseze ferma proprie in regiune astfel incat suma costurilor de demolare ale fermelor intersectate de ferma sa fie minima.
Doua ferme se intersecteaza daca si numai daca un punct de pe laturile primei ferme se gaseste strict in interiorul celei de a doua ferme ( adica ele nu se intersecteaza daca se ating doar laturile ).
h2. Cerinta
Sa se determina costul minim pe care il plateste Patratel pentru a-si construi ferma.
h2. Date de Intrare
Prima linie a fisierului $demolish.in$ contine cinci numere naturale $M, N, F, DX$ si $DY$ ( in aceasta ordine ), cu semnificatia din enunt. Fiecare din urmatoarele $F$ linii contine tot cate cinci numere, $(x1 y1 x2 y2 C)$, unde $(x1 y1)$ reprezinta coordonatele coltului stanga-jos ale unei ferme din regiune, $(x2 y2)$ coordonatele dreapta-sus ale aceleiasi ferme, iar C costul de demolare al fermei respective. Pentru un astfel de set avem intotdeauna $0 ≤ x1 < x2 ≤ M, 0 ≤ y1 < y2 ≤ N$ si $0 ≤ C ≤ 200 000$.
h2. Date de Iesire
Prima linie a fisierului demolish.out contine $COST$, costul minim cerut. A doua linie contine patru numere intregi separate de cate un spatiu, $(x1 y1 x2 y2)$, reprezentand pozitionarea fermei in regiune: $(x1 y1)$ - coordonatele coltului stanga-jos si $(x2 y2)$ - coordonatele dreapta-sus a fermei construite de Patratel pentru a obtine costul minim $COST$. Daca sunt mai multe posibilitati de amplasare, se va afisa cea care are $x1$ minim, iar daca si in acest caz sunt mai multe posibilitati, se va afisa cea care are $y1$ minim.
h2. Restrictii si precizari
* $4 < M, N < 500 001$
* $0 < DX < M + 1, 0 < DY < N + 1$
* $F < 30 001$
* Evident, fermele deja construite in regiune nu se intersecteaza
* Oricare doua ferme nu se intersecteaza daca se ating doar laturile
* Pot exista doua ferme din cele $F$ care au acelasi cost de demolare
h2. Exemplu
table(example). |_. demolish.in |_. demolish.out |
| 12 10 6 7 8
2 3 5 8 3
5 7 7 9 7
8 4 12 8 22
7 1 9 2 4
0 0 1 2 10
1 9 2 10 6 | 14
1 0 8 8 |
h3. Explicatie
Costul minim se obtine daca ferma este dispusa conform coordonatelor (1 0 8 8), intersectand fermele 1, 2 si 4, care trebuiesc demolate. Suma costurilor tuturor demolarilor efectuate este de 3+7+4 = 14. O alta plasare posibila care duce tot la costul 14 este (1 1 8 9), dar aceasta nu duce la indeplinirea conditiei de minimalitate a coordonatelor.
==Include(page="template/taskfooter" task_id="demolish")==
Explicatie: Costul minim se obtine daca ferma este dispusa conform coordonatelor (1 0 8 8), intersectand fermele 1, 2 si 4, care trebuiesc demolate. Suma costurilor tuturor demolarilor efectuate este de 3+7+4 = 14. O alta plasare posibila care duce tot la costul 14 este (1 1 8 9), dar aceasta nu duce la indeplinirea conditiei de minimalitate a coordonatelor.
==Include(page="template/taskfooter" task_id="demolish")==
