AT_abc375_e [ABC375E] 3 Team Division

题目描述

有 $N$ 个人，被分成了 $3$ 个队伍。

每个人有 $1, 2, \ldots, N$ 的编号，每个队伍有 $1, 2, 3$ 的编号，现在第 $i$ 个人属于队伍 $A_i$。

每个人有一个强度值，第 $i$ 个人的强度为 $B_i$。队伍的强度定义为该队伍中所有成员的强度之和。

你可以让 $0$ 个或更多的人更换所属队伍。请判断是否可以通过更换队伍，使得所有队伍的强度都相等。如果可以，请求出需要更换队伍的人数的最小值。

注意，除了队伍 $1, 2, 3$ 之外，不能新建队伍。

输入格式

输入以如下格式从标准输入给出。

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

输出格式

如果可以通过更换队伍使所有队伍的强度相等，输出所需更换队伍人数的最小值。否则输出 $-1$。

输入输出样例 #1

输入 #1

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

输出 #1

2

输入输出样例 #2

输入 #2

4
1 1
1 2
2 3
3 4

输出 #2

-1

输入输出样例 #3

输入 #3

3
1 1
2 1
3 1

输出 #3

0

输入输出样例 #4

输入 #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

说明/提示

限制条件

• $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$
• 输入的所有值均为整数

样例解释 1

将第 $1$ 个人调到队伍 $3$，第 $4$ 个人调到队伍 $2$，可以使所有队伍的强度都变为 $8$。

由 ChatGPT 4.1 翻译