#include <bits/stdc++.h>
const long long LL_INF = (long long)2e18 + 5;
using namespace std;
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
const long long N = 72, mod = 1e9 + 7;
void solve() {
  long long n, m;
  cin >> n >> m;
  long long k, lim = m / 2;
  cin >> k;
  vector<vector<long long>> v(n, vector<long long>(m));
  for (long long i = (long long)(0); i < (long long)(n); i++)
    for (long long j = (long long)(0); j < (long long)(m); j++) cin >> v[i][j];
  vector<long long> dp(k, -0x3f3f3f3f);
  dp[0] = 0;
  for (long long i = (long long)(0); i < (long long)(n); i++) {
    vector<vector<long long>> row_dp(lim + 1,
                                     vector<long long>(k, -0x3f3f3f3f));
    row_dp[0][0] = 0;
    for (long long j = (long long)(0); j < (long long)(m); j++)
      for (long long use = (long long)(lim - 1); use >= (long long)(0); use--)
        for (long long rem = (long long)(0); rem < (long long)(k); rem++) {
          long long new_rem = (rem + v[i][j]) % k;
          long long new_use = use + 1;
          row_dp[new_use][new_rem] =
              max(row_dp[new_use][new_rem], row_dp[use][rem] + v[i][j]);
        }
    vector<long long> fdp = dp;
    for (long long rem = (long long)(0); rem < (long long)(k); rem++)
      for (long long use = (long long)(0); use < (long long)(lim + 1); use++)
        for (long long remm = (long long)(0); remm < (long long)(k); remm++) {
          long long new_rem = (rem + remm) % k;
          fdp[new_rem] = max(fdp[new_rem], dp[rem] + row_dp[use][remm]);
        }
    dp = fdp;
  }
  cout << dp[0] << '\n';
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  solve();
}

### Prompt

Your task is to create a CPP solution to the following problem:

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>
const long long LL_INF = (long long)2e18 + 5;
using namespace std;
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
const long long N = 72, mod = 1e9 + 7;
void solve() {
  long long n, m;
  cin >> n >> m;
  long long k, lim = m / 2;
  cin >> k;
  vector<vector<long long>> v(n, vector<long long>(m));
  for (long long i = (long long)(0); i < (long long)(n); i++)
    for (long long j = (long long)(0); j < (long long)(m); j++) cin >> v[i][j];
  vector<long long> dp(k, -0x3f3f3f3f);
  dp[0] = 0;
  for (long long i = (long long)(0); i < (long long)(n); i++) {
    vector<vector<long long>> row_dp(lim + 1,
                                     vector<long long>(k, -0x3f3f3f3f));
    row_dp[0][0] = 0;
    for (long long j = (long long)(0); j < (long long)(m); j++)
      for (long long use = (long long)(lim - 1); use >= (long long)(0); use--)
        for (long long rem = (long long)(0); rem < (long long)(k); rem++) {
          long long new_rem = (rem + v[i][j]) % k;
          long long new_use = use + 1;
          row_dp[new_use][new_rem] =
              max(row_dp[new_use][new_rem], row_dp[use][rem] + v[i][j]);
        }
    vector<long long> fdp = dp;
    for (long long rem = (long long)(0); rem < (long long)(k); rem++)
      for (long long use = (long long)(0); use < (long long)(lim + 1); use++)
        for (long long remm = (long long)(0); remm < (long long)(k); remm++) {
          long long new_rem = (rem + remm) % k;
          fdp[new_rem] = max(fdp[new_rem], dp[rem] + row_dp[use][remm]);
        }
    dp = fdp;
  }
  cout << dp[0] << '\n';
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  solve();
}

```