$N$명의 학생이 교탁에 놓인 학습지를 가져오고자 한다. $i$번 학생은 교탁으로 가는 데 $t_i$초가 걸리고 학습지를 챙기는 데 $1$초가 걸린다. 단, 어떤 학생이 학습지를 챙기는 동안에는 다른 학생이 학습지를 챙길 수 없다.
학습지를 챙긴 뒤 자리로 돌아오는 시간은 무시할 때 모든 학생이 학습지를 챙기는 데 최소 몇 초가 걸리는지 구하시오.
Input
첫 번째 줄에 학생의 수 $N$이 주어진다. $(1\le N\le 1\,000)$
두 번째 줄에 각 학생이 교탁으로 가는 데 걸리는 시간을 나타내는 $N$개의 정수 $t_1, t_2, \dots, t_N$이 공백으로 구분되어 주어진다. $(1 \le t_i \le 10^5)$
Output
모든 학생이 학습지를 챙기는 데 최소 몇 초가 걸리는지 출력한다.
Examples
Input 1
5 3 1 2 4 2
Output 1
6