开始: 2023-05-16 00:00:00

蒟蒻WKY的比赛

结束: 2023-05-18 12:30:00
当前  2025-06-06 11:59:41  类型: IOI  状态: 已经结束 

P2. 任务
描述

旅行者走在提瓦特大陆上~~~

TA接下来有 n 个任务要做,第 i 个任务所要到达的地点坐标为(x_i, y_i)

旅行者从坐标 (sx, sy) 处出发,需要依次到达这 n 个地点。地点 u 到地点 v 花费的代价为他们之间的曼哈顿距离

当然,大陆上有 m 座传送锚点,第 i 座锚点的坐标为(a_i, b_i)。

旅行者可以以 0 的代价在任何时候,任何地点传送到任意一座锚点。

求旅行者完成所有任务需要的最小花费。

输入

第一行两个正整数 n,m。

第二行包含两个整数 sx, sy。

接下来的 n 行每行包含两个整数 x_i, y_i 为第 i 个任务的地点坐标。

再接下来的 m 行每行包含两个整数 a_i, b_i 为第 i 个传送锚点的坐标。

输出

完成所有任务的最小花费。

样例

输入

3 3
0 0
1 1
1 2
10000 10000
100001 100001
1000 100
10000 10000

输出

3
提示

对于 20% 的数据,保证 1≤ n, m ≤ 100。

对于 100% 的数据,保证 1≤ n, m ≤ 1000, -10^9 ≤ a_i, b_i, x_i, y_i ≤ 10^9。

提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交