Bitaro đã yêu thích việc làm vườn từ nhiều năm nay. Bắt đầu từ mùa xuân này, cậu dự định trồng một loại cây tên là củ cải Bita.

Bitaro đã chuẩn bị \(2N\) cây giống củ cải Bita, được đánh số từ \(1\) đến \(2N\), và sẽ xếp chúng theo đúng thứ tự đó để trồng. Kích thước của cây giống \(i\) \((1 \le i \le 2N)\) là \(A_i\). Để mọi cây đều nhận đủ ánh sáng, kích thước của chúng thỏa mãn:

• \(A_1 \le A_2 \le \cdots \le A_N \le A_{N+1}\).
• \(A_{N+1} \ge A_{N+2} \ge \cdots \ge A_{2N-1} \ge A_{2N} \ge A_1\).

Như vậy, cây giống \(1\) có kích thước nhỏ nhất và cây giống \(N+1\) có kích thước lớn nhất.

Bitaro cũng đã chuẩn bị \(N\) chậu màu đỏ và \(N\) chậu màu xanh lam. Chậu đỏ thứ \(j\) \((1 \le j \le N)\) có kích thước \(B_j\); chậu xanh lam thứ \(k\) \((1 \le k \le N)\) có kích thước \(C_k\). Cậu trồng một cây giống vào mỗi chậu trong số \(2N\) chậu này, rồi xếp các chậu thành một hàng sao cho các cây giống xuất hiện theo thứ tự \(1,2,\ldots,2N\).

Để đẹp mắt, các chậu phải được xếp theo một thứ tự đẹp: tồn tại \(N\) chậu liên tiếp cùng màu. Chính xác hơn, thứ tự được gọi là đẹp khi và chỉ khi tồn tại số nguyên \(l\), \(1 \le l \le N+1\), sao cho các chậu chứa cây giống \(l,l+1,\ldots,l+N-1\) đều có cùng màu.

Khi trồng cây giống có kích thước \(y\) vào chậu có kích thước \(x\), độ khó chăm sóc của cặp đó là \(|x-y|\). Khối lượng công việc của Bitaro là độ khó chăm sóc lớn nhất trong \(2N\) cặp chậu và cây giống.

Cho thông tin về các cây giống và các chậu, hãy tìm khối lượng công việc nhỏ nhất có thể khi trồng cây sao cho thứ tự các chậu là đẹp.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N
A_1 A_2 ... A_{2N}
B_1 B_2 ... B_N
C_1 C_2 ... C_N

Dữ liệu ra

In một số trên một dòng ra đầu ra chuẩn: khối lượng công việc nhỏ nhất có thể của Bitaro khi trồng cây sao cho thứ tự các chậu là đẹp.

Ràng buộc

• \(1 \le N \le 300\,000\).
• \(1 \le A_i \le 10^9\) \((1 \le i \le 2N)\).
• \(1 \le B_j \le 10^9\) \((1 \le j \le N)\).
• \(1 \le C_k \le 10^9\) \((1 \le k \le N)\).
• \(A_1 \le A_2 \le \cdots \le A_N \le A_{N+1}\).
• \(A_{N+1} \ge A_{N+2} \ge \cdots \ge A_{2N-1} \ge A_{2N} \ge A_1\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (4 điểm): \(N \le 5\).
• Nhóm 2 (5 điểm): \(N \le 10\).
• Nhóm 3 (21 điểm): \(N \le 2\,000\).
• Nhóm 4 (37 điểm): Các giá trị \(A_i\) đôi một khác nhau và \(A_N < A_{2N}\).
• Nhóm 5 (33 điểm): Không có ràng buộc bổ sung.

Ví dụ

2
1 2 6 3
2 5
4 3

2

9
1 2 3 4 5 6 7 8 9 18 17 16 15 14 13 12 11 10
2 7 4 1 7 6 4 10 6
6 8 9 3 7 1 9 5 4

8

7
13 16 18 18 21 22 22 23 23 21 19 17 15 14
14 14 20 19 22 17 25
24 15 18 25 24 19 11

3

Nguồn

Nguồn: JOI 2023/2024, kỳ thi tuyển chọn mùa xuân, ngày thi thứ hai (22/03/2024). Đề bài của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.