Farmer John planuje otworzyć nowy uniwersytet dla krów!
Istnieje $N$ krów ($1 \le N \le 10^5$), które potencjalnie mogłyby uczęszczać na ten uniwersytet. Każda krowa jest skłonna zapłacić czesne wynoszące najwyżej $c_i$ ($1 \le c_i \le 10^6$). Farmer John może ustalić czesne, które wszystkie krowy muszą zapłacić, aby się zapisać. Jeśli czesne przekracza maksymalną kwotę, którą krowa jest skłonna zapłacić, nie będzie ona uczęszczać na uniwersytet. Farmer John chce zarobić jak najwięcej pieniędzy, aby móc wypłacić swoim wykładowcom godziwe wynagrodzenie. Ustal, ile pieniędzy może zarobić i jakie czesne powinien ustalić.
Wejście
Pierwszy wiersz zawiera $N$. Drugi wiersz zawiera $N$ liczb całkowitych $c_1, c_2, \dots, c_N$, gdzie $c_i$ jest maksymalnym czesnym, które krowa $i$ jest skłonna zapłacić.
Wyjście
Wypisz maksymalną kwotę, którą Farmer John może zarobić, oraz optymalne czesne, które powinien pobierać. Jeśli istnieje kilka rozwiązań, wypisz rozwiązanie z najmniejszym optymalnym czesnym.
Zauważ, że duże wartości liczb całkowitych występujących w tym zadaniu mogą wymagać 64-bitowych typów całkowitych (np. "long" w Javie lub "long long" w C/C++).
Przykład
Wejście 1
4 1 6 4 6
Wyjście 1
12 4
Uwagi
Jeśli Farmer John pobiera $4$, na uniwersytet będą uczęszczać $3$ krowy, co pozwoli mu zarobić $3 \cdot 4 = 12$.
Podzadania
- Testy od 2 do 4 spełniają $c_i \le 1{,}000$.
- Testy od 5 do 8 spełniają $N \le 5{,}000$.
- Testy od 9 do 12 nie mają dodatkowych ograniczeń.
Autor zadania: Freddie Tang