눈 치우기

면접 대비

시간 제한1초메모리 제한512 MB

요약

각 분마다 한 집 또는 서로 다른 두 집에서 눈을 1 단위씩 치울 때, 모든 집의 눈을 치우는 최소 시간을 구합니다.

난이도: 보통10점 중 4점
유형: 수학, 그리디
정답자: 아직 제출이 없습니다

문제

지난밤 겨울 숲에 눈이 많이 내렸다. 당신은 숲 주민들을 위해 눈이 내리지 않는 동안 모든 집 앞의 눈을 치우려 한다. 당신은 1분마다 두 집을 골라 각각의 앞에서 눈을 1만큼 치우거나, 한 집을 골라 그 집 앞의 눈을 1만큼 치울 수 있다. 모든 집 앞의 눈을 다 치우는 데 걸리는 최소 시간은 얼마일까?

입력

첫 줄에 집의 수를 나타내는 정수 $N$ ( $1 \leq N \leq 100$ )이 주어진다. 다음 줄에는 각 집 앞에 쌓인 눈의 양을 나타내는 정수 $a_{i}$ ( $1 \leq a_{i} \leq 2000$ )이 주어진다.

출력

모든 집 앞의 눈을 치우는 데 걸리는 최소 분을 출력한다. 24시간(1440분)을 넘게 걸리면 -1을 출력한다.

예제4

예제 1
입력
```
3
1 2 3
```
예상 출력
```
3
```
예제 2
입력
```
3
1 2 5
```
예상 출력
```
5
```
예제 3
입력
```
1
1441
```
예상 출력
```
-1
```
예제 4
입력
```
1
1440
```
예상 출력
```
1440
```