Statues - Problem

# 10145. Statues

Statistics

<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

stdout

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

<Link /> vrea să pună mâna pe o nouă C chart, care poate fi găsită doar pe The Isle of <meta>, în interiorul The Temple of <element>. Pentru a intra în Templu, el trebuie să rezolve mai întâi un puzzle.

<Link /> trebuie să intre mai întâi într-un plan $T$ -dimensional, prin urmare fiecare punct din spațiu se descrie printr-un vector de lungime $T: [x_1, x_2, x_3, \dots, x_T]$ . În acest plan există $N$ statui staționare numerotate de la $1$ la $N$ și $Q$ statui mobile numerotate de la $1$ la $Q$ . <Link /> poate face următoarea mutare de cel mult $K$ ori: el poate alege orice statuie mobilă și o axă și poate muta statuia respectivă cu exact o unitate în orice direcție. Adică, coordonatele unei astfel de statui vor deveni sau $[x_1, x_2, \dots, x_i−1, \dots, x_T]$ sau $[x_1,x_2, \dots,x_i+1, \dots,x_T]$ .

Pentru a debloca intrarea în The Temple of <element>, el trebuie să mute statuile mobile în așa fel încât suma distanțelor Manhattan dintre fiecare statuie mobilă și fiecare statuie staționară să fie redusă la minimum.

Distanța Manhattan dintre două puncte $T$ -dimensionale $[x_1, x_2, \dots, x_T]$ și $[y_1, y_2, \dots, y_T]$ se definește ca:

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

Fie $s$ un vector cu coordonate pentru fiecare statuie staționară și $m$ un vector cu coordonate pentru fiecare statuie mobilă după efectuarea a cel mult $K$ deplasări optimale. Calculați:

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

Date de intrare

Prima linie a inputului va conține numerele întregi $N, T, K$ care reprezintă numărul de statui staționare, dimensiunea și numărul maxim de mutări pe care <Link /> le poate face.

Următoarele $N$ linii conțin câte $T$ numere întregi separate prin spațiu. Linia a $i$ -a a acestora reprezintă coordonatele statuii a $i$ -a staționare.

Linia următoare conține un singur întreg $Q$ reprezentând numărul de statui mobile.

Ultimile $Q$ linii conțin câte $T$ numere întregi separate prin spațiu, reprezentând coordonatele fiecărei statui mobile, într-un mod similar cu statuile staționare.

Date de ieșire

Afișați un singur întreg care reprezintă suma minimă a distanțelor Manhattan de la fiecare statuie staționară la fiecare statuie mobilă după ce ați făcut cel mult $K$ mutări.

Restricții și precizări

$1 \leq N, Q \leq 100 \ 000$
$1 \leq T \leq 10$
$1 \leq K \leq 10^{15}$
Toate coordonate sunt numere întregi de la $0$ până la $10^9$ inclusiv.
Se garantează că raspuns se încadrează într-un număr intreg cu semn 64 biți.

#	Puncte	Restricții
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	Fără restricții suplimentare.

Exemplul 1

stdin

stdout

Exemplul 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

QOJ.ac

QOJ

# 10145. Statues

Input

Output

Constraints and notes

Example 1

Example 2

Date de intrare

Date de ieșire

Restricții și precizări

Exemplul 1

Exemplul 2