페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5404

등록금 (Cow College) 1초 256MB

문제

N명의 학생들은 대학을 입학하려고 하는데, i번째 학생은 최대 ci원까지의 등록금만 부담이 가능하다.

등록금이 c<i원보다 크다면 해당 i번째 학생은 입학이 불가하다.

등록금을 얼마로 정해야 최대한의 이득을 추구할 수 있을지 알아보자.


입력

첫 번째 줄에는 학생의 수 N이 입력된다. (1≤N≤105)​​

두 번째 줄에는 학생들의 등록금 부담 상한액 c1,c2,…,cN​이 한 줄에 입력된다. (1≤ci≤106)​​


출력

대학에서 벌 수 있는 최대 금액과 그 때의 등록금을 출력하시오.

답이 여러 개라면 그 중 등록금의 최솟값을 선택하시오.

 

큰 자료형을 필요로 할 수 있다. (예: ​ Java​: "long", C/C++​: "long long")​


예제1

입력
4

1 6 4 6
출력
12 4


출처

USACO 2022 December Bronze

역링크 공식 문제집만