Ron Weasley dorește să-l ajute pe Harry Potter să construiască baghete magice. Hermione este plecată, așa că Ron trebuie să se descurce singur și știm cum ies vrăjile lui… Din acest motiv, are nevoie de ajutorul tău. Ron are crengi de soc de diferite lungimi și o riglă magică marcată, în dreptul fiecărui centimetru, cu numere naturale consecutive, începând cu 1. Un număr natural aflat pe rigla magică este fermecat dacă are proprietatea că este obținut prin ridicarea la puterea a doua a unui număr prim. Puterea unei crengi este egală cu numărul de numere fermecate acoperite de aceasta pe rigla magică. Pentru a crea o baghetă, Ron așază crengile pe riglă cu capătul din stânga al fiecărei crengi exact în dreptul numărului natural marcat pe riglă. În cazul în care două sau mai multe crengi se suprapun sau se ating se formează o singură baghetă. Dacă două sau mai multe crengi de soc așezate pe riglă nu se suprapun și nu se ating, se obțin baghete diferite. De exemplu, dacă Ron așază pe riglă o creangă de soc de lungime 7 centimetri, cu capătul din stânga la poziția marcată cu numărul 4, creanga va avea puterea 2 (fiindcă va acoperi numerele fermecate 4 și 9). Dacă mai așază pe riglă o altă creangă de lungime 2 centimetri, cu capătul din stânga la poziția marcată cu numărul 11, această creangă va avea puterea 0 și cele două crengi așezate vor forma împreună o baghetă pentru că se ating. Dacă mai așază pe riglă o altă creangă, de lungime 1 centimetru, cu capătul din stânga la poziția marcată cu numărul 14, această creangă va avea puterea 0 și va forma singură o baghetă pentru că nu se suprapune și nu se atinge de alte crengi.

Cerința

Scrieţi un program care, cunoscând numărul de crengi de soc și pentru fiecare dintre acestea poziția pe riglă la care se plasează capătul din stânga și lungimea crengii măsurată în centimetri, rezolvă următoarele două cerințe:

1) să se determine puterea cea mai mare pe care o are una dintre crengile folosite de Ron;
2) să se determine numărul de baghete magice realizate de Ron.

Date de intrare

Fișierul de intrare ron.in conține pe prima linie numerele c și n reprezentând cerința care trebuie rezolvată (1 sau 2), respectiv numărul de crengi de soc. Pe următoarele n linii sunt descrise crengile de soc, câte o creangă pe o linie, sub forma a două numere naturale poz și lg reprezentând, în această ordine, numărul natural aflat pe rigla magică în dreptul căruia a fost așezat capătul din stânga al crengii, respectiv lungimea în centimetri a acesteia. Numerele scrise pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire ron.out va conține o singură linie pe care va fi scris un număr natural reprezentând rezultatul la cerința c din fişierul de intrare.

Restricții și precizări

• 1 ≤ n ≤ 50.000
• 1 ≤ poz, lg ≤ 1.000.000.000
• Pentru 22 de puncte, C=1; n ≤ 1000; poz, lg ≤ 100.000
• Pentru 20 de puncte, C=1 și nu există restricții suplimentare.
• Pentru 25 de puncte, C=2; n ≤ 1000; poz, lg ≤ 100.000
• Pentru 33 de puncte, C=2 și nu există restricții suplimentare.

Exemplul 1:

ron.in

1 4
19 9
6 1
9 17
8 1

ron.out

2

Explicație

Prima creangă are puterea 1 (acoperă numărul fermecat 25), a doua creangă are puterea 0, a treia creangă are puterea 2 (acoperă numerele fermecate 9 și 25), iar a patra creangă are puterea 0. Pentru primul exemplu (c=1), puterea maximă a uneia dintre crengile folosite de Ron este 2.

Exemplul 2:

ron.in

2 4
19 9
6 1
9 17
8 1

ron.out

2

Explicație

Pentru al doilea exemplu (c=2), se obțin două baghete: prima, a treia și a patra creangă realizează împreună o baghetă pentru că se suprapun sau se ating. A doua creangă realizează singură o baghetă.