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

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

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

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

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

입력 형식

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

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

출력 형식

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

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

예제 입력 1

3
1 10
2 20
3 30

예제 출력 1

0

예제 입력 2

8
1 2
2 1
3 4
4 3
5 6
6 5
7 8
8 7

예제 출력 2

2

예제 입력 3

5
2 4
3 1
5 6
8 2
7 3

예제 출력 3

-1

힌트

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