균형 잡힌 등급

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

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

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

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

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

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

그 뒤 $N$개의 줄이 주어진다. 이들 중 $i$번째 줄에는 $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$ 중 최댓값과 최솟값을 의미한다.