题目描述

一共有 $N$ 名同学，当前他们被分到了编号 $1、2、3$ 三个队伍中。第 $i$ 名同学的当前所在队伍编号是 $A_i$，同时每名同学有一个实力值 $B_i$。定义一个队伍的总实力值为该队所有队员的实力值之和。

现在小蓝可以让任意数量的同学换队（换队后只能去这三个队伍中的任意一个，不能创建新队伍）。小蓝希望最终三个队伍的总实力值完全相等。请求出达到这个目标所需要的最少换队人数。如果无论怎么调整都无法让三个队实力相等，输出 -1。

输入格式

第一行一个正整数 $N$，表示同学的总人数。

接下来 $N$ 行，每行两个正整数 $A_i, B_i$，分别表示第 $i$ 名同学当前的队伍编号和他的实力值。

输出格式

输出一行一个整数，使得三个队伍最终总实力相等的最少换队人数。如果不存在可行方案，输出 -1。

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

2

样例 1 解释说明

让第 $1$ 名同学换到第 $3$ 队，第 $4$ 名同学换到第 $2$ 队，此时三队的总实力值都是 $8$，仅需要 $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 \le N \le 100$
• $A_i \in \{1, 2, 3\}$
• 每个初始队伍至少有一名队员
• $1 \le B_i \le 1500$，所有 $B_i$ 的总和不超过 $1500$, 即 $\sum_{i=1}^nB_i\le 1500$, 且保证 $B_i \le \lfloor\frac{\sum_{i=1}^nB_i}{3}\rfloor$