题目描述

Every day, Farmer John walks through his pasture to check on the well-being ofeach of his cows. On his farm he has two breeds of cows, Holsteins andGuernseys. His $H$ Holsteins are conveniently numbered $1 \ldots H$, and his$G$ Guernseys are conveniently numbered $1 \ldots G$($1 \leq H \leq 1000, 1 \leq G \leq 1000$). Each cow is located at a point inthe 2D plane (not necessarily distinct).

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

Farmer John starts his tour at Holstein 1, and ends at Holstein $H$. He wantsto visit each cow along the way, and for convenience in maintaining hischecklist of cows visited so far, he wants to visit the Holsteins and Guernseysin the order in which they are numbered. In the sequence of all $H+G$ cows hevisits, the Holsteins numbered $1 \ldots H$ should appear as a (not necessarilycontiguous) subsequence, and likewise for the Guernseys. Otherwise stated, thesequence of all $H+G$ cows should be formed by interleaving the list ofHolsteins numbered $1 \ldots H$ with the list of Guernseys numbered$1 \ldots G$.

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

When FJ moves from one cow to another cow traveling a distance of $D$, heexpends $D^2$ energy. Please help him determine the minimum amount of energyrequired to visit all his cows according to a tour as described above.

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

输入格式

The first line of input contains $H$ and $G$, separated by a space.

The next $H$ lines contain the $x$ and $y$ coordinates of the $H$ Holsteins, and the next $G$ lines after that contain coordinates of the Guernseys. Each

coordinate is an integer in the range $0 \ldots 1000$.

输出格式

Write a single line of output, giving the minimum energy required for FJ's tour of all the cows.

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

20

提示

感谢@e169887125 提供翻译