E - 3 Team Division Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 450 点

問題文

N 人の人がおり、3 つのチームに分かれています。

人には 1, 2, \ldots, N の番号、チームには 1, 2, 3 の番号がついており、現在人 i はチーム A_i に所属しています。

各人には強さという値が定まっており、人 i の強さは B_i です。また、チームの強さをチームに所属する人の強さの和として定めます。

0 人以上の人が所属するチームを変更することですべてのチームの強さが等しくなるようにできるか判定してください。すべてのチームの強さが等しくなるようにできる場合は所属するチームを変更する人数として考えられる最小値を求めてください。

ただし、チーム 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

Score : 450 points

Problem Statement

There are N people divided into three teams.

The people are numbered 1, 2, \ldots, N, and the teams are numbered 1, 2, 3. Currently, person i belongs to team A_i.

Each person has a value called strength; person i has a strength of B_i. The strength of a team is defined as the sum of the strengths of its members.

Determine whether it is possible for zero or more people to switch teams so that all teams have equal strength. If it is possible, find the minimum number of people who need to switch teams to achieve this.

You cannot create new teams other than teams 1, 2, 3.

Constraints

  • 3 \leq N \leq 100
  • A_i \in \lbrace 1, 2, 3 \rbrace
  • For each x \in \lbrace 1, 2, 3 \rbrace, there exists some i with A_i = x.
  • 1 \leq B_i
  • \displaystyle\sum_{i = 1}^{N} B_i \leq 1500
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

If it is possible to make all teams have equal strength, print the minimum number of people who need to switch teams. Otherwise, print -1.

Sample Input 1

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

Sample Output 1

2

If person 1 switches to team 3 and person 4 switches to team 2, all teams will have a strength of 8.

Sample Input 2

4
1 1
1 2
2 3
3 4

Sample Output 2

-1

Sample Input 3

3
1 1
2 1
3 1

Sample Output 3

0

Sample Input 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

Sample Output 4

3