------Read problems statements in Mandarin chinese
, Russian and Vietnamese as well. ------ 

Tumut, the best programmer in his village Applidz, invented a problem and decided to share it with you:

You are given two integer sequences $S_{1}, S_{2}, \dots, S_{N}$ and $T_{1}, T_{2}, \dots, T_{M}$ and an integer $x$. You are allowed to perform the following operation any number of times:
choose an element of $S$ and an element of $T$ (let's denote them by $S_{i}$ and $T_{j}$ respectively)
decrease both $S_{i}$ and $T_{j}$ by $x$, i.e. replace $S_{i}$ by $S_{i}-x$ and $T_{j}$ by $T_{j}-x$

Let's denote the minimum and maximum value in the sequence $S$ after performing the chosen operations (possibly none) by $minS$ and $maxS$ respectively. Similarly, let's denote the minimum and maximum value in $T$ after performing the chosen operations by $minT$ and $maxT$ respectively. The goal is minimizing the expression $(maxS+maxT) - (minS+minT)$. Compute the minimum value of this expression. 

------  Input ------
The first line of the input contains three space-separated integers $N$, $M$ and $x$.
The second line contains $N$ space-separated integers $S_{1}, S_{2} \dots S_{N}$.
The third line contains $M$ space-separated integers $T_{1}, T_{2} \dots T_{M}$.

------  Output ------
Print a single line containing one integer — the minimum possible value of the expression $(maxS+maxT) - (minS+minT)$.

------  Constraints ------
$1 ≤ N, M ≤ 5\cdot 10^{5}$
$1 ≤ S_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ T_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ x ≤ 10^{9}$

------  Subtasks ------
Subtask #1 (20 points):
$N, M ≤ 20$
$S_{i} ≤ 20$ for each valid $i$
$T_{i} ≤ 20$ for each valid $i$

Subtask #2 (30 points):
$N, M ≤ 1,000$
$S_{i} ≤ 1,000$ for each valid $i$
$T_{i} ≤ 1,000$ for each valid $i$

Subtask #3 (50 points): original constraints

----- Sample Input 1 ------ 
2 2 3
1 8
2 3
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
We can perform these two operations:
1. decrease $S_{2}$ and $T_{1}$ by $x$
2. decrease $S_{2}$ and $T_{2}$ by $x$

Afterwards, the sequence $S$ will be $[1, 2]$ and the sequence $T$ will be $[-1, 0]$. The resulting value of the given expression is $(2+0)-(1+(-1)) = 2$. It is impossible to obtain a smaller value no matter how many operations are performed.

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Mathematics

Greedy algorithms


Solutions:
def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def solve(s, t, x):
	m = min(t)
	t = [a - m for a in t]
	m = min(s)
	s = [a - m for a in s]
	ty = sum((a // x for a in t))
	sy = sum((a // x for a in s))
	if ty < sy:
		(s, t) = (t, s)
		(ty, sy) = (sy, ty)
	ty -= sy
	s = sorted([a % x for a in s])
	t = sorted([a % x for a in t])
	g = gcd(len(s), len(t))
	ty %= g
	for i in range(ty):
		t[i] += x
	t = sorted(t)
	dt = [x + t[i] - t[i + 1] for i in range(len(t) - 1)] + [t[-1] - t[0]]
	ds = [x + s[i] - s[i + 1] for i in range(len(s) - 1)] + [s[-1] - s[0]]
	qt = [min(dt[i::g]) for i in range(g)]
	qs = [min(ds[i::g]) for i in range(g)]
	ret = x * 2
	for i in range(g):
		ret = min(ret, qt[i] + qs[i])
	return ret
import sys
f = sys.stdin
(n, m, x) = map(int, f.readline().split())
s = list(map(int, f.readline().split()))
t = list(map(int, f.readline().split()))
q = solve(s, t, x)
print(q)


def mgcd(a, b):
	while b > 0:
		(a, b) = (b, a % b)
	return a

def reduction(arr, mdl):
	totred = 0
	for e in range(len(arr)):
		(red, arr[e]) = divmod(arr[e], mdl)
		totred += red
	return totred

def submins(arr, red, g, mdl):
	submin = [mdl + 1] * g
	rx = red % g
	submin[rx] = arr[-1] - arr[0]
	for ix in range(1, len(arr)):
		thmin = mdl + arr[ix - 1] - arr[ix]
		rx = rx - 1 if rx > 0 else g - 1
		if thmin < submin[rx]:
			submin[rx] = thmin
	return submin
(n, m, x) = map(int, input().split())
z = input().strip().split()
s = list(map(int, z[:n]))
z = input().strip().split()
t = list(map(int, z[:m]))
g = mgcd(n, m)
sred = reduction(s, x)
tred = reduction(t, x)
s.sort()
t.sort()
smin = submins(s, sred, g, x)
tmin = submins(t, tred, g, x)
ans = smin[0] + tmin[0]
for (sm, tm) in zip(smin, tmin):
	if sm + tm < ans:
		ans = sm + tm
print(ans)