三队分组

题目描述

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

人员编号为 $1, 2, \ldots, N$,队伍编号为 $1, 2, 3$。当前,人员 $i$ 属于队伍 $A_i$。

每个人都有一个称为「力量」的数值,人员 $i$ 的力量为 $B_i$。队伍的力量定义为该队所有成员力量之和。

请判断是否可以让零人或更多的人更换队伍,使得三支队伍的力量全部相等。若可行,求为了实现这一目标需要更换队伍的最少人数。

不允许创建队伍 $1, 2, 3$ 以外的其他队伍。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

若能使三支队伍的力量全部相等,输出需要更换队伍的最少人数。否则输出 -1。

样例

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

2

若人员 $1$ 更换到队伍 $3$,人员 $4$ 更换到队伍 $2$,则三支队伍的力量均为 $8$。

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 \le N \le 100$
• $A_i \in \{1, 2, 3\}$
• 对每个 $x \in \{1, 2, 3\}$,都存在某个 $i$ 满足 $A_i = x$。
• $1 \le B_i$
• $\sum_{i = 1}^{N} B_i \le 1500$
• 所有输入值均为整数。