Let \(S \coloneqq \displaystyle\sum_{i = 1}^{N} B_i\).

If \(S\) is not a multiple of \(3\), the answer is \(-1\). From now on, we assume that \(S\) is a multiple of \(3\).

Noticing that \(S\) is small, we take Dynamic Programming (DP) approach.

Let \(dp_{i, x, y, z}\) be the minimum number of people who need to switch their teams so that people \(1, 2, \ldots, i\) are assigned to each team and the strengths of teams \(1\), \(2\), and \(3\) are \(x\), \(y\), and \(z\), respectively. (If it is impossible, let it \(\infty\).)

Naively performing this DP does not finish within the execution time limit. However, considering the sum of strengths of people \(1, 2, \ldots ,\), and \(i\), it turns out that \(z\) is uniquely determined given \(i, x\), and \(y\) (strictly speaking, we use the fact that for a fixed triple \((i, x, y)\), there is at most one \(z\) with \(dp_{i,x ,y, z} \neq \infty\)). This allows us not to maintain \(z\) as the index.

In short, the answer can be found with DP, where \(dp_{i, x, y}\) is the minimum number of people who need to switch their teams so that people \(1, 2, \ldots, i\) are assigned to each team and the strengths of teams \(1\) and \(2\) are \(x\) and \(y\), respectively. (If it is impossible, let it \(\infty\).)

The sought value is \(dp_{N,\frac{S}{3},\frac{S}{3}}\), so it is sufficient to support indices \(x\) and \(y\) up to \(\frac{S}{3}\). (If you try to maintain up to \(S\), it might not finish in time depending on other constant factors.)

Alternatively, since \(1 \leq B_i\), one can kick out the index \(i\), which requires extra caution on the constant factor.

Sample code

#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';
}