计程车派单

题目描述

Y 同学是一家出租车公司的老板，他手下拥有 $M$ 台出租车。这些出租车停靠在一条笔直的公路（可以视为 $x$ 轴）上，其坐标分别为 $T_1, T_2, \ldots, T_M$。

同时，Y 同学接到了 $M$ 名乘客的打车请求，这 $M$ 名乘客也位于同一条公路上，坐标分别为 $P_1, P_2, \ldots, P_M$。

题目保证上述的 $2M$ 个坐标均互不相同。

Y 同学的任务是为每一位乘客恰好指派一台出租车，同时保证每台出租车只被指派给一位乘客。他的目标是最小化“总接驾距离”，即所有出租车到其被指派的乘客位置的距离之和。

形式化地讲，假设存在一个 $1$ 到 $M$ 的排列 $j_1, j_2, \ldots, j_M$，表示第 $i$ 台出租车被指派给第 $j_i$ 位乘客。Y 同学希望最小化以下函数的值：

请你编写程序，帮助 Y 同学求出能够达到的最小总接驾距离。

输入格式

第一行包含一个正整数 $M$，表示出租车和乘客的数量。 第二行包含 $M$ 个正整数 $T_1, T_2, \ldots, T_M$，表示每一台出租车的坐标。 第三行包含 $M$ 个正整数 $P_1, P_2, \ldots, P_M$，表示每一位乘客的坐标。

输出格式

输出一行一个整数，表示给定输入下的最小总接驾距离。

样例

样例输入 #1

5
3 2 1 5 4
8 6 10 9 7

样例输出 #1

25

样例输入 #2

5
10 70 30 90 50
71 31 51 91 11

样例输出 #2

5

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le M \le 10^6$
• $1 \le T_i, P_i \le 2 \times 10^6$
• 输入的 $2M$ 个坐标均互不相同。