#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

const int N = 100005;

int n, m;
int cnt[N];

int main() {
    scanf("%d%d", &n, &m);
    memset(cnt, 0, sizeof cnt);
    forn(i, n) {
        int x;
        scanf("%d", &x);
        ++cnt[x];
    }
    int ans = 0;
    for (int i = 0; 2 * i <= m; ++i) {
        int j = 0;
        if (i > 0) {
            j = m - i;
        }
        if (i == j) {
            int c = 0;
            for (int x = i; x < N; x += m) {
                c += cnt[x];
            }
            ans += c / 2;
        } else {
            int le = 0, ri = 0, lpairs = 0, rpairs = 0;
            for (int x = i; x < N; x += m) {
                lpairs += cnt[x] / 2;
                le += cnt[x] % 2;
            }
            for (int x = j; x < N; x += m) {
                rpairs += cnt[x] / 2;
                ri += cnt[x] % 2;
            }
            //cerr << le << ' ' << ri << ' ' << lpairs << ' ' << rpairs << endl;
            ans += lpairs + rpairs;
            int mn = min(le, ri);
            le -= mn;
            ri -= mn;
            ans += mn;
            ans += min(le / 2, rpairs);
            ans += min(ri / 2, lpairs);
        }
    }
    printf("%d\n", ans);
    return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

const int N = 100005;

int n, m;
int cnt[N];

int main() {
    scanf("%d%d", &n, &m);
    memset(cnt, 0, sizeof cnt);
    forn(i, n) {
        int x;
        scanf("%d", &x);
        ++cnt[x];
    }
    int ans = 0;
    for (int i = 0; 2 * i <= m; ++i) {
        int j = 0;
        if (i > 0) {
            j = m - i;
        }
        if (i == j) {
            int c = 0;
            for (int x = i; x < N; x += m) {
                c += cnt[x];
            }
            ans += c / 2;
        } else {
            int le = 0, ri = 0, lpairs = 0, rpairs = 0;
            for (int x = i; x < N; x += m) {
                lpairs += cnt[x] / 2;
                le += cnt[x] % 2;
            }
            for (int x = j; x < N; x += m) {
                rpairs += cnt[x] / 2;
                ri += cnt[x] % 2;
            }
            //cerr << le << ' ' << ri << ' ' << lpairs << ' ' << rpairs << endl;
            ans += lpairs + rpairs;
            int mn = min(le, ri);
            le -= mn;
            ri -= mn;
            ans += mn;
            ans += min(le / 2, rpairs);
            ans += min(ri / 2, lpairs);
        }
    }
    printf("%d\n", ans);
    return 0;
}

```