시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB34822822067.278%

문제

$N$명의 학생이 교탁에 놓인 학습지를 가져오고자 한다. $i$번 학생은 교탁으로 가는 데 $t_i$초가 걸리고 학습지를 챙기는 데 $1$초가 걸린다. 단, 어떤 학생이 학습지를 챙기는 동안에는 다른 학생이 학습지를 챙길 수 없다.

학습지를 챙긴 뒤 자리로 돌아오는 시간은 무시할 때 모든 학생이 학습지를 챙기는 데 최소 몇 초가 걸리는지 구하시오.

입력

첫 번째 줄에 학생의 수 $N$이 주어진다. $(1\le N\le 1\,000)$

두 번째 줄에 각 학생이 교탁으로 가는 데 걸리는 시간을 나타내는 $N$개의 정수 $t_1, t_2, \dots, t_N$이 공백으로 구분되어 주어진다. $(1 \le t_i \le 10^5)$

출력

모든 학생이 학습지를 챙기는 데 최소 몇 초가 걸리는지 출력한다.

예제 입력 1

5
3 1 2 4 2

예제 출력 1

6