#pragma GCC target("avx2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include #include #include #include #include //#include //using namespace atcoder; using namespace std; using i32 = int_fast32_t; using i64 = int_fast64_t; using usize = size_t; using u32 = uint_fast32_t; using u64 = uint_fast64_t; using i128 = __int128_t; using u128 = __uint128_t; using ld = long double; template using vec = vector; #define rep(i, n) for (i64 i = 0; i < (i64)(n); ++i) #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define len(hoge) (i64)((hoge).size()) using P = pair; template ostream &operator<<(ostream &os, const pair &p){ os << p.first << " " << p.second; return os; } void solve(){ } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); i32 n; cin >> n; vec d(n); rep(i,n)cin >> d[i]; vec dp(1 << n); vec mx = dp; mx[0] = 100; for(i32 Set = 1; Set < (1 << n); Set++){ rep(bit,n){ if(Set & (1 << bit)){ if(d[bit] < 0)mx[Set] = mx[Set ^ (1 << bit)] + 100; else mx[Set] = mx[Set ^ (1 << bit)]; break; } } dp[0] = 100; rep(Set, (1 << n)){ if(dp[Set] == 0)continue; rep(bit,n){ if(!(Set & (1 << bit))){ i32 k = min(dp[Set] + d[bit], mx[Set | (1 << bit)]); dp[Set | (1 << bit)] = max(dp[Set | (1 << bit)], k); } } } } cout << dp.back() << endl; }