LG#P1678. 烦恼的高考志愿

烦恼的高考志愿

P1678 烦恼的高考志愿

题目描述

\hspace{15pt}计算机竞赛小组的神牛 V 神终于结束了高考,然而作为班长的他还不能闲下来。班主任老 t 给了他一个艰巨的任务:帮同学找出最合理的大学填报方案。可是 V 神太忙了,身后还有一群小姑娘等着和他约会,于是他想到了同为计算机竞赛小组的你,请你帮他完成这个艰巨的任务。

\hspace{15pt}现有 mm 所学校,其中第 ii 所学校的预计分数线为 aia_i;有 nn 位学生,其中第 ii 位学生的估分为 bib_i。

\hspace{15pt}根据 nn 位学生的估分情况,分别给每位学生推荐一所学校,要求学校的预计分数线与学生的估分相差最小(可高可低,毕竟是估分嘛),这个最小值称为这位学生的不满意度。请求出所有学生的不满意度之和。

输入格式

\hspace{15pt}第一行输入两个整数 m,n(1≦m,n≦105)m,n \left(1 \leqq m,n \leqq 10^5\right),分别代表学校数量和学生数量。

\hspace{15pt}第二行输入 mm 个整数 $a_1,a_2,\dots,a_m \left(0 \leqq a_i \leqq 10^6\right)$,分别代表 mm 所学校的预计分数线。

\hspace{15pt}第三行输入 nn 个整数 $b_1,b_2,\dots,b_n \left(0 \leqq b_i \leqq 10^6\right)$,分别代表 nn 位学生的估分。

输出格式

\hspace{15pt}在一行上输出一个整数,代表所有学生的不满意度之和。

测试样例

4 3
513 598 567 689
500 600 550

32

数据范围与提示

\hspace{15pt}对于 30%30\% 的数据,1≦n,m≦1031 \leqq n,m \leqq 10^3,0≦ai,bi≦1040 \leqq a_i,b_i \leqq 10^4;

\hspace{15pt}对于 100%100\% 的数据,1≦n,m≦1051 \leqq n,m \leqq 10^5,0≦ai,bi≦1060 \leqq a_i,b_i \leqq 10^6。