#include <bits/stdc++.h>
using namespace std;
long long power(long long a, long long b, long long m) {
  long long ans = 1;
  a = a % m;
  if (a == 0) return 0;
  while (b) {
    if (b & 1) ans = (ans * a) % m;
    b /= 2;
    a = (a * a) % m;
  }
  return ans;
}
long long modInverse(long long a, long long m) { return power(a, m - 2, m); }
long long binpow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
long long binlog2(long long n) {
  long long logValue = -1;
  while (n) {
    logValue++;
    n >>= 1;
  }
  return logValue;
}
long long ceil(long long t1, long long t2) {
  long long ans = (t1 + t2 - 1) / t2;
  return ans;
}
void print(vector<long long> a) {
  for (int i = 0; i < a.size(); i++) cout << a[i] << " ";
  cout << "\n";
}
const long long mod = 1e9 + 7;
const long long N = 4e5 + 5;
const long long inf = 2e18;
long long dp[75][75][75][75];
long long n, m, k;
long long a[75][75];
long long ans;
long long recur(long long i, long long j, long long cnt, long long rem) {
  if (i == n - 1 && j == m - 1) {
    if (cnt < m / 2 && (rem + a[i][j]) % k == 0)
      return a[i][j];
    else if (rem == 0)
      return 0;
    else
      return -1 * inf;
  }
  if (dp[i][j][cnt][rem] != 0) return dp[i][j][cnt][rem];
  if (j == m) {
    return dp[i][j][cnt][rem] = recur(i + 1, 0, 0, rem);
  }
  if (i == n) {
    if (rem == 0)
      return 0;
    else
      return -1 * inf;
  }
  if (cnt < m / 2) {
    long long t1 = a[i][j] + recur(i, j + 1, cnt + 1, (a[i][j] + rem) % k);
    long long t2 = recur(i, j + 1, cnt, rem);
    return dp[i][j][cnt][rem] = max(t1, t2);
  } else {
    return dp[i][j][cnt][rem] = recur(i + 1, 0, 0, rem);
  }
}
void solve() {
  cin >> n >> m >> k;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) cin >> a[i][j];
  cout << recur(0, 0, 0, 0) << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int test = 1;
  while (test--) {
    solve();
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

You are given a matrix a of size n × m consisting of integers.

You can choose no more than \left⌊m/2\right⌋ 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 ≤ n, m, k ≤ 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 ≤ a_{i, j} ≤ 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long power(long long a, long long b, long long m) {
  long long ans = 1;
  a = a % m;
  if (a == 0) return 0;
  while (b) {
    if (b & 1) ans = (ans * a) % m;
    b /= 2;
    a = (a * a) % m;
  }
  return ans;
}
long long modInverse(long long a, long long m) { return power(a, m - 2, m); }
long long binpow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
long long binlog2(long long n) {
  long long logValue = -1;
  while (n) {
    logValue++;
    n >>= 1;
  }
  return logValue;
}
long long ceil(long long t1, long long t2) {
  long long ans = (t1 + t2 - 1) / t2;
  return ans;
}
void print(vector<long long> a) {
  for (int i = 0; i < a.size(); i++) cout << a[i] << " ";
  cout << "\n";
}
const long long mod = 1e9 + 7;
const long long N = 4e5 + 5;
const long long inf = 2e18;
long long dp[75][75][75][75];
long long n, m, k;
long long a[75][75];
long long ans;
long long recur(long long i, long long j, long long cnt, long long rem) {
  if (i == n - 1 && j == m - 1) {
    if (cnt < m / 2 && (rem + a[i][j]) % k == 0)
      return a[i][j];
    else if (rem == 0)
      return 0;
    else
      return -1 * inf;
  }
  if (dp[i][j][cnt][rem] != 0) return dp[i][j][cnt][rem];
  if (j == m) {
    return dp[i][j][cnt][rem] = recur(i + 1, 0, 0, rem);
  }
  if (i == n) {
    if (rem == 0)
      return 0;
    else
      return -1 * inf;
  }
  if (cnt < m / 2) {
    long long t1 = a[i][j] + recur(i, j + 1, cnt + 1, (a[i][j] + rem) % k);
    long long t2 = recur(i, j + 1, cnt, rem);
    return dp[i][j][cnt][rem] = max(t1, t2);
  } else {
    return dp[i][j][cnt][rem] = recur(i + 1, 0, 0, rem);
  }
}
void solve() {
  cin >> n >> m >> k;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) cin >> a[i][j];
  cout << recur(0, 0, 0, 0) << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int test = 1;
  while (test--) {
    solve();
  }
  return 0;
}

```