lego

Crina și Rareș pornesc în călătoria imaginară spre Deva și pentru aceasta fiecare își construiește câte un autocar din piese de lego. Pentru a nu crea blocaje în trafic, intrarea autocarelor în oraș este gestionată de un semnal pe care este scris un număr natural $S$. Astfel, fiecare autocar ce ajunge în dreptul semnalului, trebuie să aștepte, un număr de minute egal cu valoarea absolută a diferenței dintre S și numărul de identificare al autocarului său.

Cei doi copii își împart în mod egal piesele de lego pe care sunt scrise cifre (fiecare copil are același număr de piese ca și celălalt, pentru fiecare cifră în parte), cu care formează numerele de identificare ale celor două autocare. Crina aranjează una lângă alta toate piesele sale și formează cifră cu cifră, numărul $N_1$ de identificare al autocarului ei iar Rareș procedează la fel și formează numărul $N_2$ pentru autocarul său. Pentru ca cele două numere să nu fie identice, copiii stabilesc ca $N_1$ să fie strict mai mic decât numărul $S$ al semnalului iar numărul $N_2$ strict mai mare decât $S$. În cazul în care vreunul din cele două numere nu poate fi construit din piesele împărțite, atunci autocarul respectiv va avea identificatorul $0$ și va aștepta la semnal până trece celălalt autocar.

Cerinţe:

1. Determinați numerele $N_1$ și $N_2$ astfel încât, autocarul fiecărui copil să aștepte cât mai puține minute la semnal.
2. Știind că autocarele celor doi copii au ajuns în același timp în fața semnalului, determinați numărul minim de minute de așteptare ale autocarului care va trece primul de semnal.

Date de intrare

Fișierul de intrare lego.in conține:

• pe prima linie numărul natural $C$ ce poate avea valorile $1$ sau $2$, reprezentând numărul cerinței;
• pe cea de-a doua linie un singur număr natural $S$ cu semnificația din enunț;
• pe următoarele linii câte două numere naturale $n_i$ și $c_i$, despărțite prin câte un spațiu, cu următoarea semnificație: $n_i$ reprezintă numărul pieselor cu cifra $c_i$, pe care le are fiecare copil.

Date de ieșire

Pentru $C = 1$, fișierul de ieșire lego.out va conține pe prima linie două numere naturale $N_1$ și $N_2$, în această ordine, despărțite printr-un spațiu, determinate conform cerinței $1$.
Pentru $C = 2$, fișierul de ieșire lego.out va conține pe prima linie, un singur număr natural determinat conform cerinței $2$.

Restricții și precizări

• $1 \leq S \leq 10^{18}$;
• fiecare copil are cel mult $19$ piese;
• cifrele $c_i$ sunt distincte;
• pentru rezolvarea corectă a cerinței $1$ se acordă $60$ de puncte iar pentru rezolvarea corectă a cerinței $2$ se acordă $40$ de puncte.

Exemplul 1

lego.in

1
153
1 7
3 4

lego.out

0 4447

Explicație

Se rezolvă doar cerința $1$.
Pe semnal este scris numărul $153$. Fiecare copil are $3$ piese cu cifra $4$ și o piesă cu cifra $7$. Crina nu poate construi cu aceste piese un număr mai mic ca $153$, de aceea autocarul său este identificat cu numărul $0$. Rareș construiește numărul $N_2 = 4 \ 447$.

Exemplul 2

lego.in

2
42
1 3
1 5

lego.out

7

Explicație

Se rezolvă doar cerința $2$.
Pe semnal este scris numărul $42$. Fiecare copil are o cifră de $3$ și o cifră de $5$. Crina construiește numărul $N_1 = 35$ și așteaptă la semnal $42 - 35 = 7$ minute. Rareș construiește numărul $N_2 = 53$ și așteaptă la semnal $53 - 42 = 11$ minute. Numărul minim al minutelor de așteptare este $7$.