31340번 - In the cube 다국어

문제

Taja likes to go to the cafe <<In the cube>> with her friends, since it has very convenient ordering system. To make an order, guest should walk to the automated stand and choose any dishes they likes. There are several such stands and they all are fixed at specific place inside the cafe.

In the cafe guests sit in front of tables, there are $k$ tables. $i$th table cannot serve more than $c_i$ persons. Uncomfortableness of the table position is the sum of the distances from this table to $c_i$ automated stands closest to it.

Formally, cafe is the grid $(0, 0)-(5000, 5000)$. Each cell $(x, y)$ (0ドル \leq x, y \leq 5,000円$) can contain either single automated stand or single table or nothing.

The distance between cells $(x_1, y_1)$ and $(x_2, y_2)$ equals to $|x_2 - x_1| + |y_2 - y_1|$.

You are to arrange the tables in such a way, that total sum of uncomfortablenesses for all tables should be minimal.

입력

First line of the input contains two integers $n$ and $k$ (1ドル \leq n \leq 18,ドル 1ドル \leq k \leq 200$) --- amount of automated stands and tables correspondingly.

Following $n$ lines contain coordinates of $i$th stand: two integers $x_i$ and $y_i$ (0ドル \leq x_i, y_i \leq 5,円 000$).

Next of each $k$ lines contain single integer $c_j$ (1ドル \leq c_j \leq n$) --- number of seats at $j$th table.

출력

Output should contain single integer --- minimal total uncomfortableness.

제한

힌트

Possible arrangement of the tables for the first sample looks like this: