P2848 [USACO16DEC] Cow Checklist G

题目描述

每天，Farmer John 都会穿过他的牧场，检查每头奶牛的健康状况。他的农场里有两类奶牛：荷斯坦牛和根西牛。他的 $H$ 头荷斯坦牛被方便地编号为 $1 \ldots H$，而他的 $G$ 头根西牛被方便地编号为 $1 \ldots G$（$1 \leq H \leq 1000, 1 \leq G \leq 1000$）。每头奶牛都位于二维平面中的一个点（不一定不同）。

Farmer John 从荷斯坦牛 1 开始他的巡视，并在荷斯坦牛 $H$ 结束。他希望沿途访问每头奶牛，并且为了方便维护他已经访问过的奶牛清单，他希望按照编号顺序访问荷斯坦牛和根西牛。在他访问的所有 $H+G$ 头奶牛的序列中，编号为 $1 \ldots H$ 的荷斯坦牛应作为一个（不一定连续的）子序列出现，同样地，编号为 $1 \ldots G$ 的根西牛也应如此。换句话说，所有 $H+G$ 头奶牛的序列应通过将编号为 $1 \ldots H$ 的荷斯坦牛列表与编号为 $1 \ldots G$ 的根西牛列表交错排列而成。

当 Farmer John 从一头奶牛移动到另一头奶牛，移动距离为 $D$ 时，他会消耗 $D^2$ 的能量。请帮助他确定按照上述巡视方式访问所有奶牛所需的最小能量。

输入格式

输入的第一行包含用空格分隔的 $H$ 和 $G$。

接下来的 $H$ 行包含 $H$ 头荷斯坦牛的 $x$ 和 $y$ 坐标，随后的 $G$ 行包含根西牛的坐标。每个坐标都是 $0 \ldots 1000$ 范围内的整数。

输出格式

输出一行，表示 Farmer John 巡视所有奶牛所需的最小能量。

输入输出样例 1

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

20