<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$ |
| 6 | 26 | No additional restrictions. |
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