Taja lubi chodzić ze znajomymi do kawiarni „In the cube”, ponieważ ma ona bardzo wygodny system składania zamówień. Aby złożyć zamówienie, gość powinien podejść do automatycznego stanowiska i wybrać dowolne dania, na które ma ochotę. W kawiarni znajduje się kilka takich stanowisk, a wszystkie są zamocowane w określonych miejscach.

W kawiarni goście siedzą przy stolikach; dostępnych jest $k$ stolików. $i$-ty stolik może obsłużyć nie więcej niż $c_i$ osób. Niekomfortowość położenia stolika jest sumą odległości od tego stolika do $c_i$ najbliższych mu automatycznych stanowisk.

Formalnie, kawiarnia to siatka $(0, 0) - (5000, 5000)$. Każda komórka $(x, y)$ ($0 \le x, y \le 5000$) może zawierać albo pojedyncze automatyczne stanowisko, albo pojedynczy stolik, albo nic.

Odległość między komórkami $(x_1, y_1)$ oraz $(x_2, y_2)$ wynosi $|x_2 - x_1| + |y_2 - y_1|$.

Twoim zadaniem jest rozmieszczenie stolików w taki sposób, aby całkowita suma niekomfortowości dla wszystkich stolików była minimalna.

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite $n$ oraz $k$ ($1 \le n \le 18$, $1 \le k \le 200$) — odpowiednio liczbę automatycznych stanowisk oraz liczbę stolików.

Następne $n$ linii zawiera współrzędne $i$-tego stanowiska: dwie liczby całkowite $x_i$ oraz $y_i$ ($0 \le x_i, y_i \le 5000$).

Kolejne $k$ linii zawiera po jednej liczbie całkowitej $c_j$ ($1 \le c_j \le n$) — liczbę miejsc przy $j$-tym stoliku.

Wyjście

Wyjście powinno zawierać jedną liczbę całkowitą — minimalną całkowitą niekomfortowość.

Przykład

Wejście 1

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

Wyjście 1

20

Wejście 2

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

Wyjście 2

16

Uwagi

Możliwe rozmieszczenie stolików dla pierwszego przykładu wygląda następująco: