/*  -*- coding: utf-8 -*-
 *
 * d.cc: D: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

const int MAX_X = 100000;
const int MAX_M = 100000;

/* typedef */

/* global variables */

int ds[MAX_X + 1], cs[MAX_M], hcs[MAX_M];

/* subroutines */

/* main */

int main() {
  int n, m;
  cin >> n >> m;

  int maxx = 0;
  for (int i = 0; i < n; i++) {
    int xi;
    cin >> xi;
    ds[xi]++;
    if (maxx < xi) maxx = xi;
  }

  for (int x = 0; x <= maxx; x++) {
    int i = x % m;
    cs[i] += ds[x];
    hcs[i] += ds[x] / 2;
  }
  //for (int i = 0; i < m; i++) printf("%d %d %d\n", i, cs[i], hcs[i]);
  
  int cnt = 0;
  for (int i = 0, j = m; i <= j; i++, j--) {
    if (i == 0 || i == j)
      cnt += cs[i] / 2;
    else {
      if (cs[i] >= cs[j]) {
	cnt += cs[j];
	int d = (cs[i] - cs[j]) / 2;
	cnt += min(hcs[i], d);
      }
      else {
	cnt += cs[i];
	int d = (cs[j] - cs[i]) / 2;
	cnt += min(hcs[j], d);
      }
    }
  }

  printf("%d\n", cnt);
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

Takahashi is playing with N cards.

The i-th card has an integer X_i on it.

Takahashi is trying to create as many pairs of cards as possible satisfying one of the following conditions:

* The integers on the two cards are the same.
* The sum of the integers on the two cards is a multiple of M.



Find the maximum number of pairs that can be created.

Note that a card cannot be used in more than one pair.

Constraints

* 2≦N≦10^5
* 1≦M≦10^5
* 1≦X_i≦10^5

Input

The input is given from Standard Input in the following format:


N M
X_1 X_2 ... X_N


Output

Print the maximum number of pairs that can be created.

Examples

Input

7 5
3 1 4 1 5 9 2


Output

3


Input

15 10
1 5 6 10 11 11 11 20 21 25 25 26 99 99 99


Output

6

### Response

```cpp
/*  -*- coding: utf-8 -*-
 *
 * d.cc: D: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

const int MAX_X = 100000;
const int MAX_M = 100000;

/* typedef */

/* global variables */

int ds[MAX_X + 1], cs[MAX_M], hcs[MAX_M];

/* subroutines */

/* main */

int main() {
  int n, m;
  cin >> n >> m;

  int maxx = 0;
  for (int i = 0; i < n; i++) {
    int xi;
    cin >> xi;
    ds[xi]++;
    if (maxx < xi) maxx = xi;
  }

  for (int x = 0; x <= maxx; x++) {
    int i = x % m;
    cs[i] += ds[x];
    hcs[i] += ds[x] / 2;
  }
  //for (int i = 0; i < m; i++) printf("%d %d %d\n", i, cs[i], hcs[i]);
  
  int cnt = 0;
  for (int i = 0, j = m; i <= j; i++, j--) {
    if (i == 0 || i == j)
      cnt += cs[i] / 2;
    else {
      if (cs[i] >= cs[j]) {
	cnt += cs[j];
	int d = (cs[i] - cs[j]) / 2;
	cnt += min(hcs[i], d);
      }
      else {
	cnt += cs[i];
	int d = (cs[j] - cs[i]) / 2;
	cnt += min(hcs[j], d);
      }
    }
  }

  printf("%d\n", cnt);
  return 0;
}

```