分数: 450 点
问题陈述
有 N 人们分成三队。
人已数完 1, 2, \ldots, 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