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: introductory

Starter code:

Solutions:
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()


"""

70*70*70
70*70*70

dp[num][k] = ?

"""

import math
from sys import stdin

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 (maxlis)
print (dp[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 = list(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)


n, m, k = list(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[index][picked][mod] = index番目まで見てそのうちpicked個取ってmodular(mod k) になる時の最大値
    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
#dp[n][mod] = n番目まで見て総和がmodの時の最大値
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)




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))


n,m,k = list(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(list(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)
#print(dp1)
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))