Taja는 친구들과 함께 카페 «In the cube»에 가는 것을 좋아합니다. 이 카페는 매우 편리한 주문 시스템을 갖추고 있기 때문입니다. 주문을 하려면 손님은 자동 주문대(automated stand)로 걸어가서 원하는 음식을 선택해야 합니다. 카페 내부의 특정 위치에는 여러 개의 자동 주문대가 고정되어 있습니다.

카페에는 $k$개의 테이블이 있으며, 손님들은 테이블 앞에 앉습니다. $i$번째 테이블은 최대 $c_i$명의 손님을 수용할 수 있습니다. 테이블 위치의 불편함(uncomfortableness)은 해당 테이블에서 가장 가까운 $c_i$개의 자동 주문대까지의 거리의 합으로 정의됩니다.

공식적으로, 카페는 $(0, 0)$부터 $(5000, 5000)$까지의 격자입니다. 각 칸 $(x, y)$ ($0 \le x, y \le 5000$)에는 자동 주문대 하나, 테이블 하나, 또는 아무것도 없을 수 있습니다.

두 칸 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 거리는 $|x_2 - x_1| + |y_2 - y_1|$입니다.

모든 테이블의 불편함의 총합이 최소가 되도록 테이블을 배치해야 합니다.

입력

첫 번째 줄에는 자동 주문대의 개수 $n$과 테이블의 개수 $k$ ($1 \le n \le 18$, $1 \le k \le 200$)가 주어집니다.

다음 $n$개의 줄에는 각 자동 주문대의 좌표 $x_i$와 $y_i$ ($0 \le x_i, y_i \le 5000$)가 주어집니다.

이어지는 $k$개의 줄에는 각 테이블의 수용 인원 $c_j$ ($1 \le c_j \le n$)가 주어집니다.

출력

모든 테이블의 불편함의 총합의 최솟값을 하나의 정수로 출력하십시오.

예제

입력 1

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

출력 1

20

입력 2

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

출력 2

16

참고

첫 번째 예제에 대한 가능한 테이블 배치 예시는 다음과 같습니다.