Mỗi ngày, Farmer John đi qua đồng cỏ để kiểm tra tình trạng của từng con bò. Trang trại của ông có hai giống bò là Holstein và Guernsey. \(H\) con bò Holstein được đánh số thuận tiện từ \(1 \ldots H\), còn \(G\) con bò Guernsey được đánh số thuận tiện từ \(1 \ldots G\) (\(1 \leq H \leq 1000\), \(1 \leq G \leq 1000\)). Mỗi con bò nằm tại một điểm trên mặt phẳng hai chiều (các điểm không nhất thiết phân biệt).

Farmer John bắt đầu chuyến đi tại bò Holstein \(1\) và kết thúc tại bò Holstein \(H\). Trên đường đi, ông muốn thăm từng con bò; để thuận tiện cho việc cập nhật danh sách những con bò đã thăm, ông muốn thăm các bò Holstein và Guernsey theo thứ tự đánh số. Trong dãy gồm tất cả \(H+G\) con bò mà ông thăm, các bò Holstein được đánh số \(1 \ldots H\) phải xuất hiện như một dãy con (không nhất thiết liên tiếp), và các bò Guernsey cũng vậy. Nói cách khác, dãy gồm tất cả \(H+G\) con bò phải được tạo thành bằng cách xen kẽ danh sách bò Holstein đánh số \(1 \ldots H\) với danh sách bò Guernsey đánh số \(1 \ldots G\).

Khi Farmer John di chuyển từ một con bò sang một con bò khác qua khoảng cách \(D\), ông tiêu tốn \(D^2\) năng lượng. Hãy giúp ông xác định lượng năng lượng nhỏ nhất cần để thăm tất cả đàn bò theo một chuyến đi như mô tả ở trên.

Dữ liệu vào

Dòng đầu tiên chứa \(H\) và \(G\), cách nhau bởi một dấu cách.

\(H\) dòng tiếp theo chứa tọa độ \(x\), \(y\) của \(H\) con bò Holstein; \(G\) dòng sau đó chứa tọa độ của các bò Guernsey. Mỗi tọa độ là một số nguyên trong khoảng \(0 \ldots 1000\).

Dữ liệu ra

In một dòng chứa lượng năng lượng nhỏ nhất cần cho chuyến đi thăm tất cả đàn bò của Farmer John.

Ví dụ

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

20

Nguồn

USACO 2016 December Contest, Gold — Cow Checklist. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=670