/*************************************************************************
  >         File: D.cc
  >       Author: lyyllyyl
  >         Mail: riho.yoshioka@yandex.com
  > Created Time: Sun 27 Nov 2016 12:20:21 AM JST
*************************************************************************/
#include <bits/stdc++.h>

const int N = 1e5 + 5;
std::map<int, int> cnt[N];

int main() {
  std::ios::sync_with_stdio(0);
  int n, m;
  std::cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    int x;
    std::cin >> x;
    cnt[x % m][x]++;
  }
  int ans = 0;
  for (int i = 1, j = m - 1; i < j; i++, j--) {
    int a = 0, b = 0, c = 0, d = 0;
    for (auto &p: cnt[i]) {
      a += p.second - (p.second & 1);
      b += p.second & 1;
    }
    for (auto &p: cnt[j]) {
      c += p.second - (p.second & 1);
      d += p.second & 1;
    }
    if (b < d) {
      std::swap(b, d);
      std::swap(a, c);
    }
    ans += d;
    b -= d;
    ans += a / 2;
    if (b >= c) {
      ans += c;
    } else {
      ans += b;
      c -= b;
      ans += c / 2;
    }
  }
  int add = 0;
  for (auto &p: cnt[0]) {
    ans += p.second / 2;
    if (p.second & 1) add++;
  }
  ans += add / 2;
  if (!(m & 1)) {
    int add = 0;
    for (auto &p: cnt[m / 2]) {
      ans += p.second / 2;
      if (p.second & 1) add++;
    }
    ans += add / 2;
  }
  std::cout << ans << std::endl;
  return 0;
}

### Prompt

In CPP, your task is to solve 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
/*************************************************************************
  >         File: D.cc
  >       Author: lyyllyyl
  >         Mail: riho.yoshioka@yandex.com
  > Created Time: Sun 27 Nov 2016 12:20:21 AM JST
*************************************************************************/
#include <bits/stdc++.h>

const int N = 1e5 + 5;
std::map<int, int> cnt[N];

int main() {
  std::ios::sync_with_stdio(0);
  int n, m;
  std::cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    int x;
    std::cin >> x;
    cnt[x % m][x]++;
  }
  int ans = 0;
  for (int i = 1, j = m - 1; i < j; i++, j--) {
    int a = 0, b = 0, c = 0, d = 0;
    for (auto &p: cnt[i]) {
      a += p.second - (p.second & 1);
      b += p.second & 1;
    }
    for (auto &p: cnt[j]) {
      c += p.second - (p.second & 1);
      d += p.second & 1;
    }
    if (b < d) {
      std::swap(b, d);
      std::swap(a, c);
    }
    ans += d;
    b -= d;
    ans += a / 2;
    if (b >= c) {
      ans += c;
    } else {
      ans += b;
      c -= b;
      ans += c / 2;
    }
  }
  int add = 0;
  for (auto &p: cnt[0]) {
    ans += p.second / 2;
    if (p.second & 1) add++;
  }
  ans += add / 2;
  if (!(m & 1)) {
    int add = 0;
    for (auto &p: cnt[m / 2]) {
      ans += p.second / 2;
      if (p.second & 1) add++;
    }
    ans += add / 2;
  }
  std::cout << ans << std::endl;
  return 0;
}

```