Taja thích đến quán cà phê «In the cube» cùng bạn bè vì quán có hệ thống gọi món rất tiện lợi. Để đặt món, khách hàng cần đi đến quầy tự động và chọn bất kỳ món ăn nào họ thích. Có một vài quầy như vậy và tất cả đều được cố định tại các vị trí cụ thể bên trong quán.

Trong quán, khách ngồi trước các bàn, có $k$ cái bàn. Bàn thứ $i$ không thể phục vụ quá $c_i$ người. Độ khó chịu của vị trí đặt bàn là tổng khoảng cách từ bàn này đến $c_i$ quầy tự động gần nó nhất.

Về mặt hình thức, quán cà phê là một lưới $(0, 0) - (5000, 5000)$. Mỗi ô $(x, y)$ ($0 \le x, y \le 5000$) có thể chứa một quầy tự động, một cái bàn hoặc để trống.

Khoảng cách giữa hai ô $(x_1, y_1)$ và $(x_2, y_2)$ bằng $|x_2 - x_1| + |y_2 - y_1|$.

Bạn cần sắp xếp các bàn sao cho tổng độ khó chịu của tất cả các bàn là nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $k$ ($1 \le n \le 18, 1 \le k \le 200$) — số lượng quầy tự động và số lượng bàn tương ứng.

$n$ dòng tiếp theo chứa tọa độ của quầy thứ $i$: hai số nguyên $x_i$ và $y_i$ ($0 \le x_i, y_i \le 5000$).

$k$ dòng tiếp theo, mỗi dòng chứa một số nguyên $c_j$ ($1 \le c_j \le n$) — số lượng chỗ ngồi tại bàn thứ $j$.

Dữ liệu ra

Dữ liệu ra chỉ chứa một số nguyên duy nhất — tổng độ khó chịu nhỏ nhất.

Ví dụ

Ví dụ 1

3 4
1 2
4 1
5 4
1
2
3
3

Kết quả 1

20

Ví dụ 2

2 10
0 0
5000 5000
1
1
1
1
1
1
1
1
1
1

Kết quả 2

16

Ghi chú

Cách sắp xếp các bàn có thể có cho ví dụ đầu tiên trông như sau: