Challenge Number King

Interview

Time limit1sMemory limit512 MB

Summary

Given up to 20 card values, count how many integers from 1 to their total sum cannot be formed as a subset sum.

Level: Medium5 of 10
Topics: Dynamic programming, Bit manipulation, Greedy, Sorting
Solved: No attempts yet

Problem

Today is a festive day.

While wandering around the festival wondering what to do, Baeknam found an event called Challenge Number King and, lured by the prize of 1,000,000 won, signed up right away.

Challenge Number King is a game where you combine $N$ number cards to make various numbers.

In this round, you win by calling out the count of numbers that cannot be made as a sum of the numbers written on the cards.

Help Baeknam take first place and enjoy the festival.

Input

The first line gives the number of cards $N$ ( $1\leq N \leq 20$ ).

The second line gives $N$ numbers.

Each number in the input is a natural number no greater than 100,000,000.

Output

Let $M$ be the sum of the numbers written on all the cards. Output the count of natural numbers between 1 and $M$ inclusive that cannot be made.

Examples2

Example 1
Input
```
3
1 2 3
```
Expected output
```
0
```
Example 2
Input
```
3
1 3 4
```
Expected output
```
2
```