Înaintea vacanței de Paște, la școală, s-au primit cadouri pentru elevii din clasa a V-a. Sunt N cutii cu bomboane și se cunoaște numărul de bomboane din fiecare cutie. Numărul de cutii de bomboane primite de fiecare copil trebuie să fie același. Acest număr trebuie să fie mai mare sau egal cu 2. Cutiile cu bomboane vor fi oferite în ordinea primirii, primele cutii primului copil, următoarele cutii celui de al doilea copil, următoarele cutii celui de al treilea copil etc.

Se dorește să se împartă cutiile cu bomboane unui număr cât mai mare de copii. De asemenea, mai este o condiție: să se împartă copiilor toate cutiile, sau cel mult una dintre cutii să rămână neoferită. În cazul că se ia decizia ca o cutie să nu fie dată copiilor, aceasta se păstrează de către doamna dirigintă pentru a-i servi pe aceștia la întoarcerea la școală, iar restul cutiilor cu bomboane se pun pe catedră în ordinea în care au fost primite, fără ca elevii să știe despre cea păstrată. Alegerea acestei cutii trebuie făcută astfel încât numărul total de bomboane care se împart să fie cât mai mare.

Cerința

1) Care este numărul maxim de copii care vor primi cadouri?
2) Care este numărul maxim posibil de bomboane pe care le poate primi un copil în condițiile descrise mai sus?
Pentru ambele cerințe trebuie determinat și numărul de bomboane din cutia care eventual se păstrează.

Date de intrare

Fișierul de intrare cadouri.in conține pe prima linie un număr C, indicând cerința. Pe linia a doua se află un număr N, reprezentând numărul de cutii de bomboane primite la școală. Pe linia a treia se află N numere, separate prin câte un spațiu, reprezentând numărul de bomboane din fiecare cutie, în ordinea în care acestea au fost primite.

Date de ieșire

Fișierul de ieșire cadouri.out va conține două numere naturale, separate printr-un singur spațiu liber, cu următoarea semnificație:
pentru C = 1 prima valoare este numărul maxim de copii care primesc cadouri iar a doua este numărul de bomboane din cutia păstrată; pentru C = 2 prima valoare este numărul maxim de bomboane primite de un copil iar a doua reprezintă numărul de bomboane din cutia păstrată.
Dacă nu se păstrează nicio cutie, în fișierul de ieșire a doua valoare scrisă va fi 0 (atât în cazul cerinței 1 cât și în cazul cerinței 2).

Restricții și precizări

• 2 ≤ N ≤ 100.000
• Numerele de pe linia a treia sunt naturale, nenule, formate din cel mult 9 cifre.
• Pentru 23 de puncte, C = 1
• Pentru 77 de puncte, C = 2

Exemplul 1:

cadouri.in

1
5
2 7 4 1 2

cadouri.out

2 1

Explicație

Se rezolvă cerința 1. Doi copii primesc cadouri. Cutia cu o bomboană nu este dată nici unui copil.

Exemplul 2:

cadouri.in

2
5
2 7 4 1 2

cadouri.out

9 1

Explicație

Se rezolvă cerința 2. Doi copii primesc cadouri, primul copil primește cutiile cu 2 și 7 bomboane, iar al doilea copil primește cutiile cu 4 și 2 bomboane. Deci primul copil primește număr maxim de bomboane, 9. Cutia cu o bomboană nu este dată niciunui copil.