Simulare oni7 | patrate

Anei îi place mult să se joace la calculator. Acum are un nou joc în care $n$ blocuri orizontale formate din pătrate de latură $1$, cad pe verticală. Suprafaţa de joc se reprezintă ca un tablou cu $L \ (L > n)$ linii numerotate de la $1$ la $L$ şi $C$ coloane, numerotate de la $1$ la $C$, ca în figură. Tabloul este constituit din $L \times C$ celule pătratice de latură $1$. Fiecare bloc este format din unul sau mai multe pătrate alăturate, situate doar pe direcţia orizontală. Blocurile sunt numerotate de la $1$ la $n$ şi cad pe rând, în această ordine, întotdeauna de pe linia $L$, la intervale diferite de timp şi au aceeaşi viteză de cădere. Fiecare pătrat din bloc cade până la linia cu cel mai mic număr de ordine care este neocupată de un alt pătrat al unui bloc căzut anterior. Dacă nu întâlneşte un alt pătrat oprit anterior, atunci se opreşte pe linia $1$. Aşadar, pătratele din acelaşi bloc pot să se oprească pe linii diferite.

După ce pătratele tuturor blocurilor au ajuns pe poziţiile finale, Ana trebuie să determine o zonă continuă de lungime maximă $L_{max}$, măsurată pe orizontală, cu proprietatea că înălţimea fiecărei coloane a sa este cel puţin $h$.

Cerinţă

Determinaţi indicele coloanei de început $c_i$ şi lungimea $L_{max}$ măsurată pe orizontală a zonei continue formată din pătrate cu proprietatea că fiecare coloană de pătrate a zonei are înălţimea cel puţin $h$.

Date de intrare

Fişierul de intrare patrate.in conţine:

• pe prima linie două număre naturale $n$ şi $h$, separate printr-un spaţiu, cu semnificaţia din enunţ.
• fiecare din următoarele $n$ linii conţine câte două numere naturale $c$ şi $p$, separate printr-un spaţiu. Valorile $c$ şi $p$ de pe linia $i + 1$ reprezintă coloana corespunzătoare primului pătrat al capătului din stânga al blocului $i$, respectiv numărul de pătrate din bloc.

Date de ieşire

Fişierul de ieşire patrate.out conţine pe o singură linie numerele naturale $c_i$ şi $L_{max}$, separate printr-un spaţiu. Dacă există mai multe soluţii, atunci se afişează aceea pentru care $c_i$ este minim.

Restricţii şi precizări

• $1 \leq h \lt n \leq 1 \ 000$
• $2 \leq c + p \leq 1 \ 000 \ 000 \ 000$
• Problema admite soluţie pentru toate datele de intrare.

Exemplu

patrate.in

4 2
3 2
2 6
7 3
6 3

patrate.out

6 3

Explicaţie

În figură, numerotarea pătratelor identifică blocurile din care acestea fac parte. Zona de pătrate de lungime maximă incepe la coloana $6$ şi are lungimea $3$.