페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5837
서브태스크

조이 4인조 (JOI04) 2초 1024MB

문제

JOI 중학교에는 4N 명의 1학년이 재적하고 있어 4개의 반으로 나누어져 있다. 각 반의 정보는 다음과 같습니다.

  • 1학년 A반: N명의 학생이 있다. 각 학생의 키는 A_ 1 , A _2 , ..., A _N 다.

  • 1학년 B반: N명의 학생이 있다. 각 학생의 키는 B _1 , B _2 , ..., B _N 다.

  • 1학년 C반: N명의 학생이 있다. 각 학생의 키는 C _1 , C _2 , ..., C _N 다.

  • 1학년 D반: N명의 학생이 있다. 각 학생의 키는 D _1 , D _2 , ..., D _N 다.

다음 달 JOI 중학교에서는 체육대회가 개최된다. 그 중 각 학년이 춤추는 댄스는 체육대회의 꽃이라고 불리는 종목이다.

여기서 1학년은, 각 반들로부터 대표를 한 명씩 선택해, 4명이서 댄스를 하게 되었다. 댄스팀의 비주얼을 가능한 한 좋게 하기 위해 키의 차이가 가능한 한 작아지도록 4명을 선택하기로 했다.

1학년의 신장이 주어질 때, 네 명의 키의 최대치와 네 명의 키의 최소치의 차이의 최소를 구하는 프로그램을 작성하라.


입력

입력은 다음 형식으로 제공됩니다.

N

A_ 1 , A _2 , ..., A _N

B _1 , B _2 , ..., B _N
C _1 , C _2 , ..., C _N
D _1 , D _2 , ..., D _N

[제한]

1 ≦ N ≦ 75,000．

1 ≦ A i ≦ 10 ^9 ( 1 ≦ i ≦ N )．

1 ≦ B j ≦ 10 ^9 ( 1 ≦ j ≦ N )．

1 ≦ C k ≦ 10 ^9 ( 1 ≦ k ≦ N )．

1 ≦ D l ≦ 10 ^9 ( 1 ≦ l ≦ N )．

입력 된 모든 값은 정수입니다.


출력

「4 명의 신장의 최대치」와 「4 명의 신장의 최소치」의 차로서 생각할 수 있는 최소의 값을 1 행으로 출력하라.


부분문제

번호 점수 조건
#17점

N = 1

#223점

N ≦ 30

#314점

N≤2\,000, A_i≤10 , B_j≤10, C_k≤10, D_l≤10 (1≤i,j,k,l≤N)

#420점

N≤2\,000, A_i≤2\,000 , B_j≤2\,000, C_k≤2\,000, D_l≤2\,000 (1≤i,j,k,l≤N)

#513점

N≤2\,000

#623점

추가 제한 없음


예제1

입력
1
169
173
152
200
출력
48

N = 1 이므로 모든 학생을 선택하여 4 인조를 만들어야합니다. 이 때 4 명의 신장의 최대 값은 200 , 최소값은 152 이며, 그 차이는 200 - 152 = 48 이다. 따라서 48 을 출력합니다.

이 입력 예제는 작은 문제 1, 2, 4, 5, 6 의 제약 조건을 충족합니다.


예제2

입력
7
7994635
1111111
1111111
1111111
출력
2

이 입력 예제는 작은 문제 2, 3, 4, 5, 6 의 제약 조건을 충족합니다.


예제3

입력
7
1111211
1211111
1111211
1111112
출력
0

이 입력 예제는 작은 문제 2, 3, 4, 5, 6 의 제약 조건을 충족합니다.


예제4

입력
5
287690413420138
813873223415907
261330361747787
958672544126345
출력
70

이 입력 예제는 작은 문제 2, 4, 5, 6 의 제약 조건을 충족합니다.


예제5

입력
10
1682200811351576245013621518192522121275
1993194513121401202717051086233317871654
2257154812191031261321711866153228001497
1062117519841870205916392107133512892494
출력
79

이 입력 예는 작은 문제 2, 5, 6 의 제약 조건을 충족합니다.


출처

JOI 2023 예선2

역링크