[USACO16DEC]Cow Checklist G

题目描述

每天，面条老师走过他的牧场，检查他的每头奶牛的存在感。在他的农场，他有两个品种的牛，H和G。他的H方便地编号为$1 \ldots H$，G方便地编号为$1 \ldots G$($1 \leq H \leq 1000, 1 \leq G \leq 1000$)。每个牛位于2D平面中的点（不一定是不同的）。

面条老师从H 1出发，在H H结束。他想要沿途参观每头牛，为了方便保持他到目前为止访问的牛的清单，他想按他们的编号顺序访问H和G。在他访问的所有$H+G$头牛的序列中，H编号为$1 \ldots H$应该显示为（不一定是连续的）子序列，对于G也相同。换句话说，所有$H+G$牛的序列应该通过将编号为$1 \ldots H$的H列表与编号为$1 \ldots G$的G列表交错形成。

当面条老师从一头母牛移动到另一头母牛，行进距离为$D$时，他消耗$D^2$能量。请帮助他确定访问所有奶牛所需的最低能量。

输入格式

输入的第一行包含两个整数，$H$ 和 $G$

接下来的 $H$ 行，每行包含 $x$ 和 $y$ 两个整数，表示H的坐标。

接下来的 $G$ 行, 每行包含 $x$ 和 $y$ 两个整数，表示G的坐标。

每个坐标都是 $0 \ldots 1000$之间的整数.

输出格式

输出包括一行，为访问所有奶牛所需的最低能量。

样例 #1

样例输入 #1

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

样例输出 #1

20