题目描述

有 $N$ 个人，他们被分成了 $3$ 个团队。

每个人都有一个编号 $1,\ 2,\ \dots,\ N$，每个团队也有一个编号 $1,\ 2,\ 3$。当前，第 $i$ 个人所属的团队是 $A_i$。

每个人都有一个强度值，第 $i$ 个人的强度值为 $B_i$。此外，团队的强度被定义为该团队内所有成员的强度值之和。

现在，你可以选择将 $0$ 人或以上的人调整到不同的团队。你的任务是判断是否可以使所有团队的强度相等。如果可以，请计算最少需要调整的人数；如果不可能，则输出 $-1$。

请注意，不能创建新的团队，团队编号仍然只有 $1,\ 2,\ 3$。

输入格式

第一行输入 $N$

接下来 $N$ 行，每行输入两个整数 $A_i$ $B_i$

输出格式

如果可以使所有团队的强度相等，输出最小需要调整的人数；否则输出 $-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 \{1, 2, 3\}$
• 对于每个 $x \in \{1, 2, 3\}$，至少存在一个 $i$ 使得 $A_i = x$
• $1 \leq B_i$
• $\displaystyle\sum_{i=1}^{N} B_i \leq 1500$
• 所有输入均为整数

样例 1 解释

可以让第 $1$ 个人加入团队 $3$，让第 $4$ 个人加入团队 $2$，使得所有团队的强度变为 $8$。