Clique Coloring

Time limit2sMemory limit512 MB

Summary

Given up to five clique sizes, find the smallest number of vertices in a complete graph whose edges can be covered by cliques of those sizes with no repeated edge.

Level: Hard8 of 10
Topics: Combinatorics, Math, Brute force, Implementation
Solved: No attempts yet

Problem

There is a complete graph with $m$ vertices. Initially, no edge of the graph is colored. For each $i$ ( $1 \le i \le n$ ), Snuke performed the following operation: choose $a_i$ vertices of the graph and paint every edge connecting two of the chosen vertices with color $i$ . It turned out that no edge was painted more than once. Compute the minimum possible value of $m$ .

Input

The first line of input contains one integer $n$ ( $1 \le n \le 5$ ). Then $n$ lines follow; the $i$ -th of these lines contains one integer $a_i$ ( $2 \le a_i \le 10^9$ ).

Output

Print the minimum possible value of $m$ .

Hint

Number the vertices of the graph $1, 2, 3, 4, 5$ . For example, you can color the graph as follows.

Choose vertices $1, 2, 3$ and color the edges between them with color $1$ .
Choose vertices $1, 4, 5$ and color the edges between them with color $2$ .

Examples2

Example 1
Input
```
2
3
3
```
Expected output
```
5
```
Example 2
Input
```
5
2
3
4
5
6
```
Expected output
```
12
```