photo

Photo

== include(page="template/taskheader" task_id="photo") ==

Poveste şi cerinţă...

Vi se oferă o fotografie a liniei de orizont a oraşului Târgu-Mureş realizată în timpul nopţii. Unele camere încă mai au lumina aprinsă. Se ştie că toate clădirile se modelează cu dreptunghiuri de arie cel mult $A$. Găsiţi numărul minim de clădiri ce reconstituie fotografia.
 
Mai exact, se dă un număr întreg $A$ şi $N$ puncte la coordonate numere întregi $(x, y)$. Cerinţa constă în a găsi un număr minim de dreptunghiuri, cu una din laturi pe axa _Ox_ iar aria cel mult egală cu $A$, care acoperă toate punctele. Dreptunghiurile se pot suprapune.

h2. Date de intrare

Fişierul de intrare $photo.in$ ...

Prima linie a fişierului de intrare $photo.in$ conţine două numere întregi $N$ şi $A$, separate printr-un singur spaţiu. Următoarele $N$ linii conţin două numere întregi $x$ şi $y$, reprezentând coordonatele fiecărui punct.

h2. Date de ieşire

În fişierul de ieşire $photo.out$ ...

Fişierul de ieşire $photo.out$ conţine o singură linie cu numărul minim de dreptunghiuri.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100$
* $1 ≤ A ≤ 200 000$
* Fiecare punct are $0 ≤ x ≤ 3 000 000$ şi $1 ≤ y ≤ A$.
* Pentru $30%$ din teste $1 ≤ N ≤ 18$.

h2. Exemplu

table(example). |_. photo.in |_. photo.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. photo.in |_. photo.out |_. Explicaţie |
| 6 4
2 1
4 1
5 1
5 4
7 1
6 4
| 3
| !problema/photo/?photo.png!
|

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

8472