클리크 색칠

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

요약

최대 다섯 개의 클리크 크기가 주어질 때, 같은 간선을 두 번 칠하지 않고 그 크기들의 클리크로 모든 간선을 덮을 수 있는 최소 정점 수를 구한다.

난이도: 어려움10점 중 8점
유형: 조합론, 수학, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

정점이 $m$ 개인 완전 그래프가 있다. 처음에는 그래프의 간선에 색이 칠해져 있지 않다. Snuke는 각 $i$ ( $1 \le i \le n$ )에 대해 다음 작업을 수행했다. 그래프에서 $a_i$ 개의 정점을 고르고, 고른 정점 중 두 개를 잇는 모든 간선을 색 $i$ 로 칠한다. 어떤 간선도 두 번 이상 칠해지지 않았다. $m$ 의 최솟값을 구하시오.

입력

첫째 줄에 정수 $n$ ( $1 \le n \le 5$ )이 주어진다. 이어서 $n$ 개의 줄이 주어지고, $i$ 번째 줄에는 정수 $a_i$ ( $2 \le a_i \le 10^9$ )가 주어진다.

출력

$m$ 의 최솟값을 출력한다.

힌트

그래프의 정점에 $1, 2, 3, 4, 5$ 의 번호를 붙이자. 예를 들어 다음과 같이 색칠할 수 있다.

정점 $1, 2, 3$ 을 고르고 그 사이의 간선을 색 $1$ 로 칠한다.
정점 $1, 4, 5$ 를 고르고 그 사이의 간선을 색 $2$ 로 칠한다.

예제2

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