J. Egg Placement
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Beggsie the chicken needs you to solve a problem in Farmer John's farm. The farm can be represented as a two dimensional grid. Further, there are $$$n$$$ eggs on the farm, where the $$$i$$$th egg is at position $$$(x_i, y_i)$$$.

The compactness of the farm can be represented by the sum of Manhattan distances between each pair of eggs. Formally, if $$$(x_i', y_i')$$$ is the current position of the $$$i$$$th egg, then the compactness given by $$$\sum\limits_{i=1}^n \sum\limits_{j=i+1}^n (|x_i' - x_j'| + |y_i' - y_j'|)$$$.

There are $$$d$$$ days, and during the $$$i$$$th day there are $$$s_i$$$ seconds. During each second, Beggsie can choose to move a single egg in one of the four cardinal directions, or to not move anything. Now, let $$$c_i$$$ be the compactness of the farm after day $$$i$$$. Farmer John wants Beggsie to minimize the value of $$$\sum\limits_{i=1}^d c_i$$$. Please help Beggsie by finding the minimum such value!

Input

The first line of input will contain $$$n$$$, $$$d$$$. ($$$1 \leq n, d \leq 2 \cdot 10^5$$$) — the number of eggs in the farm, and the number of days during which Beggsie can move eggs.

The $$$i$$$th of the next $$$n$$$ lines of input will contain $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq 10^6$$$) — the position of the $$$i$$$th egg in the farm.

The last line of input will contain $$$d$$$ space-separated integers $$$s_1, s_2, \cdots, s_n$$$ ($$$1 \leq s_i \leq 10^6$$$) — the number of seconds in each day.

Output

Output a single integer, denoting the minimum value of $$$\sum\limits_{i=1}^d c_i$$$. Since this integer may be extremely large, output it modulo $$$998244353$$$.

Examples
Input
2 3
1 1
4 3
1 1 1
Output
9
Input
3 3
3 1
2 1
5 1
2 1 1
Output
2
Input
5 3
1 1
4 5
6 3
2 3
9 8
3 4 7
Output
126