균형 잡힌 등급

서울과학고의 자료구조 수업에는 $N$명의 학생이 수강한다. 이 수업에는 중간고사와 기말고사가 있으며, 각 시험의 점수는 $0$ 이상 $10^6$ 이하의 정수이다.

선생님은 학생들의 시험 점수를 바탕으로 학생마다 '상', '중', '하' 중 하나의 등급을 부여하려고 한다. 이때 등급은 다음 두 조건을 만족해야 한다.

• 각 등급은 적어도 한 명의 학생이 받아야 한다.
• 더 높은 등급을 받은 학생은 더 낮은 등급을 받은 학생보다 중간고사와 기말고사 점수가 모두 높아야 한다.

선생님은 불균형도가 최소가 되도록 등급을 매기려고 한다. '상', '중', '하' 등급을 받은 학생 수를 각각 $a$, $b$, $c$라고 하자. 이때 불균형도는 $\max(a,b,c) -\min(a,b,c)$로 정의된다.

가능한 불균형도의 최솟값을 구하여라.

첫 줄에 학생 수 $N$이 주어진다.

이어서 $N$개의 줄에 걸쳐 $i$번 학생의 중간고사 점수 $A_i$와 기말고사 점수 $B_i$가 띄어쓰기를 사이에 두고 주어진다.

가능한 불균형도의 최솟값을 출력한다.

조건에 맞게 등급을 부여하는 것이 불가능하면 -1을 출력한다.

• $3\le N\le 2\times 10^5$
• $0\le A_i,B_i\le 10^6$ $(1\le i\le N)$
• 입력으로 주어지는 모든 수는 정수이다.

$\max(a,b,c)$와 $\min(a,b,c)$는 각각 $a$, $b$, $c$ 중 최댓값과 최솟값을 의미한다.