103754: [Atcoder]ABC375 E - 3 Team Division

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

问题陈述

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

人们按编号为1, 2, …, N，队伍分别编号为1, 2, 3。目前，编号为i的人属于A_i队伍。

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

判断是否有可能通过零个或更多人的队伍转换使得所有队伍力量相等。如果可能，找出实现这一目标所需转换队伍的最少人数。

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

约束条件

• $3 \leq N \leq 100$
• $A_i \in \lbrace 1, 2, 3 \rbrace$
• 对于每个$x \in \lbrace 1, 2, 3 \rbrace$，存在某个$i$使得$A_i = x$。
• $1 \leq B_i$
• $\displaystyle\sum_{i = 1}^{N} B_i \leq 1500$
• 所有输入值都是整数。

输入

输入从标准输入以下格式给出：

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出

如果可能使得所有队伍力量相等，打印需要转换队伍的最少人数。否则，打印-1。

示例输入1

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

示例输出1

2

如果编号1的人转到队伍3，编号4的人转到队伍2，那么所有队伍的力量都会是8。

示例输入2

4
1 1
1 2
2 3
3 4

示例输出2

-1

示例输入3

3
1 1
2 1
3 1

示例输出3

0

示例输入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

示例输出4

3