Bò nhảy rất kém. Nhưng Farmer John phát hiện bò duyên dáng thường cho nhiều sữa hơn, nên đăng ký cả đàn học khiêu vũ. Buổi đầu cần ghép $N$ bò đực ($1\le N\le1{,}000$) và $N$ bò cái thành đôi. Đôi tốt có chiều cao gần nhau, chênh lệch nhỏ. Cho mọi chiều cao, tìm cách ghép làm nhỏ nhất tổng chênh lệch chiều cao của các đôi.

Dữ liệu vào

• Dòng 1: nguyên $N$.
• Dòng $2..N+1$: mỗi dòng nguyên là chiều cao một bò đực.
• Dòng $N+2..2N+1$: mỗi dòng nguyên là chiều cao một bò cái.

Dữ liệu ra

• Dòng 1: số nguyên, tổng chênh lệch của ghép tối ưu.

Ví dụ

Dữ liệu vào 1

4
2
8
5
5
1
4
10
7

Dữ liệu ra 1

6

Ghi chú

Dữ liệu vào

4 bò đực cao 2,8,5,5; 4 bò cái cao 1,4,10,7.

Giải thích — Dữ liệu ra

Các đôi tốt nhất theo chiều cao: 2-1, 8-10, 5-4, 5-7. Tổng chênh lệch 6.

Tác giả: Brian Dean, 2004