P1678 Troubles with Gaokao Choices

The ace of the computer competition club, V Shen, has finally finished the Gaokao. However, as the class monitor, he still cannot take a break. His homeroom teacher, Lao t, gave him a daunting task: help his classmates find the most reasonable college application plan. But V Shen is too busy, with a group of girls waiting to date him, so he turned to you, a fellow member of the computer competition club, to help complete this task.

There are $m$ schools, each with an expected cutoff score $a_i$. There are $n$ students, with estimated scores $b_i$. Based on the estimated scores of the $n$ students, recommend one school to each student such that the difference between the school’s expected cutoff score and the student’s estimated score is minimized (either higher or lower—after all, it’s just an estimate). This minimum difference is called dissatisfaction. Find the minimum possible sum of dissatisfaction over all students.

The first line contains two integers $m, n$. The second line contains $m$ numbers, representing the expected cutoff scores of the $m$ schools. The third line contains $n$ numbers, representing the estimated scores of the $n$ students.

Output one line, the minimum sum of dissatisfaction.

Constraints: For $30\%$ of the testdata, $1 \le n, m \le 10^3$, and the estimated scores and cutoffs are $\le 10^4$. For $100\%$ of the testdata, $1 \le n, m \le 10^5$, the estimated scores and cutoffs are $\le 10^6$, and all are non-negative integers. Translated by ChatGPT 5