¡Farmer John planea abrir una nueva universidad para vacas!
Hay $N$ vacas ($1 \le N \le 10^5$) que podrían asistir a esta universidad. Cada vaca está dispuesta a pagar una matrícula máxima de $c_i$ ($1 \le c_i \le 10^6$). Farmer John puede fijar la matrícula que todas las vacas deben pagar para inscribirse. Si esta matrícula supera el máximo que una vaca está dispuesta a pagar, esa vaca no asistirá a la universidad. Farmer John quiere ganar la mayor cantidad de dinero posible para pagar un salario justo a sus profesores. Determina cuánto dinero puede ganar y cuánto debe cobrar de matrícula.
Entrada
La primera línea contiene $N$. La segunda línea contiene $N$ enteros $c_1, c_2, \dots, c_N$, donde $c_i$ es la matrícula máxima que la vaca $i$ está dispuesta a pagar.
Salida
Imprime la cantidad máxima de dinero que Farmer John puede ganar y la matrícula óptima que debe cobrar. Si hay varias soluciones, imprime la solución con la menor matrícula óptima.
Ten en cuenta que el gran tamaño de los enteros involucrados en este problema puede requerir tipos enteros de 64 bits (por ejemplo, "long" en Java o "long long" en C/C++).
Ejemplos
Entrada 1
4 1 6 4 6
Salida 1
12 4
Nota
Si Farmer John cobra $4$, entonces asistirán $3$ vacas, lo que le permitirá ganar $3 \cdot 4 = 12$.
Subtareas
- Los casos de prueba del 2 al 4 cumplen $c_i \le 1{,}000$.
- Los casos de prueba del 5 al 8 cumplen $N \le 5{,}000$.
- Los casos de prueba del 9 al 12 no tienen restricciones adicionales.
Autor del problema: Freddie Tang