Smallest sum no subsequence can make

Time limit2sMemory limit512 MB

Summary

Given N ≤ 20 numbers, find the smallest natural number that is not the sum of any non-empty subsequence.

Level: Medium5 of 10
Topics: Backtracking, Brute force, Sorting
Solved: No attempts yet

Problem

You are given a sequence $S$ . Write a program that finds the smallest natural number that cannot be written as the sum of a non-empty subsequence of $S$ .

For example, if $S = [5, 1, 2]$ , you can make $1$ , $2$ , $3 = 1 + 2$ , $5$ , $6 = 1 + 5$ , $7 = 2 + 5$ , and $8 = 1 + 2 + 5$ . No subsequence sums to $4$ , so the answer is $4$ .

Input

The first line contains the size $N$ of the sequence $S$ ( $1 \le N \le 20$ ).

The second line contains the $N$ elements of $S$ , separated by spaces. Each element is a natural number no greater than 100,000.

Output

Print the smallest natural number that is not the sum of any subsequence of $S$ .

Examples3

Example 1
Input
```
3
5 1 2
```
Expected output
```
4
```
Example 2
Input
```
3
2 1 4
```
Expected output
```
8
```
Example 3
Input
```
4
2 1 2 7
```
Expected output
```
6
```