Statues — RMI contest
Task type: batch | Time limit: 1 s | Memory limit: 512 MB | Difficulty: 25
Algorithms: data structures, greedy, coordinate compression, mathematical optimization

# Statues

Time limit: *1000 ms*
Memory limit: *512 MB*

`<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, ..., 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 `i` (from 1 to T) and move that statue by exactly one unit along that axis. That is, the coordinate `x_i` for that statue will become either `x_i - 1` or `x_i + 1`, changing the statue's position from `[x_1, x_2, ..., x_i, ..., x_T]` to either `[x_1, x_2, ..., x_i - 1, ..., x_T]` or `[x_1, x_2, ..., x_i + 1, ..., 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, ..., x_T]` and `[y_1, y_2, ..., y_T]` is defined as:

`dist([x_1, ..., x_T], [y_1, ..., y_T]) = |x_1 - y_1| + |x_2 - y_2| + ... + |x_T - y_T|`
(This is the sum of the absolute differences of their coordinates along each dimension).

Let `s` be the array containing the coordinates of each **stationary** statue and `m` be the array containing the coordinates of each **mobile** statue after making the (at most) K moves optimally. You are required to compute the minimum possible value of:

`Sum_{i=1 to N} Sum_{j=1 to Q} dist(s_i, m_j)`

(This is the sum of the Manhattan distances over all pairs of stationary statue `s_i` and final mobile statue `m_j`).

## Standard input

The first line of input will contain the integers N, T, K, which represent the number of stationary statues, the number of dimensions, and the maximum number of moves `<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 initial coordinates of each **mobile** statue, in a similar fashion as with the **stationary** statues.

## Standard 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 optimally.

## Constraints and notes

* 1 <= N, Q <= 100,000
* 1 <= T <= 10
* 1 <= K <= 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 | Restrictions       |
|---|--------|--------------------|
| 1 | 7      | T = Q = 1          |
| 2 | 10     | N, Q, K <= 100     |
| 3 | 12     | N, Q <= 50         |
| 4 | 28     | T = 1              |
| 5 | 17     | Q = 1              |
| 6 | 26     | No additional restrictions. |

---

**Example 1:**

*Input:*
```
3 2 7
8 1
2 0
0 3
2
10 2
2 6
```
*Output:*
```
29
```

---

**Example 2:**

*Input:*
```
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
```
*Output:*
```
708
```

---


Starter code: