Aspersoare

Time limit: 0.5s Memory limit: 8MB Input: Output:

După o lungă perioadă de analiză, cu ajutorul vostru, Andrei s-a hotărât cu cine se va împrieteni de pe strada sa. Din păcate, acea persoană nu a vrut să se împrietenească cu amicul nostru. De supărare, Andrei și-a schimbat reședința și și-a cumpărat o casă cu grădină.
Andrei vrea să aibă grijă foarte mare de grădina sa, așa că a decis să cumpere aspersoare pentru a-și uda toată grădina. El vrea să acopere toată suprafața grădinii, care are forma unui dreptunghi cu lungimea LL și lățimea WW. Cum Andrei nu se pricepe la montarea aspersoarelor, a chemat ajutoare, ca să le monteze, și pe voi, ca să îl ajutați cu deciziile.

Aveți la dispoziție NN aspersoare. Despre fiecare cunoașteți următoarele informații: distanța față de capătul stânga al grădinii la care poate fi montat aspersorul și raza de acoperire a aspersorului. Fiecare aspersor va fi poziționat în centrul grădinii ca și lățime.

Cerință

Andrei vă roagă acum pe voi să alegeți un număr minim de aspersoare, căci nu vrea să dea prea mulți bani, astfel încât să acopere toată suprafața grădinii. Dacă nu este posibilă o alegere a aspersoarelor astfel încât să se acopere întreaga suprafață a grădinii, să se afișeze mesajul Imposibil.

Date de intrare

Pe prima linie se găsesc trei numere naturale, NN, LL și WW cu semnificația din enunț. Pe următoarele NN linii se vor găsi câte două numere naturale, dd și rr, care reprezintă distanța față de capătul din stânga al grădinii pentru aspersorul respectiv, și raza de acoperire a acestuia.

Date de ieșire

Pe prima linie se va găsi un singur număr natural, ce reprezintă numărul minim de aspersoare ce trebuie selectate pentru a acoperi întreaga suprafață a grădinii, sau mesajul Imposibil, în cazul în care nu este posibilă acoperirea.

Restricții și precizări

  • 1N100 0001 \leq N \leq 100 \ 000
  • 1L100 0001 \leq L \leq 100 \ 000
  • 1W10 0001 \leq W \leq 10 \ 000
  • 0d100 0000 \leq d \leq 100 \ 000
  • 0r100 0000 \leq r\leq 100 \ 000
  • Pentru 2121 de puncte: 1N81 \leq N \leq 8 și 1L,W1001 \leq L,W \leq 100.
  • Pentru restul de 7979 de puncte, nu există restricții suplimentare.

Exemplul 1

stdin

8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4

stdout

6

Explicație


După cum se poate vedea pe desen, se pot selecta următoarele aspersoare pentru a acoperi toată grădina: (1,2)(1,2), (5,3)(5,3), (7,2)(7,2), (10,2)(10,2), (13,3)(13,3), (19,4)(19,4).

Exemplul 2

stdin

1 99 7
64 13

stdout

Imposibil

Explicație


Se vede în imagine că nu se poate acoperi întreaga suprafață.

Log in or sign up to be able to send submissions!