#include <iostream> #include <stdio.h> #include <memory.h> using namespace std; const int INF = 10005; int dp[10010]; int money[110]; void dodp(int n) { memset(dp, 0x80, sizeof(dp)); dp[0] = 0; for(int i = 0; i < n; i ++) { for(int v = INF; v >= 0; v --) { if(v >= money[i]) dp[v] = max(dp[v-money[i]]+money[i], dp[v]); } } for(int i = 0; i < INF; i++) { if(dp[i] < 0) { cout << i << endl; break; } } } int main() { int n; while(scanf("%d", &n) != EOF) { for(int i = 0; i < n; i ++) scanf("%d", money+i); dodp(n); } return 0; }