\(S \coloneqq \displaystyle\sum_{i = 1}^{N} B_i\) とおきます。

\(S\) が \(3\) の倍数でないとき、答えは \(-1\) です。以下、\(S\) が \(3\) の倍数であると仮定します。

\(S\) の値が小さいことを利用して動的計画法を行います。

\(dp_{i, x, y, z}\) を人 \(1, 2, \ldots, i\) までの所属チームを確定させて、チーム \(1, 2, 3\) の強さがそれぞれ \(x, y, z\) であるときの所属したチームを変えた人数の最小値（そのようなことが起きないときは \(\infty\)） として定義します。

この dp を素朴に行うと実行時間制限に間に合いませんが、人 \(1, 2, \ldots , i\) の強さの和を考えると \(i, x, y\) から \(z\) は一意に定まることに注目すると（より厳密には、\(i, x, y\) が定まっているとき \(dp_{i,x ,y, z} \neq \infty\) なる \(z\) は高々一意であることを利用します）、添え字として \(z\) は持つ必要がないことがわかります。

以上をまとめると、\(dp_{i, x, y}\) を人 \(1, 2, \ldots, i\) までの所属チームを確定させて、チーム \(1, 2\) の強さがそれぞれ \(x, y\) であるときの所属したチームを変えた人数の最小値とした動的計画法により答えが計算できることがわかります。

求める答えは \(dp_{N,\frac{S}{3},\frac{S}{3}}\) であるため、dp の添え字 \(x, y\) としては \(\frac{S}{3}\) までを考えれば十分であることに注意してください（\(S\) までを計算する方針だと、他の部分の定数倍によっては間に合わない可能性があります）。

また、\(1 \leq B_i\) を利用すると、添え字として \(i\) を省略する方針を取ることもできます。この場合はさらに定数倍に気を付ける必要があります。

実装例

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
template<class T, class U> inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return true; } return false; }

int main() {
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	rep(i, n) cin >> a[i] >> b[i];
	int sum = accumulate(b.begin(), b.end(), 0);
	if (sum % 3 != 0) {
		cout << "-1\n";
		return 0;
	}
	int A = 501;
	int inf = 1000000000;
	vector<vector<int>> dp(A, vector<int>(A, inf));
	dp[0][0] = 0;
	rep(i, n) {
		vector<vector<int>> ep(A, vector<int>(A, inf));
		int e = b[i];
		rep(j, A) {
			rep(k, A) {
				if (a[i] == 1) {
					if (j + e < A) chmin(ep[j + e][k], dp[j][k]);
					if (k + e < A) chmin(ep[j][k + e], dp[j][k] + 1);
					chmin(ep[j][k], dp[j][k] + 1);
				}
				else if (a[i] == 2) {
					if (j + e < A) chmin(ep[j + e][k], dp[j][k] + 1);
					if (k + e < A) chmin(ep[j][k + e], dp[j][k]);
					chmin(ep[j][k], dp[j][k] + 1);
				}
				else {
					if (j + e < A) chmin(ep[j + e][k], dp[j][k] + 1);
					if (k + e < A) chmin(ep[j][k + e], dp[j][k] + 1);
					chmin(ep[j][k], dp[j][k]);
				}
			}
		}
		dp = move(ep);
	}
	int res = dp[sum / 3][sum / 3];
	cout << (res == inf ? -1 : res) << '\n';
}