rt. 写朴素做法时我注意到只要记录正负数差值即可 没想到 n 次背包 + bitset，跑完一次总的背包后再回退（就是消失之物那样），这样的复杂度仅 $O(nV)$，应该是比 std 的 $O(\frac{n^2V}{w})$ 更有的，但我调不出来 TAT，对拍出了一组错的数据：

1.in:

10
-23 -25 15 12 31 -31 -28 4 7 -14 

1.ans

31

1.out

30

最优方案：

-31 -28 -25 -23 -14 4 12 15 31 7

代码（里面有一些调试用的东西没删）

#include <bits/stdc++.h>
using namespace std;

using LL = __int128;
using ll = long long;
using ldb = long double;
using vi = vector < int >;
using ull = unsigned long long;
#define pb push_back
#define ve vector < edge >
#define lowbit(x) ((x) & -(x))
#define me(a, b) memset(a, b, sizeof(a))
#define L(i, j, k) for (int i = j; i <= int(k); i++)
#define R(i, j, k) for (int i = j; i >= int(k); i--)
#define debug cerr << __FILE__ << ": " << __LINE__ << '\n';
#define qio() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
namespace io {
	char buf[1 << 21], *p1 = buf, *p2 = buf;
	#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
	int read() {
		int res(0), f(1);
		char ch(getchar());
		while (ch < '0' || ch > '9') {
			if (ch == '-')
				f = -1;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			res = res * 10 + (ch ^ '0');
			ch = getchar();
		}
		return res * f;
	}
	ll readl() {
		ll res(0);
		int f(1);
		char ch(getchar());
		while (ch < '0' || ch > '9') {
			if (ch == '-')
				f = -1;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			res = res * 10 + (ch ^ '0');
			ch = getchar();
		}
		return res * f;
	}
} 
using io::read;
using io::readl;

template < class T >
ostream& operator << (ostream& out, vector < T > v) {
	out << '[';
	if (!v.empty()) {
		L(i, 0, v.size() - 2)
			out << v[i] << ',';
		out << v[v.size() - 1];
	}
	return out << ']';
}
namespace Dbg {
	template < class T >
	void dbg(char *f, T t) {
		cerr << f << '=' << t << endl;
	}
	template < class T, class ...Ar >
	void dbg(char *f, T x, Ar... y) {
		while (*f != ',')
			cerr << *f++;
		cerr << '=' << x << ',';
		dbg(f + 1, y...);
	}
}
#define gdb(...) cerr << "gdb in line " <<__LINE__ << ": ", Dbg::dbg((char*)#__VA_ARGS__,__VA_ARGS__);

const int N = 2e3 + 5; // Adjust
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;

int _[N << 1], __[N][N << 1];
int n, *f = &_[N], *g[N];
vi nb, neg, pos;

int main() {
	n = read();
	for (int i = 1, x; i <= n; i++) {
		if ((x = read()) > 0)
			pos.pb(x);
		else if (x < 0)
			neg.pb(x);
		if (x != 0)
			nb.pb(x);
		g[i - 1] = &__[i - 1][N];
	}

	n = nb.size();

	if (pos.empty()) {
		int ans = -inf;
		for (int num : neg)
			ans = max(ans, num);
		return printf("%d\n", ans), 0;
	}
	if (neg.empty()) {
		int ans = 0;
		for (int num : pos)
			ans = max(ans, num);
		return printf("%d\n", ans), 0;
	}

//	f[0] = 1;
	for (int num : nb) {
		f[num] = 1;
		if (num < 0)
			for (int dlt = max(-2000, -2000 + num); dlt <= min(2000, 2000 + num); dlt++)
				f[dlt] += f[dlt - num] - (dlt == 2 * num), assert(dlt - num >= -2000);
		else
			for (int dlt = min(2000, 2000 + num); dlt >= max(-2000, -2000 + num); dlt--)
				f[dlt] += f[dlt - num] - (dlt == 2 * num), assert(dlt - num <= 2000);
		gdb(num, f[0]);
		cout << "__________\n";
	}

//	f[0]--;
	gdb(f[0]);

	int ans = -inf;
	for (int i = 0; i < n; i++) {
		int num = nb[i];
		for (int dlt = -2000; dlt < max(-2000, -2000 + num); dlt++)
			g[i][dlt] = f[dlt];
		for (int dlt = min(2000, 2000 + num) + 1; dlt <= 2000; dlt++)
			g[i][dlt] = f[dlt];
		if (nb[i] > 0)
			for (int dlt = max(-2000, -2000 + nb[i]); dlt <= min(2000, 2000 + num); dlt++)
				g[i][dlt] = f[dlt] - g[i][dlt - nb[i]];
		else
			for (int dlt = min(2000, 2000 + num); dlt >= max(-2000, -2000 + num); dlt--)
				g[i][dlt] = f[dlt] - g[i][dlt - nb[i]];

//		if (!i)
//			gdb(g[i][0], f[0]);
		
		if (num == 31)
			gdb(f[0], g[i][0], g[i][-31]);

		if (num > 0) {
			for (int dlt = -2000; dlt <= 0; dlt++)
				if (g[i][dlt]) {
					ans = max(ans, dlt + num);
					if (dlt + num == 30)
						gdb(dlt, g[i][dlt], num);
				}
		} else {
			for (int dlt = 0; dlt <= 2000; dlt++)
				if (g[i][dlt])
					ans = max(ans, g[i][dlt] + num);
		}

//		gdb(i, ans);
	}
	
	return printf("%d\n", ans), 0;
}