k服务问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

假设平面上有k 辆服务车位于p1 , p2 ,…… , pk 。对这k 个服务车的服务请求序列的位置是 q1 , q2 ,…… ,qn 。当前k 个服务要按服务请求序列提出请求的先后次序响应每个服务。对服务请求qi 的响应就是从当前的k 辆服务车中选取一辆服务车j,从j 的当前位置移动到服务请求qi 的位置。响应服务请求qi 的耗费是服务车j 移动的距离。服务请求是在服务过程中一个接着一个地给出的。问如何调度最节省,即k 辆服务车在服务过程中移动的总距离最短。
对于给定的k 辆服务车以及服务请求序列q1 , q2 ,…… ,qn  ,设计一个最优调度算法,满足所有服务请求并使k 辆服务车在服务过程中移动的总距离最短。

Input

输入数据的第一行有2 个正整数k 和n(k≤10,n≤100),表示有k 辆服务车和n 个服务请求。接下来的k行中每行有2个数x 和y,表示服务车初始位置的x坐标和y 坐标。紧接着的k 行中每行也有2 个数x 和y,表示服务请求位置的x 坐标和y 坐标。

Output

将计算出的k 辆服务车移动的最短总距离输出,四舍五入保留整数部分。

Sample Input

2 5
1 0
3 0
0 0
1 0
0 0
1 0
0 0
1 0
0 0
1 0
0 0
1 0

Sample Output

3

Hint

Source