cadouri

Înaintea vacanței de Paste, 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țe

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?

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 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 \leq N \leq 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ă cerinta $2$. Doi copii primesc cadouri, primul copil primește cutiile cu $2$ și $7$ bomboane, iar al doilea copil primește cutiile cu $4$ si $2$ bomboane. Deci primul copil primește număr maxim de bomboane, $9$. Cutia cu o bomboană nu este dată nici unui copil.