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*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ă Lmax, 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 ci şi lungimea Lmax 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 patrate2.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 patrate2.out conţine pe o singură linie numerele naturale ci şi Lmax, separate printr-un spaţiu. Dacă există mai multe soluţii, atunci se afişează aceea pentru care ci este minim.
Restricţii
1 ≤ h < n ≤ 1000
2 ≤ c + p ≤ 1000000000
Problema admite soluţie pentru toate datele de intrare.
Exemple
patrate2.in
patrate2.out
Explicaţii
4 2
3 2
2 6
7 3
6 3
6 3
Î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.
