Taja aime se rendre au café « In the cube » avec ses amis, car il dispose d'un système de commande très pratique. Pour passer une commande, le client doit se rendre à une borne automatisée et choisir les plats qu'il souhaite. Il existe plusieurs bornes de ce type, toutes fixées à des emplacements précis à l'intérieur du café.

Dans le café, les clients s'assoient devant des tables ; il y a $k$ tables. La $i$-ème table ne peut pas servir plus de $c_i$ personnes. L'inconfort de la position d'une table est la somme des distances entre cette table et les $c_i$ bornes automatisées les plus proches d'elle.

Formellement, le café est une grille $(0, 0) - (5000, 5000)$. Chaque cellule $(x, y)$ ($0 \le x, y \le 5000$) peut contenir soit une borne automatisée, soit une table, soit rien.

La distance entre les cellules $(x_1, y_1)$ et $(x_2, y_2)$ est égale à $|x_2 - x_1| + |y_2 - y_1|$.

Vous devez disposer les tables de telle sorte que la somme totale des inconforts pour toutes les tables soit minimale.

Entrée

La première ligne de l'entrée contient deux entiers $n$ et $k$ ($1 \le n \le 18$, $1 \le k \le 200$), représentant respectivement le nombre de bornes automatisées et le nombre de tables.

Les $n$ lignes suivantes contiennent les coordonnées de la $i$-ème borne : deux entiers $x_i$ et $y_i$ ($0 \le x_i, y_i \le 5000$).

Chacune des $k$ lignes suivantes contient un entier unique $c_j$ ($1 \le c_j \le n$), représentant le nombre de places à la $j$-ème table.

Sortie

La sortie doit contenir un seul entier : l'inconfort total minimal.

Exemples

Entrée 1

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

Sortie 1

20

Entrée 2

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

Sortie 2

16

Remarque

Une disposition possible des tables pour le premier exemple ressemble à ceci :