HỆ THỐNG ĐIỆN

Nhận được sự đầu tư lớn của một tập đoàn nước ngoài, đất nước Omega dự định xây dựng k  nhà máy thủy điện tại k địa điểm khác nhau để cung cấp điện cho n thành phố. Các nhà máy thủy điện được đánh số thứ tự từ 1 đến k, chi phí xây dựng cho nhà máy thủy điện thứ i là w_i. Tuy nhiên họ cần phải tính toán để chi phí xây dựng và lắp đặt hệ thống điện lưới quốc gia là ít nhất.

Hệ thống điện lưới được mô tả như một bản đồ được chia thành các ô vuông đơn vị mà tọa độ đỉnh của các ô vuông là một cặp số nguyên (x,y) cho biết hoành độ và tung độ của nó. Các nhà máy thủy điện và các thành phố đều nằm trên đỉnh của ô vuông đơn vị. Chi phí lắp đặt đường dây điện giữa hai điểm (u, v) và (s, t) được tính bằng giá trị |u-s|+|v-t|

Hãy tính toán chi phí ít nhất để xây dựng hệ thống điện cho đất nước Omega sao cho tất cả các thành phố đều có điện biết rằng thành phố có điện khi có đường dây điện đến ít nhất một thành phố có điện khác hoặc có đường dây điện nối trực tiếp nhà máy thủy điện.

Lưu ý: không cần thiết phải xây dựng hết k  nhà máy thủy điện

Dữ liệu: Vào từ tệp văn bản ELECTRIC.INP

+ Dòng đầu tiên gồm 2 số nguyên dương k và n lần lượt là số lượng các nhà máy thủy điện và số lượng thành phố.

+ K dòng tiếp theo dòng thứ i (i=1..k) gồm 3 số nguyên x_i , y_i, w_i cho biết nhà máy thủy điện thứ i nằm ở tọa độ (x_i, y_i) và chi phí xây dựng là w_i

+ N dòng tiếp theo mỗi dòng thứ j (j=1..n) chứa 2 số nguyên u_j, v_j cho biết hoành độ và tung độ của thành phố thứ j.

Dữ liệu ra: ghi vào tệp văn bản ELECTRIC.OUT một số nguyên cho biết chi phí ít nhất để xây dựng hệ thống điện lưới cho nước Omega.

Giới hạn:

+ 1≤n≤200

+ 1≤k≤n

+ Tọa độ của các thành phố và nhà máy thủy điện có trị tuyệt đối ≤10⁶

+ 1≤w_i≤10⁶

Các số trên một dòng của Input cách nhau ít nhất 1 ký tự trắng.

Ví dụ:

ELECTRIC.INP	ELECTRIC.OUT
3 7 1 1 10 4 7 20 9 3 15 1 6 2 3 5 1 5 5 7 3 8 1 8 7	37