3 Team Division

题目描述

有 $N$ 人被分成三支队伍。 这些人编号为 $1, 2, \ldots, N$，队伍编号为 $1, 2, 3$。当前，第 $i$ 个人所属的队伍是 $A_i$。 每个人有一个称为 strength 的数值；第 $i$ 个人的 strength 为 $B_i$。队伍的 strength 定义为其成员的 strength 之和。 判断是否可以让零个或多个人人换队，使得所有队伍的 strength 相等。如果可以，求使之成立所需换队人数的最小值。 不能创建除队伍 $1$, $2$, $3$ 以外的新队伍。

输入格式

输入按标准输入给出，格式如下： $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

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

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

2

4
1 1
1 2
2 3
3 4

-1

3
1 1
2 1
3 1

0

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

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$ 个人换到队伍 $3$ 且第 $4$ 个人换到队伍 $2$，所有队伍的 strength 将为 $8$。

标签: AtCoder|abc375E

来源

AtCoder|abc375E