Score : $450$ points

问题陈述

有 $N$ 个人被分成三个队伍。

这些人被编号为 $1, 2, \ldots, N$，队伍被编号为 $1, 2, 3$。目前，第 $i$ 个人属于队伍 $A_i$。

每个人都有一个称为 力量 的值；第 $i$ 个人的力量是 $B_i$。一个队伍的 力量 被定义为其成员力量的总和。

确定是否可能让零个或更多的人换队伍，以便所有队伍的力量相等。如果可能，找出需要换队伍的最少人数以实现这一点。

你不能创建除了队伍 $1$、$2$、$3$ 之外的新队伍。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There are $N$ people divided into three teams.

The people are numbered $1, 2, \ldots, N$, and the teams are numbered $1, 2, 3$. Currently, person $i$ belongs to team $A_i$.

Each person has a value called strength; person $i$ has a strength of $B_i$. The strength of a team is defined as the sum of the strengths of its members.

Determine whether it is possible for zero or more people to switch teams so that all teams have equal strength. If it is possible, find the minimum number of people who need to switch teams to achieve this.

You cannot create new teams other than teams $1$, $2$, $3$.

Constraints

• $3 \leq N \leq 100$
• $A_i \in \lbrace 1, 2, 3 \rbrace$
• For each $x \in \lbrace 1, 2, 3 \rbrace$, there exists some $i$ with $A_i = x$.
• $1 \leq B_i$
• $\displaystyle\sum_{i = 1}^{N} B_i \leq 1500$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

Output

If it is possible to make all teams have equal strength, print the minimum number of people who need to switch teams. Otherwise, print -1.

Sample Input 1

6
1 2
2 5
1 5
3 3
1 3
3 6

Sample Output 1

2

If person $1$ switches to team $3$ and person $4$ switches to team $2$, all teams will have a strength of $8$.

Sample Input 2

4
1 1
1 2
2 3
3 4

Sample Output 2

-1

Sample Input 3

3
1 1
2 1
3 1

Sample Output 3

0

Sample Input 4

12
2 5
1 4
3 3
2 3
3 9
1 2
2 2
3 9
2 6
1 9
1 1
3 1

Sample Output 4

3