You are given a matrix $a$ of size $n \times m$ consisting of integers.

You can choose no more than $\left\lfloor\frac{m}{2}\right\rfloor$ elements in each row. Your task is to choose these elements in such a way that their sum is divisible by $k$ and this sum is the maximum.

In other words, you can choose no more than a half (rounded down) of elements in each row, you have to find the maximum sum of these elements divisible by $k$.

Note that you can choose zero elements (and the sum of such set is $0$).


-----Input-----

The first line of the input contains three integers $n$, $m$ and $k$ ($1 \le n, m, k \le 70$) — the number of rows in the matrix, the number of columns in the matrix and the value of $k$. The next $n$ lines contain $m$ elements each, where the $j$-th element of the $i$-th row is $a_{i, j}$ ($1 \le a_{i, j} \le 70$).


-----Output-----

Print one integer — the maximum sum divisible by $k$ you can obtain.


-----Examples-----
Input
3 4 3
1 2 3 4
5 2 2 2
7 1 1 4

Output
24

Input
5 5 4
1 2 4 2 1
3 5 1 2 4
1 5 7 1 2
3 8 7 1 2
8 4 7 1 6

Output
56



-----Note-----

In the first example, the optimal answer is $2$ and $4$ in the first row, $5$ and $2$ in the second row and $7$ and $4$ in the third row. The total sum is $2 + 4 + 5 + 2 + 7 + 4 = 24$.

Difficulty: EASY

Starter code:

Solutions:
inf = 1000000007
(n, m, k) = map(int, input().split())
dp = [-inf for i in range(k)]
dp[0] = 0
sz = m // 2
for _ in range(n):
	a = list(map(int, input().split()))
	pre = dp
	dp = [[-inf for _ in range(k)] for _ in range(sz + 1)]
	dp[0] = pre
	for x in a:
		for i in range(sz, 0, -1):
			for j in range(k):
				dp[i][j] = max(dp[i][j], dp[i - 1][((j - x) % k + k) % k] + x)
	for i in range(1, sz + 1):
		for j in range(k):
			dp[0][j] = max(dp[0][j], dp[i][j])
	dp = dp[0]
print(dp[0])


def read_generator():
	while True:
		tokens = input().split(' ')
		for t in tokens:
			yield t
reader = read_generator()

def readword():
	return next(reader)

def readint():
	return int(next(reader))

def readfloat():
	return float(next(reader))

def readline():
	return input()

def solve(n, m, t, a):
	ss = []
	for i in range(n):
		h = sum(a[i])
		s = [-1] * (h + 73)
		s[0] = 0
		for j in range(m):
			for k in range(h + 1, -1, -1):
				if 0 < s[k] + 1 <= m // 2:
					v = a[i][j]
					s[k + v] = min(s[k + v], s[k] + 1)
					if s[k + v] == -1:
						s[k + v] = s[k] + 1
		toAdd = []
		for j in range(len(s)):
			if s[j] > -1:
				toAdd.append(j)
		ss.append(toAdd)
	res = [0] * t
	for s in ss:
		nextRes = [0] * t
		for j in range(t):
			for v in s:
				nextRes[(v + res[j]) % t] = max(res[j] + v, nextRes[(v + res[j]) % t])
		res = nextRes
	return res[0]
tests = 1
for t in range(tests):
	n = readint()
	m = readint()
	k = readint()
	a = []
	for i in range(n):
		r = []
		for j in range(m):
			r.append(readint())
		a.append(r)
	print(solve(n, m, k, a))


import sys
input = sys.stdin.readline
(n, m, k) = list(map(int, input().split()))
arr = [list(map(int, input().split())) for i in range(n)]
dp = []
for i in range(n):
	dp.append([])
	for j in range(m):
		dp[i].append([])
		for x in range(k):
			dp[i][j].append([])
			for z in range(m // 2 + 1):
				dp[i][j][x].append(-sys.maxsize)
dp[0][0][0][0] = 0
if m // 2 > 0:
	dp[0][0][arr[0][0] % k][1] = arr[0][0]
for i in range(n):
	for j in range(m):
		for x in range(k):
			for z in range(m // 2 + 1):
				val = arr[i][j]
				if j > 0:
					if z != 0:
						dp[i][j][x][z] = max(dp[i][j - 1][x][z], dp[i][j - 1][(x - val) % k][z - 1] + val)
					else:
						dp[i][j][x][z] = dp[i][j - 1][x][z]
				elif i > 0:
					if z == 0:
						dp[i][j][x][z] = max(dp[i - 1][m - 1][x])
					if z == 1:
						dp[i][j][x][z] = max(dp[i - 1][m - 1][(x - val) % k]) + val
print(max(dp[n - 1][m - 1][0]))


from math import inf as _inf
import sys as _sys
_NEGATIVE_INF = -_inf

def main():
	(n, m, k) = _read_ints()
	a = tuple((tuple(_read_ints()) for i_row in range(n)))
	result = find_max_sum(a, k)
	print(result)

def _read_line():
	result = _sys.stdin.readline()
	assert result[-1] == '\n'
	return result[:-1]

def _read_ints():
	return map(int, _read_line().split())

def find_max_sum(matrix, k):
	selections_n = len(matrix[0]) // 2
	rows_maximums = tuple(map(lambda row: _find_seq_maximums(row, selections_n, k), matrix))
	cache = [[None] * k for i_row in range(len(matrix) + 1)]
	cache[len(matrix)][0] = 0
	for remainder_need in range(1, k):
		cache[len(matrix)][remainder_need] = _NEGATIVE_INF
	for i_row in reversed(range(len(matrix))):
		row_maximums = rows_maximums[i_row]
		for remainder_need in range(k):
			result = _NEGATIVE_INF
			for (remainder, maximum) in row_maximums.items():
				potential_result = maximum + cache[i_row + 1][(remainder_need - remainder) % k]
				if potential_result > result:
					result = potential_result
			cache[i_row][remainder_need] = result
	return cache[0][0]

def _find_seq_maximums(seq, selections_n, k):
	cache = [[[None] * (selections_n + 1) for remainder_need in range(k)] for i in range(len(seq) + 1)]
	for i in range(len(seq) + 1):
		cache[i][0][0] = 0
		for remainder_need in range(1, k):
			cache[i][remainder_need][0] = _NEGATIVE_INF
	for can_select in range(selections_n + 1):
		cache[len(seq)][0][can_select] = 0
		for remainder_need in range(1, k):
			cache[len(seq)][remainder_need][can_select] = _NEGATIVE_INF
	for i in reversed(range(len(seq))):
		for remainder_need in range(k):
			for can_select in range(1, selections_n + 1):
				skip_result = cache[i + 1][remainder_need][can_select]
				take_result = seq[i] + cache[i + 1][(remainder_need - seq[i]) % k][can_select - 1]
				if take_result > skip_result:
					result = take_result
				else:
					result = skip_result
				cache[i][remainder_need][can_select] = result
	maximums = dict()
	for remainder in range(k):
		maximum = cache[0][remainder][selections_n]
		if maximum > _NEGATIVE_INF:
			maximums[remainder] = maximum
	return maximums
main()


import sys
input = sys.stdin.readline

def main():
	(n, m, k) = map(int, input().split())
	half = m // 2
	se_s = []
	for i in range(n):
		lst = list(map(int, input().split()))
		lst.sort(reverse=True)
		total_sub = sum(lst[:half])
		dp = [[0 for _ in range(k)] for _ in range(half + 1)]
		for num2 in lst:
			for i in range(half, 0, -1):
				for num in dp[i - 1]:
					pos = (num + num2) % k
					dp[i][pos] = max(dp[i][pos], num + num2)
		se_s.append(set(dp[-1]))
	ans = 0
	ans_sub = set([0])
	for se in se_s:
		se_tmp = set()
		for num in se:
			for num2 in ans_sub:
				se_tmp.add(num + num2)
				if (num + num2) % k == 0:
					ans = max(ans, num + num2)
		tmp = [0 for _ in range(k)]
		for num in se_tmp:
			tmp[num % k] = max(tmp[num % k], num)
		ans_sub = set(tmp)
	print(ans)
main()


def getnum(row, col, nowmod, rest, matrix, dic, k):
	if (row, col, nowmod, rest) in dic:
		return dic[row, col, nowmod, rest]
	m = len(matrix)
	n = len(matrix[0])
	if row == m:
		if nowmod == 0:
			return 0
		else:
			return -2147483647
	if col == n - 1:
		(nextrow, nextcol) = (row + 1, 0)
	else:
		(nextrow, nextcol) = (row, col + 1)
	if nextcol == 0:
		num1 = getnum(nextrow, nextcol, nowmod, n // 2, matrix, dic, k)
	else:
		num1 = getnum(nextrow, nextcol, nowmod, rest, matrix, dic, k)
	if rest > 0:
		if nextcol == 0:
			num2 = getnum(nextrow, nextcol, (nowmod + matrix[row][col]) % k, n // 2, matrix, dic, k) + matrix[row][col]
		else:
			num2 = getnum(nextrow, nextcol, (nowmod + matrix[row][col]) % k, rest - 1, matrix, dic, k) + matrix[row][col]
	else:
		num2 = -2147483647
	dic[row, col, nowmod, rest] = max(num1, num2)
	return max(num1, num2)
(m, n, k) = map(int, input().split())
matrix = []
for i in range(m):
	arr = list(map(int, input().split()))
	matrix.append(arr)
dp = [[[[-1 for q in range(n // 2 + 1)] for p in range(k)] for j in range(n)] for i in range(m + 1)]
for p in range(k):
	if p == 0:
		dp[m][0][p][n // 2] = 0
	else:
		dp[m][0][p][n // 2] = -2147483647
for i in range(m - 1, -1, -1):
	for j in range(n - 1, -1, -1):
		for p in range(k):
			for q in range(n // 2 + 1):
				if j == n - 1:
					(nexti, nextj) = (i + 1, 0)
				else:
					(nexti, nextj) = (i, j + 1)
				if j == n - 1:
					num1 = dp[nexti][nextj][p][n // 2]
				else:
					num1 = dp[nexti][nextj][p][q]
				if q > 0:
					if j == n - 1:
						num2 = dp[nexti][nextj][(p + matrix[i][j]) % k][n // 2] + matrix[i][j]
					else:
						num2 = dp[nexti][nextj][(p + matrix[i][j]) % k][q - 1] + matrix[i][j]
				else:
					num2 = -2147483647
				dp[i][j][p][q] = max(num1, num2)
print(dp[0][0][0][n // 2])


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for k in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for k in range(c)] for k in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** (-10)
(N, M, K) = MAP()
dp = list3d(M + 1, M // 2 + 1, K, -1)
nxt = [-1] * K
dp[0][0][0] = 0
for i in range(N):
	row = LIST()
	for j in range(M):
		for k in range(M // 2 + 1):
			for l in range(K):
				if dp[j][k][l] != -1:
					dp[j + 1][k][l] = max(dp[j + 1][k][l], dp[j][k][l])
					if k + 1 <= M // 2:
						dp[j + 1][k + 1][(l + row[j]) % K] = max(dp[j + 1][k + 1][(l + row[j]) % K], dp[j][k][l] + row[j])
	for k in range(M // 2 + 1):
		for l in range(K):
			nxt[l] = max(nxt[l], dp[M][k][l])
	dp = list3d(M + 1, M // 2 + 1, K, -1)
	dp[0][0] = nxt
	nxt = [-1] * K
ans = dp[0][0][0]
print(ans)


(N, M, K) = map(int, input().split())
dp1 = [0] + [-float('inf')] * (K - 1)
from collections import defaultdict
for i in range(N):
	dp2 = [[-float('inf')] * (M // 2 + 1) for _ in range(K)]
	dp2[0][0] = 0
	A = list(map(int, input().split()))
	for j in range(M):
		new_dp2 = [[-float('inf')] * (M // 2 + 1) for _ in range(K)]
		new_dp2[0][0] = 0
		for k in range(K):
			for l in range(M // 2):
				new_dp2[(k + A[j]) % K][l + 1] = max(dp2[(k + A[j]) % K][l + 1], dp2[k][l] + A[j])
		dp2 = new_dp2
	new_dp1 = [0] + [-float('inf')] * (K - 1)
	for k1 in range(K):
		for k2 in range(K):
			new_dp1[(k1 + k2) % K] = max(new_dp1[(k1 + k2) % K], dp1[k1] + max(dp2[k2]))
	dp1 = new_dp1
ans = dp1[0]
print(ans)


import sys
input = sys.stdin.readline
T = 1
for _ in range(T):
	(n, m, k) = map(int, input().split())
	A = []
	for i in range(n):
		A.append(list(map(int, input().split())))
	kDP = []
	for i in range(n):
		msum = max(A[i]) * m
		rsum = [10 ** 9 for i in range(msum + 1)]
		for j in range(m):
			for k1 in range(msum - A[i][j], -1, -1):
				if rsum[k1] != 10 ** 9:
					rsum[k1 + A[i][j]] = min(rsum[k1 + A[i][j]], rsum[k1] + 1)
			rsum[A[i][j]] = 1
		rkmod = [0 for i in range(k)]
		for j in range(1, msum + 1):
			if rsum[j] <= m // 2:
				rkmod[j % k] = j
		kDP.append(rkmod)
	ans = [[0 for i in range(k)] for j in range(n)]
	ans[0] = kDP[0]
	for i in range(1, n):
		for k1 in range(k):
			for j in range(k):
				if ans[i - 1][j] != 0 and kDP[i][k1] != 0:
					ans[i][(j + k1) % k] = max(ans[i - 1][j] + kDP[i][k1], ans[i][(j + k1) % k])
			ans[i][k1] = max(ans[i - 1][k1], ans[i][k1], kDP[i][k1])
	print(ans[n - 1][0])


import sys

def I():
	return int(input())

def LI():
	return [int(i) for i in input().split()]
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()
ans = 0

def sol(a, k):
	m = len(a)
	d = m // 2
	dp = [[[0] * k for i in range(m + 1)] for i in range(d + 1)]
	for i in range(m):
		c = a[i]
		dp[1][i + 1][c % k] = max(dp[1][i + 1][c % k], c)
		for l in range(d + 1):
			for j in range(k):
				dp[l][i + 1][j] = max(dp[l][i][j], dp[l][i + 1][j])
				if l < d:
					dp[l + 1][i + 1][(dp[l][i][j] + c) % k] = max(dp[l + 1][i + 1][(dp[l][i][j] + c) % k], dp[l][i][j] + c)
	rt = [0] * k
	for i in range(k):
		for l in range(d + 1):
			rt[i] = max(rt[i], dp[l][m][i])
	return rt
(n, m, k) = LI()
if m == 1:
	print(0)
	exit()
p = []
for i in range(n):
	a = LI()
	p += (sol(a, k),)
dp = [0] * k
nx = [0] * k
for i in range(n):
	for t in range(k):
		for j in range(k):
			nx[(dp[t] + p[i][j]) % k] = max(nx[(dp[t] + p[i][j]) % k], dp[t] + p[i][j])
	dp = nx[:]
ans = dp[0]
print(ans)


(n, m, k) = map(int, input().split())
l = m // 2
p = [-1] * k
p[0] = 0
for _ in range(n):
	t = [[-1] * (l + 1) for i in range(k)]
	t[0][0] = 0
	for q in map(int, input().split()):
		for j in range(l - 1, -1, -1):
			for i in range(k):
				if t[i][j] != -1:
					d = (i + q) % k
					t[d][j + 1] = max(t[d][j + 1], t[i][j] + q)
	r = [-1] * k
	for i in range(k):
		q = max(t[i])
		if q != -1:
			for j in range(k):
				if p[j] != -1:
					d = (i + j) % k
					r[d] = max(r[d], p[j] + q)
	p = r
print(p[0])


maxn = int(75)
nvc = int(-100000005)
G = [[nvc for _ in range(maxn)] for _ in range(maxn)]
F = [[nvc for _ in range(maxn)] for _ in range(maxn)]
a = [0 for _ in range(maxn)]
(n, m, k) = map(int, input().split(' '))
F[0][0] = 0
for i in range(n):
	a = list(map(int, input().split(' ')))
	for u in range(m // 2 + 1):
		for v in range(k):
			G[0][v] = max(G[0][v], F[u][v])
	F = [[nvc for _ in range(maxn)] for _ in range(maxn)]
	for j in range(m):
		for u in range(m // 2 + 1):
			for v in range(k):
				F[u + 1][(v + a[j]) % k] = max(F[u + 1][(v + a[j]) % k], G[u][v] + a[j])
				F[u][v] = max(F[u][v], G[u][v])
		for u in range(m // 2 + 1):
			for v in range(k):
				G[u][v] = F[u][v]
res = 0
for i in range(m // 2 + 1):
	res = max(res, F[i][0])
print(res)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
from collections import defaultdict as dc
(n, m, k) = RL()
mm = m >> 1
g = []
for _ in range(n):
	g.append(RLL())
dn = [set() for _ in range(mm + 1)]
dn[0].add(0)
dic = [[0] * (mm + 1) for _ in range(k)]
for i in range(n):
	for j in range(m):
		key = g[i][j]
		for t in range(min(j, mm - 1), -1, -1):
			for r in dn[t]:
				rr = (r + key) % k
				dic[rr][t + 1] = max(dic[rr][t + 1], dic[r][t] + key)
				dn[t + 1].add(rr)
	tmp = set()
	for t in dn:
		tmp |= t
	dn = [set() for _ in range(mm + 1)]
	dn[0] = tmp
	for r in range(k):
		dic[r][0] = max((dic[r][c] for c in range(mm + 1)))
print(dic[0][0])


from sys import stdin
input = stdin.readline
(Y, X, K) = map(int, input().split())
a = [tuple(map(int, inp.split())) for inp in stdin.read().splitlines()]
dp = [[[-1] * K for i in range(X // 2 + 1)] for j in range(Y)]
for y in range(0, Y):
	if y == 0:
		dp[y][0][0] = 0
	else:
		for k in range(K):
			dp[y][0][k] = dp[y - 1][-1][k]
	for x in range(X):
		cur = a[y][x]
		for i in range(X // 2 - 1, -1, -1):
			for k in range(K):
				if dp[y][i][k] != -1:
					dp[y][i + 1][k] = max(dp[y][i + 1][k], dp[y][i][k])
					dp[y][i + 1][(k + cur) % K] = max(dp[y][i + 1][(k + cur) % K], dp[y][i][k] + cur)
print(dp[Y - 1][X // 2][0])


import sys, math
import io, os
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write('\n'.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
INF = float('inf')
mod = int(1000000000.0) + 7
(n, m, k) = mdata()
A = [mdata() for i in range(n)]
dp1 = [-INF] * k
dp1[0] = 0
for i in range(n):
	dp = [[-INF] * (m // 2 + 1) for _ in range(k)]
	dp[0][0] = 0
	for j in range(m):
		a = A[i][j]
		for x in range(m // 2, 0, -1):
			for y in range(k):
				dp[(y + a) % k][x] = max(dp[(y + a) % k][x], dp[y][x - 1] + a)
	dp2 = dp1[:]
	for x in range(k):
		for y in range(k):
			dp2[(x + y) % k] = max(dp2[(x + y) % k], dp1[x] + max(dp[y]))
	dp1 = dp2[:]
out(dp1[0])


import os
import sys
from io import BytesIO, IOBase

def main():
	(n, m, k) = getints()
	m //= 2
	dp = [int(-1000000000.0)] * k
	dp[0] = 0
	for _ in range(n):
		tmp = [[int(-1000000000.0)] * k for _ in range(m + 1)]
		tmp[0][0] = 0
		for a in getints():
			for x in range(m - 1, -1, -1):
				for y in range(k):
					col = (y + a) % k
					tmp[x + 1][col] = max(tmp[x + 1][col], tmp[x][y] + a)
		ndp = [int(-1000000000.0)] * k
		for x in range(k):
			mx = int(-1000000000.0)
			for i in range(m + 1):
				mx = max(mx, tmp[i][x])
			for y in range(k):
				nxt = (x + y) % k
				ndp[nxt] = max(ndp[nxt], dp[y] + mx)
		dp = ndp
	print(dp[0])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def getint():
	return int(input())

def getints():
	return list(map(int, input().split()))

def getint1():
	return list(map(lambda x: int(x) - 1, input().split()))
main()


(n, m, k) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
dp1 = []
for i in range(n):
	B = A[i]
	temp = [[-1] * k for _ in range(m // 2 + 1)]
	temp[0][0] = 0
	for b in B:
		for l in reversed(range(m // 2)):
			for j in range(k):
				if temp[l][j] != -1:
					temp[l + 1][(b + j) % k] = max(temp[l + 1][(b + j) % k], temp[l][j] + b)
	temp2 = [-1] * k
	for j in range(k):
		for l in range(m // 2 + 1):
			temp2[j] = max(temp2[j], temp[l][j])
	dp1.append(temp2)
dp2 = [[-1] * k for i in range(n + 1)]
dp2[0][0] = 0
for i in range(n):
	for j in range(k):
		dp2[i + 1][j] = dp2[i][j]
	for j in range(k):
		if dp1[i][j] == -1:
			continue
		for l in range(k):
			if dp2[i][l] == -1:
				continue
			dp2[i + 1][(j + l) % k] = max(dp2[i + 1][(j + l) % k], dp2[i][l] + dp1[i][j])
ans = dp2[n][0]
print(max(ans, 0))


import itertools
from pprint import pprint
import math
import sys
import os
from collections import defaultdict

def is_debug():
	return 'PYPY3_HOME' not in os.environ

def stdin_wrapper():
	data = '5 5 4\n1 2 4 2 1\n3 5 1 2 4\n1 5 7 1 2\n3 8 7 1 2\n8 4 7 1 6\n\n'
	for line in data.split('\n'):
		yield line
if not is_debug():

	def stdin_wrapper():
		while True:
			yield sys.stdin.readline()
inputs = stdin_wrapper()

def input_wrapper():
	return next(inputs)

def get_str():
	if is_debug():
		return input_wrapper()
	return input()

def get(_type):
	if _type == str:
		return get_str()
	return _type(input_wrapper())

def get_arr(_type):
	return [_type(x) for x in input_wrapper().split()]

def tuplerize(method):

	def wrap(*args, **kwargs):
		res = method(*args, **kwargs)
		if not isinstance(res, (tuple, list)):
			res = (res,)
		return res
	return wrap

@tuplerize
def solve(k, n, m, mx):
	h = n
	w = m
	_max_count = w // 2 + 1
	_max_rem = k
	dp = [[[-1 for _ in range(_max_rem)] for _ in range(_max_count)] for _ in range(w)]
	next_dp = [[[-1 for _ in range(_max_rem)] for _ in range(_max_count)] for _ in range(w)]
	next_dp[0][0][0] = 0
	for y in range(h):
		dp = next_dp
		next_dp = [[[-1 for _ in range(_max_rem)] for _ in range(_max_count)] for _ in range(w)]
		for x in range(w):
			for cnt in range(_max_count):
				for rem in range(_max_rem):
					v = dp[x][cnt][rem]
					if v == -1:
						continue
					nx = x + 1
					cur_dp = dp
					if x == w - 1:
						nx = 0
						cur_dp = next_dp
					if x == w - 1:
						cur_dp[nx][0][rem] = max(cur_dp[nx][0][rem], v)
					else:
						cur_dp[nx][cnt][rem] = max(cur_dp[nx][cnt][rem], v)
					if cnt < _max_count - 1:
						_mx = mx[y][x]
						nrem = (rem + _mx) % k
						if x == w - 1:
							cur_dp[nx][0][nrem] = max(cur_dp[nx][0][nrem], v + _mx)
						else:
							cur_dp[nx][cnt + 1][nrem] = max(cur_dp[nx][cnt + 1][nrem], v + _mx)
	return next_dp[0][0][0]
(n, m, k) = get_arr(int)
mx = [get_arr(int) for _ in range(n)]
print(*solve(k, n, m, mx))


import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
x = []
inf = 1145141919
for _ in range(n):
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	dp = []
	dp0 = [1]
	dp.append(dp0)
	for i in range(m):
		ai = a[i]
		if i < m // 2:
			dp0 = dp0 + [0] * ai
			dp.append(dp0)
		for j in range(len(dp) - 2, -1, -1):
			for l in range(len(dp[j])):
				dp[j + 1][l + ai] |= dp[j][l]
	y = [-inf] * k
	y[0] = 0
	dp0 = dp[-1]
	for i in range(len(dp0)):
		if dp0[i]:
			y[i % k] = i
	x.append(y)
dp0 = [-inf] * k
dp0[0] = 0
for i in range(n):
	y = x[i]
	dp = [-inf] * k
	for j in range(k):
		s = dp0[j]
		if s < 0:
			continue
		for l in range(k):
			dp[(j + l) % k] = max(dp[(j + l) % k], s + y[l])
	dp0 = dp
ans = dp0[0]
print(ans)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def IND(i, j):
	return i * K + j

def ind(i, j, k):
	return i * (m // 2 + 1) * K + j * K + k
(n, m, K) = inpl()
DP = [0] * (K * (n + 1))
for i in range(n):
	dp = [0] * (K * (m // 2 + 1) * (m + 1))
	a = inpl()
	for (j, x) in enumerate(a):
		for cnt in range(m // 2):
			for mo in range(K):
				dp[ind(j + 1, cnt, mo)] = dp[ind(j, cnt, mo)]
		for cnt in range(m // 2):
			for mo in range(K):
				now = dp[ind(j, cnt, mo)]
				dp[ind(j + 1, cnt + 1, (now + x) % K)] = max(dp[ind(j, cnt + 1, (now + x) % K)], dp[ind(j + 1, cnt + 1, (now + x) % K)], now + x)
	for mo in range(K):
		mx = 0
		for j in range(m + 1):
			for cnt in range(m // 2 + 1):
				mx = max(dp[ind(j, cnt, mo)], mx)
		for mm in range(K):
			if DP[IND(i, mm)] % K != mm:
				continue
			now = DP[IND(i, mm)]
			DP[IND(i + 1, (now + mx) % K)] = max(DP[IND(i, (now + mx) % K)], DP[IND(i + 1, (now + mx) % K)], now + mx)
print(DP[IND(n, 0)])


MAX = 10000000000
MIN = -10000000000
(n, m, k) = map(int, input().split())
L = []
for i in range(0, n):
	s = [int(x) for x in input().split()]
	L.append(s)
ln = m // 2
mx = [MIN] * k
mx[0] = 0
for i in range(n):
	mx2 = [MIN] * k
	mx2[0] = 0
	dp = [MAX] * 2455
	dp[0] = 0
	for j in range(m):
		for e in range(len(dp) - 1, -1, -1):
			if e + L[i][j] < len(dp) and dp[e] + 1 <= ln and (dp[e] != MAX):
				dp[e + L[i][j]] = min(dp[e + L[i][j]], dp[e] + 1)
	for j in range(len(dp)):
		if dp[j] != MAX:
			for e in range(k):
				if mx[e] != MIN:
					mx2[(j + e) % k] = max(mx2[(j + e) % k], mx[e] + j)
	mx = []
	for j in range(k):
		mx.append(mx2[j])
print(mx[0])


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def output(*args):
	sys.stdout.buffer.write(('\n'.join(map(str, args)) + '\n').encode('utf-8'))

def main():
	(n, m, k) = map(int, input().split())
	mat = [tuple(map(int, input().split())) for _ in range(n)]
	take_max = m // 2
	minf = -10 ** 9
	dp_row = [[minf] * k for _ in range(take_max + 1)]
	dp = [[minf] * k for _ in range(n + 1)]
	dp[0][0] = dp_row[0][0] = 0
	for (i, row) in enumerate(mat):
		for (j, val) in enumerate(row):
			for dp_i in range(min(j + 1, take_max - 1), -1, -1):
				for dp_j in range(k):
					if dp_row[dp_i][dp_j] == minf:
						continue
					nmod = (dp_j + val) % k
					dp_row[dp_i + 1][nmod] = max(dp_row[dp_i + 1][nmod], dp_row[dp_i][dp_j] + val)
		for mod in range(k):
			max_val = minf
			for j in range(take_max + 1):
				max_val = max(max_val, dp_row[j][mod])
				dp_row[j][mod] = minf
			if max_val == minf:
				continue
			for pmod in range(k):
				dp[i + 1][(mod + pmod) % k] = max(dp[i + 1][(mod + pmod) % k], dp[i][pmod] + max_val)
		dp_row[0][0] = 0
	print(dp[-1][0])
main()


(n, m, k) = map(int, input().split())
dp = [-10000000000 for i in range(k)]
dp[0] = 0
sz = m // 2
mat = []
for i in range(n):
	mat.append(list(map(int, input().split())))
for a in mat:
	pre = dp
	dp = [[-10000000000 for i in range(k)] for j in range(sz + 1)]
	dp[0] = pre
	for x in a:
		for i in range(sz, 0, -1):
			for j in range(k):
				dp[i][j] = max(dp[i][j], dp[i - 1][((j - x) % k + k) % k] + x)
	for i in range(1, sz + 1):
		for j in range(k):
			dp[0][j] = max(dp[0][j], dp[i][j])
	dp = dp[0]
print(dp[0])


from sys import stdin, stdout

def zero_remainder_sum(n, m, k, a_a):
	cnt = m // 2
	dp = [[[-1 for _ in range(k)] for _ in range(cnt + 1)] for _ in range(n)]
	dp[0][0][0] = 0
	for i in range(n):
		for j in range(m):
			for c in range(min(m // 2 + 1, j + 2) - 1, 0, -1):
				for r in range(k):
					if dp[i][c - 1][r] == -1:
						continue
					v = dp[i][c - 1][r] + a_a[i][j]
					dp[i][c][v % k] = max(dp[i][c][v % k], v)
		if i != n - 1:
			for c in range(0, cnt + 1):
				for r in range(k):
					dp[i + 1][0][r] = max(dp[i + 1][0][r], dp[i][c][r])
	res = 0
	for i in range(cnt + 1):
		res = max(res, dp[n - 1][i][0])
	return res
(n, m, k) = map(int, stdin.readline().split())
a_a = []
for _ in range(n):
	a_a.append(list(map(int, stdin.readline().split())))
res = zero_remainder_sum(n, m, k, a_a)
stdout.write(str(res))


(m, n, k) = map(int, input().split())
matrix = []
for i in range(m):
	arr = list(map(int, input().split()))
	matrix.append(arr)
dp = [[[[-1 for q in range(n // 2 + 1)] for p in range(k)] for j in range(n)] for i in range(m + 1)]
for p in range(k):
	if p == 0:
		dp[m][0][p][n // 2] = 0
	else:
		dp[m][0][p][n // 2] = -2147483647
for i in range(m - 1, -1, -1):
	for j in range(n - 1, -1, -1):
		for p in range(k):
			for q in range(n // 2 + 1):
				if j == n - 1:
					(nexti, nextj) = (i + 1, 0)
				else:
					(nexti, nextj) = (i, j + 1)
				if j == n - 1:
					num1 = dp[nexti][nextj][p][n // 2]
				else:
					num1 = dp[nexti][nextj][p][q]
				if q > 0:
					if j == n - 1:
						num2 = dp[nexti][nextj][(p + matrix[i][j]) % k][n // 2] + matrix[i][j]
					else:
						num2 = dp[nexti][nextj][(p + matrix[i][j]) % k][q - 1] + matrix[i][j]
				else:
					num2 = -2147483647
				dp[i][j][p][q] = max(num1, num2)
print(dp[0][0][0][n // 2])


import sys
input = sys.stdin.readline
(N, M, K) = map(int, input().split())
a = [sorted(list(map(int, input().split()))) for _ in range(N)]
ln = 70 * M + 1
dp = [[70] * ln for _ in range(N)]
for i in range(N):
	dp[i][0] = 0
	for j in range(M):
		for k in range(ln - 1, -1, -1):
			if k + a[i][j] < ln:
				dp[i][k + a[i][j]] = min(dp[i][k + a[i][j]], dp[i][k] + 1)
t = [[0] * K for _ in range(N)]
for i in range(N):
	for j in range(ln):
		if dp[i][j] <= M // 2:
			t[i][j % K] = max(t[i][j % K], j)
dp2 = [[-10 ** 9] * K for _ in range(N + 1)]
dp2[0][0] = 0
for i in range(N):
	for j in range(K):
		for k in range(K):
			if t[i][k] == 0 and k > 0:
				continue
			if dp2[i][j] != -10 ** 9:
				dp2[i + 1][(j + k) % K] = max(dp2[i + 1][(j + k) % K], dp2[i][j] + t[i][k])
print(dp2[-1][0])


(n, m, k) = map(int, input().split())
mat = [list(map(int, input().split())) for i in range(n)]
inf = 1 << 30
modulars = [[-inf] * k for i in range(n)]
for index in range(n):
	a = mat[index]
	dp = [[[-inf] * k for i in range(m // 2 + 1)] for _ in range(m + 1)]
	dp[0][0][0] = 0
	for i in range(1, m + 1):
		v = a[i - 1]
		for picked in range(m // 2 + 1):
			for mod in range(k):
				if picked >= 1:
					dp[i][picked][mod] = max(dp[i][picked][mod], dp[i - 1][picked][mod], dp[i - 1][picked - 1][(mod - v) % k] + v)
				else:
					dp[i][picked][mod] = max(dp[i][picked][mod], dp[i - 1][picked][mod])
	for mod in range(k):
		modulars[index][mod] = max((dp[m][picked][mod] for picked in range(m // 2 + 1)))
dp = [[-inf] * k for i in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
	for mod in range(k):
		dp[i][mod] = max((dp[i - 1][(mod - prevmod) % k] + modulars[i - 1][prevmod] for prevmod in range(k)))
ans = dp[n][0]
print(ans)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass

def pmat(A):
	for ele in A:
		print(*ele, end='\n')

def seive():
	prime = [1 for i in range(10 ** 6 + 1)]
	prime[0] = 0
	prime[1] = 0
	for i in range(10 ** 6 + 1):
		if prime[i]:
			for j in range(2 * i, 10 ** 6 + 1, i):
				prime[j] = 0
	return prime
inf = 1000000007
(n, m, k) = map(int, input().split())
dp = [-inf for i in range(k)]
dp[0] = 0
sz = m // 2
for _ in range(n):
	a = list(map(int, input().split()))
	pre = dp
	dp = [[-inf for _ in range(k)] for _ in range(sz + 1)]
	dp[0] = pre
	for x in a:
		for i in range(sz, 0, -1):
			for j in range(k):
				dp[i][j] = max(dp[i][j], dp[i - 1][((j - x) % k + k) % k] + x)
	for i in range(1, sz + 1):
		for j in range(k):
			dp[0][j] = max(dp[0][j], dp[i][j])
	dp = dp[0]
print(dp[0])
endtime = time.time()


import copy

def get_h(data, n, k):
	h = []
	for _ in range(k):
		h.append([0] * (n + 1))
	hh = copy.deepcopy(h)
	for v in data:
		for j in range(1, n + 1):
			for i in range(k):
				t = (h[i][j - 1] + v) % k
				tt = (i + v) % k
				if t == tt:
					hh[t][j] = max(hh[t][j], h[i][j - 1] + v)
		(hh, h) = (h, hh)
		for j in range(0, n + 1):
			for i in range(k):
				hh[i][j] = h[i][j]
	return [max(t) for t in h]
(n, m, k) = list(map(int, input().split()))
bh = [0] * k
tbh = [0] * k
for _ in range(n):
	data = list(map(int, input().split()))
	h = get_h(data, m // 2, k)
	for t in range(k):
		for i in range(k):
			j = (t - i + k) % k
			if (bh[i] + h[j]) % k == t:
				tbh[t] = max(tbh[t], bh[i] + h[j])
	(bh, tbh) = (tbh, bh)
	for i in range(k):
		tbh[i] = bh[i]
print(bh[0])


import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
INF = 10 ** 6
dp = [-INF] * k
dp[0] = 0
for i in range(n):
	a = list(map(int, input().split()))
	pre = dp
	dp = [[-INF] * k for i in range(m // 2 + 1)]
	dp[0] = pre
	for j in range(m):
		for l in range(1, m // 2 + 1)[::-1]:
			for h in range(k):
				dp[l][h] = max(dp[l][h], dp[l - 1][(h - a[j]) % k] + a[j])
	for j in range(1, m // 2 + 1):
		for l in range(k):
			dp[0][l] = max(dp[0][l], dp[j][l])
	dp = dp[0]
print(dp[0])


import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(n)]
DP = [-1] * k
DP[0] = 0
for i in range(n):
	DP0 = [[-1] * k for i in range(m // 2 + 1)]
	DP0[0][0] = 0
	for a in A[i]:
		for i in range(m // 2 - 1, -1, -1):
			for j in range(k - 1, -1, -1):
				if DP0[i][j] != -1:
					DP0[i + 1][(j + a) % k] = max(DP0[i + 1][(j + a) % k], DP0[i][j] + a)
	NDP = [-1] * k
	for i in range(m // 2 + 1):
		for j in range(k):
			if DP0[i][j] == -1:
				continue
			for d in range(k):
				if DP[d] == -1:
					continue
				NDP[(d + j) % k] = max(NDP[(d + j) % k], DP[d] + DP0[i][j])
	DP = NDP
print(DP[0])


from collections import *
import sys
input = sys.stdin.readline
N = 75
INF = 10 ** 18

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

def solve():
	(N, M, K) = rl()
	S = []
	for n in range(N):
		S.append(rl())
	tmp = []
	for n in range(N):
		dp = [[-INF for k in range(K)] for m in range(M // 2 + 1)]
		dp[0][0] = 0
		for m in range(M):
			for m2 in range(M // 2 - 1, -1, -1):
				for k in range(K):
					dp[m2 + 1][(k + S[n][m]) % K] = max(dp[m2 + 1][(k + S[n][m]) % K], dp[m2][k] + S[n][m])
		dp2 = [-INF] * K
		for m2 in range(M // 2 + 1):
			for k in range(K):
				dp2[k] = max(dp2[k], dp[m2][k])
		tmp.append(dp2)
	ans = list(tmp[0])
	for n in range(1, N):
		curr = list(tmp[n])
		tmp2 = [-10 ** 18] * K
		for k1 in range(K):
			for k2 in range(K):
				tmp2[(k1 + k2) % K] = max(tmp2[(k1 + k2) % K], curr[k1] + ans[k2])
		ans = list(tmp2)
	return ans[0]
print(solve())


(n, m, k) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
s = []
for q in a:
	d = [0] + [float('inf')] * 4999
	for q1 in q:
		d1 = d[:]
		for q2 in range(5000):
			if d1[q2] + 1 <= m // 2:
				d[q2 + q1] = min(d1[q2 + q1], d1[q2] + 1)
	ans = [0] + [-float('inf')] * (k - 1)
	for q1 in range(5000):
		if d[q1] != float('inf'):
			ans[q1 % k] = max(ans[q1 % k], q1)
	s.append(ans)
ans = [0] + [-float('inf')] * (k - 1)
for q in range(n):
	ans1 = ans[:]
	for q1 in range(k):
		for q2 in range(k):
			ans[(q1 + q2) % k] = max(ans[(q1 + q2) % k], ans1[q1] + s[q][q2])
print(ans[0])


import math
from sys import stdin
import sys
sys.setrecursionlimit(300000)
(n, m, k) = map(int, stdin.readline().split())
a = []
for i in range(n):
	tmp = list(map(int, stdin.readline().split()))
	a.append(tmp)
maxlis = []
for i in range(n):
	tdp = [[float('-inf')] * k for i in range(m // 2 + 1)]
	tdp[0][0] = 0
	for j in range(m):
		for x in range(len(tdp) - 2, -1, -1):
			for y in range(k):
				tdp[x + 1][(y + a[i][j]) % k] = max(tdp[x + 1][(y + a[i][j]) % k], tdp[x][y] + a[i][j])
	udp = [float('-inf')] * k
	for x in range(len(tdp)):
		for y in range(k):
			udp[y] = max(udp[y], tdp[x][y])
	maxlis.append(udp)
dp = maxlis[0]
for i in range(1, len(maxlis)):
	now = maxlis[i]
	ndp = [float('-inf')] * k
	for x in range(k):
		for y in range(k):
			ndp[(x + y) % k] = max(ndp[(x + y) % k], dp[x] + now[y])
	dp = ndp
print(dp[0])


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(N, M, K) = map(int, input().split())
half = M // 2
W = []
for _ in range(N):
	A = list(map(int, input().split()))
	dp = [[[-(1 << 30)] * K for _ in range(half + 2)] for _ in range(M + 1)]
	dp[0][0][0] = 0
	for (i, a) in enumerate(A, 1):
		for j in range(half + 1):
			for k in range(K):
				v1 = a + dp[i - 1][j - 1][(k - a) % K]
				v2 = dp[i - 1][j][k]
				dp[i][j][k] = v1 if v1 > v2 else v2
	w = [max((dp[M][j][k] for j in range(half + 1))) for k in range(K)]
	W.append(w)

def conv(A, B):
	n = len(A)
	res = [-(1 << 30)] * n
	for (i, a) in enumerate(A):
		for (j, b) in enumerate(B):
			idx = (i + j) % n
			if res[idx] < a + b:
				res[idx] = a + b
	return res
w0 = W[0]
for w in W[1:]:
	w0 = conv(w0, w)
print(w0[0])


INF = int(1000000000.0)
(n, m, k) = map(int, input().split())
a = [[] for i in range(n)]
for i in range(n):
	for j in map(int, input().split()):
		a[i].append(j)
dp = [[[-INF for q in range(k)] for p in range(m + 1)] for j in range(m)]
best = [-INF for q in range(k)]
best[0] = 0
for i in range(n):
	for j in range(m):
		for p in range(m + 1):
			for q in range(k):
				if p > j + 1 or p > m // 2:
					dp[j][p][q] = -INF
				elif j == 0:
					dp[j][p][q] = max(a[i][j] + best[(q - a[i][j] + k) % k] if p == 1 else -INF, best[q])
				else:
					dp[j][p][q] = max(a[i][j] + dp[j - 1][p - 1][(q - a[i][j] + k) % k], dp[j - 1][p][q])
		for q in range(k):
			for p in range(m + 1):
				best[q] = max(best[q], dp[m - 1][p][q])
print(best[0])


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections as col

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def solve():
	(N, M, K) = getInts()
	S = []
	for n in range(N):
		S.append(getInts())
	tmp = []
	for n in range(N):
		dp = [[-10 ** 18 for k in range(K)] for m in range(M // 2 + 1)]
		dp[0][0] = 0
		for m in range(M):
			for m2 in range(M // 2 - 1, -1, -1):
				for k in range(K):
					dp[m2 + 1][(k + S[n][m]) % K] = max(dp[m2 + 1][(k + S[n][m]) % K], dp[m2][k] + S[n][m])
		dp2 = [-10 ** 18] * K
		for m2 in range(M // 2 + 1):
			for k in range(K):
				dp2[k] = max(dp2[k], dp[m2][k])
		tmp.append(dp2)
	ans = list(tmp[0])
	for n in range(1, N):
		curr = list(tmp[n])
		tmp2 = [-10 ** 18] * K
		for k1 in range(K):
			for k2 in range(K):
				tmp2[(k1 + k2) % K] = max(tmp2[(k1 + k2) % K], curr[k1] + ans[k2])
		ans = list(tmp2)
	return ans[0]
print(solve())


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16
(n, m, k) = MI()
aa = LLI(n)

def solve(row):

	def chmax(i, j, val):
		if val > dp[i][j]:
			dp[i][j] = val
	dp = [[-inf] * (m // 2 + 1) for _ in range(k)]
	dp[0][0] = 0
	for a in row:
		for j in range(m // 2 - 1, -1, -1):
			for i in range(k):
				pre = dp[i][j]
				if pre == -1:
					continue
				ni = (i + a) % k
				chmax(ni, j + 1, pre + a)
	return [max(dp[i]) for i in range(k)]
ss = [solve(aa[i]) for i in range(n)]
dp = [[-inf] * k for _ in range(n + 1)]
dp[0][0] = 0
for (i, row) in enumerate(ss):
	for j in range(k):
		dp[i + 1][j] = max((dp[i][(j - r) % k] + s for (r, s) in enumerate(row)))
print(dp[-1][0])


import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def solve():
	(n, m, k) = map(int, input().split())
	mat = []
	for i in range(n):
		mat.append(list(map(int, input().split())))
	ma = m // 2
	dp = [[0 for j in range(k)] for i in range(n)]
	for i in range(n):
		dpma = [[0 for a in range(k)] for b in range(ma + 1)]
		for j in range(m):
			for y in reversed(range(1, ma + 1)):
				for x in range(k):
					if dpma[y - 1][(x - mat[i][j]) % k] != 0 or (y == 1 and mat[i][j] % k == x):
						dpma[y][x] = max(dpma[y][x], dpma[y - 1][(x - mat[i][j]) % k] + mat[i][j])
						dp[i][x] = max(dp[i][x], dpma[y][x])
	ans = 0
	dpans = [0 for i in range(k)]
	for i in range(n):
		dpans2 = [0 for i in range(k)]
		for x in range(k):
			for j in range(k):
				if (dpans[(x - j) % k] != 0 or dp[i][j] % k == x) and dp[i][j] != 0:
					dpans2[x] = max(dpans2[x], dpans[(x - j) % k] + dp[i][j])
		for x in range(k):
			dpans[x] = max(dpans[x], dpans2[x])
	print(dpans[0])

def main():
	t = 1
	for _ in range(t):
		solve()
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
	(n, m, k) = map(int, input().split())
	max_sum_mod = [0] * k
	for __ in range(n):
		a = list(map(int, input().split()))
		dp = [[0] * k for __ in range(1 + m // 2)]
		for each in a:
			for i in range(m // 2, 0, -1):
				for j in range(k):
					dp[i][(each + dp[i - 1][j]) % k] = max(dp[i][(each + dp[i - 1][j]) % k], each + dp[i - 1][j])
		max_sum_mod_copy = list(max_sum_mod)
		for i in range(k):
			for j in range(k):
				if (max_sum_mod[(i - j) % k] == 0 or dp[-1][j] == 0) and i != j:
					continue
				if i == j and dp[-1][j] == 0:
					continue
				max_sum_mod_copy[i] = max(max_sum_mod_copy[i], dp[-1][j] + max_sum_mod[(i - j) % k])
		max_sum_mod = list(max_sum_mod_copy)
	print(max_sum_mod[0])


from pprint import pprint
import sys
import math
iinf = -10 ** 18
(n, m, k) = map(int, input().split())
maxselect = m // 2
maze = []
for i in range(n):
	l = list(map(int, input().split()))
	maze.append(l)
dp2 = []
for hh in range(n):
	dp = []
	for i in range(m + 10):
		l = [None] * k
		dp.append(l)
	dp[0][0] = 0
	for ww in range(m):
		v = maze[hh][ww]
		for i in range(maxselect, 0, -1):
			for j in range(k):
				newj = (j + v) % k
				oldjnum = dp[i - 1][j]
				if oldjnum is None:
					continue
				if dp[i][newj] is None:
					dp[i][newj] = iinf
				dp[i][newj] = max(dp[i][newj], oldjnum + v)
	l = [iinf] * k
	for i in range(k):
		for j in range(len(dp)):
			if dp[j][i] is None:
				dp[j][i] = iinf
			l[i] = max(l[i], dp[j][i])
	dp2.append(l)
res = []
for i in range(n + 1):
	l = [None] * k
	res.append(l)
res[0][0] = 0
from copy import deepcopy
for i in range(0, n):
	for orij in range(k):
		if res[i][orij] is None:
			continue
		for newj in range(k):
			newjj = (newj + orij) % k
			if res[i + 1][newjj] is None:
				res[i + 1][newjj] = iinf
			res[i + 1][newjj] = max(res[i + 1][newjj], res[i][orij] + dp2[i][newj])
print(res[n][0])


import io
import os
from collections import Counter, defaultdict, deque

def solve(R, C, K, grid):
	assert len(grid) == R
	assert len(grid[0]) == C
	half = C // 2

	def pack(a, b):
		return a * 128 + b

	def unpack(ab):
		return divmod(ab, 128)
	inf = float('inf')
	dp = []
	for row in grid:
		possible = {pack(0, 0): 0}
		for x in row:
			nextPossible = defaultdict(int)
			nextPossible.update(possible)
			for (oldKey, mx) in possible.items():
				(mod, count) = unpack(oldKey)
				if count + 1 <= half:
					key = pack((mod + x) % K, count + 1)
					nextPossible[key] = max(nextPossible[key], mx + x)
			possible = nextPossible
		dpRow = [-inf] * K
		for (oldKey, mx) in possible.items():
			(mod, count) = unpack(oldKey)
			dpRow[mod] = max(dpRow[mod], mx)
		dp.append(dpRow)
	ans = [-inf] * K
	ans[0] = 0
	for row in dp:
		nextAns = list(ans)
		for (mod, mx) in enumerate(row):
			for (k, v) in enumerate(ans):
				nextAns[(mod + k) % K] = max(nextAns[(mod + k) % K], mx + v)
		ans = nextAns
	return ans[0]
DEBUG = False
if DEBUG:
	import random
	random.seed(0)
	for _ in range(1):
		N = 70
		M = 70
		K = random.randint(1, 70)
		grid = [[random.randint(1, 70) for i in range(M)] for i in range(N)]
		ans1 = solve(N, M, K, grid)
		print(ans1)
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = 1
for tc in range(1, TC + 1):
	(N, M, K) = [int(x) for x in input().split()]
	grid = [[int(x) for x in input().split()] for i in range(N)]
	ans = solve(N, M, K, grid)
	print(ans)


(n, m, k) = [int(x) for x in input().split()]
remainderMax = [-float('inf') for _ in range(k)]
remainderMax[0] = 0
for _ in range(n):
	arr = [int(x) for x in input().split()]
	dp = [[-float('inf') for __ in range(k)] for ___ in range(m // 2 + 1)]
	dp[0][0] = 0
	for x in arr:
		for nE in range(m // 2, 0, -1):
			if nE == 1:
				dp[nE][x % k] = max(dp[nE][x % k], x)
			if nE >= 2:
				for r in range(k):
					dp[nE][r] = max(dp[nE][r], x + dp[nE - 1][(r - x % k + k) % k])
	dp2 = [-float('inf') for __ in range(k)]
	for r in range(k):
		for nE in range(m // 2 + 1):
			dp2[r] = max(dp2[r], dp[nE][r])
	remainderMax2 = [-float('inf') for __ in range(k)]
	for r1 in range(k):
		for r2 in range(k):
			r3 = (r1 + r2) % k
			remainderMax2[r3] = max(remainderMax2[r3], remainderMax[r1] + dp2[r2])
	remainderMax = remainderMax2
print(remainderMax[0])


import os, sys
from io import BytesIO, IOBase

def main():
	(n, m, k) = map(int, input().split())
	arr = [list(map(int, input().split())) for _ in range(n)]
	dp = [[[0] * k for _ in range(m // 2 + 1)] for _ in range(n)]
	for i in range(n):
		for j in range(m):
			for r in range(min(m // 2 + 1, j + 2) - 1, 0, -1):
				for x in range(k):
					y = arr[i][j] + dp[i][r - 1][x]
					dp[i][r][y % k] = max(dp[i][r][y % k], y)
		if i != n - 1:
			for xx in range(k):
				for yy in range(m // 2 + 1):
					dp[i + 1][0][xx] = max(dp[i + 1][0][xx], dp[i][yy][xx])
	a = 0
	for i in range(m // 2 + 1):
		a = max(a, dp[-1][i][0])
	print(a)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from math import inf
(n, m, k) = map(int, input().split())
matx = [[-inf] * k for i in range(n)]
dp = [[[0] * k for i in range(m // 2 + 1)] for j in range(m + 1)]
for _ in range(n):
	a = [int(x) for x in input().split()]
	for i in range(m // 2 + 1):
		for j in range(k):
			dp[0][i][j] = -inf
	dp[0][0][0] = 0
	for i in range(m):
		for j in range(m // 2 + 1):
			for p in range(k):
				dp[i + 1][j][p] = dp[i][j][p]
				if j > 0:
					dp[i + 1][j][p] = max(dp[i][j - 1][(p - a[i]) % k] + a[i], dp[i + 1][j][p])
				matx[_][p] = max(matx[_][p], dp[i + 1][j][p])
dp12 = [[-inf] * k for i in range(n)]
dp12[0] = matx[0][:]
for i in range(1, n):
	for j in range(k):
		dp12[i][j] = dp12[i - 1][j]
		for p in range(k):
			if matx[i][p] != -inf:
				dp12[i][j] = max(dp12[i - 1][(j - matx[i][p]) % k] + matx[i][p], dp12[i][j])
print(dp12[n - 1][0])