#include <bits/stdc++.h>
using namespace std;
using P = pair<long long, long long>;

long long n;
vector<long long> a, cnt;

long long solve();
long long dfs(long long s, long long nextid, long long sum);

int main() {
  cin >> n;
  a.resize(n);
  cnt.assign(n, 0);
  for(int i = 0; i < n; ++i) cin >> a[i];
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long res = 0;
  for(int i = 0; i < n; ++i) res += a[i];
  return res - dfs(0, 0, 0);
}

long long dfs(long long s, long long nextid,
              long long sum) {
  if(nextid == (1LL << n)) return sum;
  long long res = sum;
  P nowp = make_pair(s, nextid);
  // nextid:false
  res = max(res, dfs(s, nextid + 1, sum));
  // nextid:true
  vector<int> lst;
  for(int i = 0; i < n; ++i)
    if(nextid >> i & 1) lst.push_back(i);
  int lstsize = lst.size();
  if(lstsize <= 1) return res;
  for(int i = 0; i < lstsize; ++i)
    for(int j = i + 1; j < lstsize; ++j) {
      if(s >> (lst[i] * n + lst[j]) & 1) return res;
      s += (1LL << (lst[i] * n + lst[j]));
    }
  for(int i = 0; i < lstsize; ++i) {
    if(++cnt[lst[i]] > a[lst[i]]) {
      for(int j = i; j >= 0; --j) --cnt[lst[j]];
      return res;
    }
  }
  sum += lstsize - 1;
  nowp = make_pair(s, nextid);
  res = max(res, dfs(s, nextid + 1, sum));
  for(int i = 0; i < lstsize; ++i) --cnt[lst[i]];
  return res;
}

### Prompt

Please formulate a Cpp solution to the following problem:

There is a complete graph of m vertices. Initially, the edges of the complete graph are uncolored. Sunuke did the following for each i (1 ≤ i ≤ n): Select ai vertices from the complete graph and color all edges connecting the selected vertices with color i. None of the sides were painted in multiple colors. Find the minimum value that can be considered as m.

Constraints

* 1 ≤ n ≤ 5
* 2 ≤ ai ≤ 109

Input


n
a1
.. ..
an


Output

Output the minimum value of m on one line.

Examples

Input

2
3
3


Output

5


Input

5
2
3
4
5
6


Output

12

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using P = pair<long long, long long>;

long long n;
vector<long long> a, cnt;

long long solve();
long long dfs(long long s, long long nextid, long long sum);

int main() {
  cin >> n;
  a.resize(n);
  cnt.assign(n, 0);
  for(int i = 0; i < n; ++i) cin >> a[i];
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long res = 0;
  for(int i = 0; i < n; ++i) res += a[i];
  return res - dfs(0, 0, 0);
}

long long dfs(long long s, long long nextid,
              long long sum) {
  if(nextid == (1LL << n)) return sum;
  long long res = sum;
  P nowp = make_pair(s, nextid);
  // nextid:false
  res = max(res, dfs(s, nextid + 1, sum));
  // nextid:true
  vector<int> lst;
  for(int i = 0; i < n; ++i)
    if(nextid >> i & 1) lst.push_back(i);
  int lstsize = lst.size();
  if(lstsize <= 1) return res;
  for(int i = 0; i < lstsize; ++i)
    for(int j = i + 1; j < lstsize; ++j) {
      if(s >> (lst[i] * n + lst[j]) & 1) return res;
      s += (1LL << (lst[i] * n + lst[j]));
    }
  for(int i = 0; i < lstsize; ++i) {
    if(++cnt[lst[i]] > a[lst[i]]) {
      for(int j = i; j >= 0; --j) --cnt[lst[j]];
      return res;
    }
  }
  sum += lstsize - 1;
  nowp = make_pair(s, nextid);
  res = max(res, dfs(s, nextid + 1, sum));
  for(int i = 0; i < lstsize; ++i) --cnt[lst[i]];
  return res;
}

```