1869: 山区建小学
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：1
解决：1
题目描述
政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di（为正整数），其中，0 < i < m。为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学（设 0 < n < = m < 500 ）。
请根据给定的m、n以及所有村庄的位置，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。
请根据给定的m、n以及所有村庄的位置，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。
输入
第1行为m和n，其间用空格间隔。
第2行为m个正整数，依次表示从左到右的所有村庄的位置坐标，相邻两数之间以空格间隔。
第2行为m个正整数，依次表示从左到右的所有村庄的位置坐标，相邻两数之间以空格间隔。
输出
各村庄到最近学校的距离之和的最小值。
样例输入
10 2
1 2 3 4 5 6 7 8 9 10样例输出
12提示
如果要在一段连续的N个村庄间建一所小学的话，则最佳地点一定是建在正中间的那个村庄即第(N+1)/2个村庄。