Little penguin Polo has an n × m matrix, consisting of integers. Let's index the matrix rows from 1 to n from top to bottom and let's index the columns from 1 to m from left to right. Let's represent the matrix element on the intersection of row i and column j as a_{ij}.

In one move the penguin can add or subtract number d from some matrix element. Find the minimum number of moves needed to make all matrix elements equal. If the described plan is impossible to carry out, say so.


-----Input-----

The first line contains three integers n, m and d (1 ≤ n, m ≤ 100, 1 ≤ d ≤ 10^4) — the matrix sizes and the d parameter. Next n lines contain the matrix: the j-th integer in the i-th row is the matrix element a_{ij} (1 ≤ a_{ij} ≤ 10^4).


-----Output-----

In a single line print a single integer — the minimum number of moves the penguin needs to make all matrix elements equal. If that is impossible, print "-1" (without the quotes).


-----Examples-----
Input
2 2 2
2 4
6 8

Output
4

Input
1 2 7
6 7

Output
-1

Difficulty: interview

Starter code:

Solutions:
import re
import itertools
from collections import Counter, deque

class Task:
    a = []
    d = 0
    answer = 0
	
    def getData(self):
        n, m, self.d = [int(x) for x in input().split(' ')]
        for _ in range(n):
            self.a += [int(x) for x in input().split(' ')]
        #inFile = open('input.txt', 'r')
        #inFile.readline().rstrip()
        #self.childs = inFile.readline().rstrip()

    def solve(self):
        a = self.a

        for x in a:
            if x % self.d != a[0] % self.d:
                self.answer = -1
                return
        
        a = [x // self.d for x in a]
        a.sort()
        
        d = [sum(a)] + [0 for _ in range(1, a[-1] + 1)]
        
        lessCurrentLevel = 0
        counter = Counter(a)
        
        for level in range(1, a[-1] + 1):
            lessCurrentLevel += counter[level - 1]
            d[level] = d[level - 1] + lessCurrentLevel - \
                    (len(a) - lessCurrentLevel)
        self.answer = min(d)

    def solve2(self):
        a, d = self.a, self.d
        for i in range(1, len(a)):
            if a[i] % d != a[0] % d:
                self.answer = -1
                return
        a = [x // d for x in a]
        d = [abs(a[0] - i) for i in range(10000 + 1)]
        for i in range(1, len(a)):
            for j in range(0, len(d)):
                d[j] += abs(a[i] - j)
        self.answer = min(d)

    def printAnswer(self):
        print(self.answer)
        #print(re.sub('[\[\],]', '', str(self.answer)))
        #outFile = open('output.txt', 'w')
        #outFile.write(self.answer)

task = Task()
task.getData()
task.solve()
task.printAnswer()


def f(t):
    t.sort()
    return t[len(t) // 2]
    
n, m, d = map(int, input().split())
t, p = [], [0] * (n * m)
for i in range(n):
    t += list(map(int, input().split()))
u = t[0] % d
for i, v in enumerate(t):
    if u != v % d:
        p = []
        break
    else: p[i] = v // d
if p:
    s = f(p)
    print(sum(abs(i - s) for i in p))
else: print(-1)

n, m, d = map(int, input().split())
k, t = n * m, []
for i in range(n):
    t += list(map(int, input().split()))
u = t[0] % d
for v in t:
    if u != v % d:
        t = []
        break
if t:
    t.sort()
    s = t[k // 2]
    print(sum(abs(v - s) for v in t) // d)
else: print(-1)

n, m, d = (int(x) for x in input().split())
s = set()
l = []
for i in range(n):
	tmp = [int(x) for x in input().split()]
	s |= {x % d for x in tmp}
	l += [x // d for x in tmp]
if len(s) != 1:
	print(-1)
	return
l.sort()
mean = l[n * m // 2]
ans = 0
for x in l:
	ans += abs(x - mean)
if n * m // 2 > 0:
	mean = l[n * m // 2 - 1]
	ans2 = 0
	for x in l:
		ans2 += abs(x - mean)
	ans = min(ans, ans2)
print(ans)


def main():
    n, m, d = list(map(int, input().split()))
    l = [x for _ in range(n) for x in map(int, input().split())]
    n *= m
    m = min(l)
    for i, x in enumerate(l):
        x -= m
        if x % d:
            print(-1)
            return
        l[i] = x
    l.sort()
    m = l[n // 2]
    print(sum(abs(x - m) for x in l) // d)


def __starting_point():
    main()

__starting_point()

n, m, d = list(map(int, input().split()))
mat = []
for _ in range(n):
    for x in list(map(int, input().split())):
        mat.append(x)
x = mat[0] % d
for y in mat:
    if y % d != x:
        print(-1)
        return
mat = [(y - x) / d for y in mat]
mat.sort()
med = mat[int((m * n) / 2)]
print(int(sum([abs(y - med) for y in mat])))


from itertools import chain
n, m, d = map(int, input().split())
a = [map(int, input().split()) for i in range(n)]
p = sorted(chain.from_iterable(a))
e = set()
ans = 0
for i in p:
    e.add(i % d)
if len(e) > 1:
    print(-1)
    return
else:
    if len(p) % 2 == 0:
        med = p[(len(p)//2) - 1]
        for i in p:
            ans += abs(i - med)
        print(ans // d)
    else:
        med = p[(len(p)//2)]
        for i in p:
            ans += abs(i - med)
        print(ans // d)

def polo(l, d):
    l.sort()
    #find median k
    k = l[int(len(l)/2)]
    s = 0

    #loop through again and calculate if each element |x-k| % d == 0
    #if so, add k to sum
    for n in l:
        if abs(n-k) % d == 0:
            s = s + abs(n-k)
        else:
            return -1
    return int(s / d)


l = []
n,m,d = [int(x) for x in input().split(' ')]
for _ in range(n):
    l.extend(int(x) for x in input().split(' '))

print(polo(l, d))


"""http://codeforces.com/problemset/problem/289/B"""
def solve(d, l):
    l.sort()
    m = l[0] % d
    median = len(l) // 2
    res = 0
    for num in l:
        if num % d != m:
            return -1
        res += abs(num - l[median]) // d
    return res

def __starting_point():
    f = lambda: list(map(int, input().split()))
    n, m, d = f()
    l = []
    for i in range(n):
        l += f()
    print(solve(d, l))

__starting_point()

def solve(d, l):
    l.sort()
    m = l[0] % d
    median = len(l) // 2
    res = 0
    for num in l:
        if num % d != m:
            return -1
        res += abs(num - l[median]) // d
    return res

def __starting_point():
    f = lambda: list(map(int, input().split()))
    n, m, d = f()
    l = []
    for i in range(n):
        l += f()
    print(solve(d, l))

__starting_point()

n,m,d = map(int,input().split())
array = []
for i in range(n):
	array.extend(map(int,input().split()))
array.sort()
mid = int(n*m/2)
ans = 0
notpossible = False
for i in range(n*m):
	if array[mid] > array[i]:
		diff = array[mid] - array[i]
		if diff%d != 0:
			notpossible = True
			break
		ans += int(diff/d)
	elif array[mid] < array[i]:
		diff = array[i] - array[mid]
		if diff%d != 0:
			notpossible = True
			break
		ans += int(diff/d)
if notpossible:
	print("-1")
else:
	print(ans)

import sys

def main():
    (n, m, d) = list(map(int, sys.stdin.readline().split(' ')))
    nums = []
    for i in range(n):
        nums = nums + list(map(int, sys.stdin.readline().split(' ')))
    k = n * m
    g = nums[0] % d
    for i in range(1, k):
        if nums[i] % d != g:
            sys.stdout.write('-1\n')
            return
    nums = sorted(nums)
    ret = 0
    median = nums[k//2]
    for i in range(k):
        ret += abs((nums[i] - median) // d)
    sys.stdout.write("{}\n".format(ret))


main()



n, m, d = list(map(int, input().split()))
k, t = n * m, []
for i in range(n):
    t += list(map(int, input().split()))
u = t[0] % d
for v in t:
    if u != v % d:
        t = []
        break
if t:
    t.sort()
    s = t[k // 2]
    print(sum(abs(v - s) for v in t) // d)
else:
  print(-1)


# http://codeforces.com/problemset/problem/289/B
n,m,d = list(map(int, input().split()))
mat = []
for _ in range(n):
     for x in list(map(int, input().split())):
        mat.append(x)
    #mat.append([x for x in list(map(int, input().split()))])
#print(mat)
x = mat[0] % d
#print(x)
for y in mat:
    if y % d != x:
        print(-1)
        return
mat = [(y-x)/d for y in mat]
#print(mat)
mat.sort()
#print(mat)
med = mat[int((m*n) / 2)]
#print(med)
print(int(sum([abs(y-med) for y in mat])))


array = []
n, m, d = input().split()
n, m, d = int(n), int(m), int(d)

for i in range(n):
    array += list(map(int, input().split()))
rem = array[0] % d
flag = False
for j in range(m*n):
    if array[j] % d != rem:
        flag = True
if flag:
    print('-1')
else:
    array.sort()
    median = len(array)//2
    ans = 0
    for i in range(n*m):
        val = array[i] - array[median]
        if val < 0:
            val = -val
        ans += val
    print(ans//d)

x,y,n=map(int,input().split())
a=[]
b=[]
for i in range(x):
    a+=list(map(int,input().split()))
r=a[0]%n
count=0
count1=0
for i in a:
    if i%n!=r:
        print(-1)
        return
a.sort()
s=0
x=a[(x*y)//2]
for i in a:
    s+=abs(x-i)//n
print(s)

n,m,d=map(int,input().split())
a=[]
for i in range(n):
    a.extend(list(map(int,input().split())))
a.sort();k=0
mi=(n*m)//2
for i in range(n*m):
    if abs(a[mi]-a[i])%d!=0:
        print(-1);return
    else:
        k+=(abs(a[mi]-a[i])//d)
print(k)

n,m,d=map(int,input().split())
a=[]
sum=0
for i in range(n):
    a.extend(list(map(int,input().split())))
x=a[0]%d
a.sort()
mid=a[n*m//2]
for i in a:
    if i%d!=x:
        print('-1')
        return
    else   :
        sum+=abs(i-mid)//d
print(sum)        

n,m,d=list(map(int,input().split()))
a=[]
for i in range(n):
    b=list(map(int,input().split()))
    a=a+b
a.sort()
if d>a[n*m-1]-a[0] and a[0]!=a[n*m-1]:
    print(-1)
else:
    s=0
    x=a[0]%d
    m=a[n*m//2]
    for i in a:
        if i%d!=x:
            print(-1)
            return
        s= s+ abs(m-i)/d
    print(int(s))


def med(list):
    nonlocal n,m
    s=sorted(list)
    return s[(n*m-1)//2]
nmd=list(input().split())
n=int(nmd[0])
m=int(nmd[1])
d=int(nmd[2])
sum=0
a=[[0]*m  for _ in range(n)]
for i in range(n):
    a[i]=[int(j) for j in input().strip().split(" ")]
sum=0
w=[]
for i in range(n):
    for j in range(m):
        w.append(a[i][j])
k=med(w)
for i in range(n):
    for j in range(m):
        sum=sum+abs(a[i][j]-k)
        w.append(a[i][j])
if sum%d==0:
    print(sum//d)
else:
    print(-1)


n,m,d=map(int,input().split())
a=[]
for i in range(n):
    a.extend(list(map(int,input().split())))
a.sort();k=0
mi=(n*m)//2
for i in range(n*m):
    if abs(a[mi]-a[i])%d!=0:
        print(-1)
        return
    else:
        k+=(abs(a[mi]-a[i])//d)
print(k)

n, m, d = [int(x) for x in input().split(' ')]

total = n*m
total_matrix = []

for i in range(n):
	total_matrix += [int(x) for x in input().split(' ')]

total_matrix = sorted(total_matrix)

middle = total // 2
not_possible = False
count = 0

for el in total_matrix:
	if abs(total_matrix[middle] - el) % d != 0:
		not_possible = True
		break
	else:
		count += abs(total_matrix[middle] - el) // d

if not_possible:
	print(-1)
else:
	print(count)

import statistics

def solve(array, d):
    minval = min(array)
    for i in range(len(array)):
        if (array[i] - minval) % d:
            return -1
        array[i] //= d

    # minimize sum |array_i - x|
    # x = median
    median = round(statistics.median(array))
    moves = 0
    for el in array:
        moves += abs(el - median)

    return moves

line = input()
n, m, d = list(map(int, line.strip().split()))
array = []

for i in range(n):
    line = input()
    row = list(map(int, line.strip().split()))
    array += row

print(solve(array, d))



n, m, d = list(map(int, input().split()))
ll = []
for i in range(n):
    temp = [int(x) for x in input().split()]
    ll.append(temp)
l = []
for i in range(n):
    for j in range(len(ll[i])):
        l.append(ll[i][j])
# print(arr)
flag = 0
l = sorted(l)
for i in range(len(l) - 1):
    if abs(l[i] - l[i + 1]) % d != 0:
        flag = 1
        break
# print(l)
median = l[len(l) // 2]
moves = 0
# print(median)
for i in range(len(l)):
    moves += abs(l[i] - median) // d
if flag == 1:
    print(-1)
else:
    print(moves)