No Change

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

요약

동전 값들이 주어질 때, 서로 다른 동전의 합으로 만들 수 없는 가장 작은 양의 금액을 구한다.

난이도: 쉬움10점 중 3점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

Jack has $N$ coins, with values $M\_1$ , $M\_2$ , \dots, $M\_N$ . Find the smallest positive amount that cannot be paid with these coins with no change.

입력

The first line contains $N$ ( $1 \le N \le 1\\,000$ ), the number of coins. The second line contains $N$ integers $M\_i$ ( $1 \le M\_i \le 1\\,000\\,000$ ), the values of the coins.

출력

The only line should contain a single positive integer: the smallest amount that Jack cannot pay with his coins.

예제2

예제 1
입력
```
3
1 2 5
```
예상 출력
```
4
```
예제 2
입력
```
3
1 2 2
```
예상 출력
```
6
```