Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Đó là điệu nhảy mùa xuân trong một lần hiếm hoi ~N~ con bò đực đã được mời nhảy với ~M~ con bò cái (miễn là chúng giữ được hành vi tốt nhất của chúng).

Nông dân John, gần như bị ám ảnh trong tổ chức các điệu nhảy của mình, muốn cảnh tượng đó hấp dẫn nhất có thể. Vì vậy, anh ta muốn ghép cặp ~N~ bò đực với các đối tác bò cái sao cho tổng số tất cả các khác biệt về chiều cao của các cặp được giảm thiểu. Bò đực có chiều cao ~B_i~ và bò cái có chiều cao ~C_i~.

Tất nhiên, một số con bò cái sẽ không thể ghép cặp được vì ~N \lt M~. Những con bò cái đó ta không tính vào đáp án.

Dữ liệu vào

• Dòng 1: Hai số nguyên được phân tách bằng dấu cách: ~N~ và ~M~.
• Dòng ~2..N + 1~: Dòng ~i + 1~ chứa một số nguyên duy nhất: ~B_i~.
• Dòng ~N + 2..M + N + 1~: Dòng ~i + N + 1~ chứa một số nguyên duy nhất: ~C_i~.

Kết quả

• Một số nguyên duy nhất là tổng tối thiểu của giá trị tuyệt đối chênh lệch chiều cao.

Giới hạn

• ~1 \le N \le 5000~; ~N \lt M \le 5000~; ~1 \le C_i \le 1\,000\,000~; ~1 \le B_i \le 1\,000\,000~.

Sample Input 1

5 7
10 16 12 10 13
7 17 12 10 9 6 11

Sample Output 1

4

Nguồn: VinhDinhCoder.