Farmer John prévoit d'ouvrir une nouvelle université pour les vaches !
Il y a $N$ vaches ($1 \le N \le 10^5$) qui pourraient fréquenter cette université. Chaque vache est prête à payer des frais de scolarité d'au plus $c_i$ ($1 \le c_i \le 10^6$). Farmer John peut fixer les frais de scolarité que toutes les vaches doivent payer pour s'inscrire. Si ces frais dépassent le maximum qu'une vache est prête à payer, elle ne fréquentera pas l'université. Farmer John souhaite gagner le plus d'argent possible afin de payer un salaire équitable à ses enseignants. Déterminez combien d'argent il peut gagner et quels frais de scolarité il doit demander.
Entrée
La première ligne contient $N$. La deuxième ligne contient $N$ entiers $c_1, c_2, \dots, c_N$, où $c_i$ est le montant maximal des frais de scolarité que la vache $i$ est prête à payer.
Sortie
Affichez le montant maximal que Farmer John peut gagner et les frais de scolarité optimaux qu'il doit demander. S'il existe plusieurs solutions, affichez celle dont les frais de scolarité optimaux sont les plus faibles.
Notez que les grandes valeurs des entiers utilisés dans ce problème peuvent nécessiter des types entiers sur 64 bits (par exemple, "long" en Java ou "long long" en C/C++).
Exemples
Entrée 1
4 1 6 4 6
Sortie 1
12 4
Remarque
Si Farmer John demande $4$, alors $3$ vaches fréquenteront l'université, ce qui lui permettra de gagner $3 \cdot 4 = 12$.
Sous-tâches
- Les tests 2 à 4 vérifient $c_i \le 1{,}000$.
- Les tests 5 à 8 vérifient $N \le 5{,}000$.
- Les tests 9 à 12 n'ont aucune contrainte supplémentaire.
Auteur du problème : Freddie Tang