# Statues

Time limit: 1s Memory limit: 512MB Input: Output:

<Link /> wants to get his hands on a new C chart, that can only be found on The Isle of <meta>, inside The Temple of <element>. To get inside the Temple, he must solve a puzzle first.

<Link /> must first enter a $T$-dimensional plane, therefore every point in space would be described by an array of length $T: [x_1,x_2,x_3, \dots, x_T]$. In this plane, there are $N$ stationary statues numbered from $1$ to $N$ and $Q$ mobile statues numbered from $1$ to $Q$. <Link /> can make the following move at most $K$ times: he can choose any mobile statue and an axis and move that statue by exactly one unit in any direction. That is, the coordinate of such statue will become either $[x_1,x_2, \dots,x_i−1,\dots,x_T]$ or $[x_1,x_2,\dots,x_i+1,\dots, x_T]$.

To unlock the entrance to The Temple of <element>, he must move the mobile statues in such a way that the sum of the Manhattan distances between every mobile statue and every stationary statue is minimized.

The Manhattan distance between two $T$-dimensional points $[x_1,x_2,\dots,x_T]$ and $[y_1,y_2,\dots,y_T]$ is defined as:

$dist([x_1, x_2, \dots, x_T], [y_1, y_2, \dots, y_T]) = \displaystyle \sum_{i = 1}^{T} |x_i - y_i|$

Let $s$ be the array with the coordinates of each stationary statue and $m$ the array with the coordinates of each mobile statue after making at most $K$ moves optimally. You are required to compute:

$\displaystyle \sum_{i = 1}^{N} \sum_{j = 1}^{Q} dist(s_i, m_j)$

## Input

The first line of input will contain the integers $N, T, K$ which represent the number of stationary statues, the number of dimension and the number of moves that <Link /> can make.

On each of the next $N$ lines, there will be $T$ space-separated integers. The $i$-th line of these represents the coordinates of the $i$-th stationary statue.

On the next line, there will be a single integer $Q$ representing the number of mobile statues.

On each of the next $Q$ lines, there will be $T$ space-separated integers, representing the coordinates of each mobile statue, in a similar fashion as with the stationary statues.

## Output

Output a single integer representing the minimum sum of Manhattan distances from every stationary statue to every mobile statue after making at most $K$ moves.

## Constraints and notes

• $1 \leq N, Q \leq 100 \ 000$
• $1 \leq T \leq 10$
• $1 \leq K \leq 10^{15}$
• All the coordinates are integers between $0$ and $10^9$ inclusive.
• It is guaranteed that the answer fits in a 64-bit signed integer.
# Points Constraints
1 7 $T = Q = 1$
2 10 $N, Q, K \leq 100$
3 12 $N, Q \leq 50$
4 28 $T = 1$
5 17 $Q = 1$

## Example 1

stdin

3 2 7
8 1
2 0
0 3
2
10 2
2 6


stdout

29


## Example 2

stdin

6 4 200
12 1 19 10
45 3 42 44
42 32 40 41
39 12 32 47
35 18 40 20
38 14 25 1
3
34 10 7 9
29 32 21 50
16 36 18 38


stdout

708