tl3 | confectii

Într-o sală sunt $N$ elevi numerotați de la $1$ la $N$. Aceștia pot confecționa fie obiecte roșii, fie obiecte albe.
Fiecare elev are o limită maximă de obiecte roșii și albe pe care le poate confecționa. Elevul cu numarul $i$ poate confecționa maxim $a_i$ obiecte roșii și maxim $b_i$ obiecte albe.
Dacă un elev confecționează mai multe obiecte roșii decât alt elev, acesta sigur confecționează și mai multe obiecte albe decât acel alt elev. Deci, dacă $a_i \geq a_j$ , atunci $b_i \geq b_j \ \forall \ i, j \in \{1, 2, \dots , N\}$.
Pentru a crește numărul de obiecte confecționate, elevii pot alege să formeze un grup. Doi elevi sunt de acord să facă parte din grup și să confecționeze împreună doar dacă diferența absolută dintre numerele lor este mai mică decât numărul elevilor din grup. De exemplu, elevii $1, 2, 3, 4$ pot forma un grup, dar elevii $1, 2, 3, 5$ nu pot. În plus, toți elevii din grup vor confecționa același număr de obiecte. Dacă un elev din grup confecționează $5$ obiecte în total, atunci toți elevii vor confecționa fiecare $5$ obiecte în total.

Cerință

Determinați numărul maxim de obiecte ce pot fi confecționate de un grup de elevi, dacă elevii decid să confecționeze împreună, în grup.

Date de intrare

Pe prima linie a fișierului de intrare confectii.in se află numărul natural $N$, ce semnifică numărul de elevi. Pe următoarele $N$ linii, se află două numere, $a_i$ și $b_i$, reprezentând numărul maxim de obiecte roșii, respectiv albe, pe care le poate confecționa elevul cu numărul $i$.

Date de ieșire

Pe prima linie a fișierului de ieșire confectii.out scrieți un singur număr natural, numărul maxim de obiecte ce pot fi confecționate.

Restricții și precizări

• $1 \leq N \leq 10^6$
• $1 \leq a_i, \ b_i \leq 10^9$
• Pentru 40% din teste: $b_i = 0 \ \forall \ i \ \in \{1, 2, \dots, N\}$

Exemplu

confectii.in

5
10 12
30 35
50 59
20 18
40 37

confectii.out

152

Explicație

Elevii $2, 3, 4, 5$ confecționează fiecare câte $20$ de obiecte roșii și $18$ obiecte albe.