#include <bits/stdc++.h>
using namespace std;
long long f[200000001], a[10001];
long long t, n, m;
long long ans, sum;
signed main() {
  scanf("%lld", &t);
  ans = 1000;
  for (long long i = 1; i <= t; i++) scanf("%lld", &a[i]);
  for (long long i = 1; i < t; i++) {
    for (long long j = 1; j <= ans; j++) f[j] = -0x3fffffff;
    f[ans] = ans;
    sum = 0;
    for (long long k = ans; k >= a[i]; k--)
      f[k - a[i]] = f[k - a[i]] < f[k] + a[i + 1] - a[i]
                        ? f[k] + a[i + 1] - a[i]
                        : f[k - a[i]],
            sum = sum < f[k - a[i]] ? f[k - a[i]] : sum;
    ans = ans < sum ? sum : ans;
  }
  printf("%d", ans);
  return 0;
}
