탁월함

면접 대비

시간 제한2초메모리 제한256 MB

요약

모든 학생을 두 명씩 짝지어 가장 작은 팀 점수 합이 최대가 되도록 합니다.

난이도: 보통10점 중 4점
유형: 그리디, 정렬, 투 포인터
정답자: 아직 제출이 없습니다

문제

세계 코딩 연맹이 프로그래머 두 명으로 팀을 짜는 대규모 온라인 프로그래밍 대회를 연다. 심사위원 David는 남동부 대표단의 팀 편성을 맡았다. 모든 학생은 정확히 한 팀에 배정되고, 참가를 원하는 학생 수가 짝수라서 남는 학생 없이 두 명씩 짝지을 수 있다. David는 자신이 내보내는 팀이 모두 정해진 총점 이상이 되기를 바란다. 팀의 총점은 두 팀원의 점수를 더한 값이다.

모든 팀의 총점이 $X$ 이상이 되도록 팀을 편성할 수 있는 최댓값 $X$ 를 구하라.

입력

첫째 줄에 대회에 참가하려는 학생 수 $n$ 이 주어진다 ( $1 \le n \le 10^5$ , $n$ 은 짝수). 이어지는 $n$ 개 줄에는 학생 $i$ 의 점수 $s_i$ 가 한 줄에 하나씩 주어진다 ( $1 \le s_i \le 10^6$ ).

출력

모든 팀의 총점이 $X$ 이상이 되도록 David가 팀을 편성할 수 있는 최댓값 $X$ 를 한 줄에 출력한다.

예제3

예제 1
입력
```
4
1
2
3
5
```
예상 출력
```
5
```
예제 2
입력
```
2
18
16
```
예상 출력
```
34
```
예제 3
입력
```
4
13
12
19
14
```
예상 출력
```
27
```