Photo

photo

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.

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 paralelă cu axa _Ox_ iar aria cel mult egală cu $A$, care acoperă toate punctele. Dreptunghiurile se pot suprapune.

h2. Date de intrare

8472