#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
#define vv(a,b,c,d) vector<vector<a> >(b,vector<a>(c,d))
#define vvv(a,b,c,d,e) vector<vector<vector<a> > >(b,vv(a,c,d,e))
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

int N, M, X[100005];
vi A[100005];
// same val
int B[100005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    cin >> N >> M;
    rep(i, N) {
        cin >> X[i];
        A[X[i] % M].push_back(X[i]);
    }
    rep(i, M) {
        sort(all(A[i]));
        int pre = 0, suc = 0;
        A[i].push_back(0);
        each(x, A[i]) {
            if (x != pre) {
                // 同じ値
                B[i] += suc / 2;
                suc = 1;
                pre = x;
            } else suc++;
        }
        A[i].pop_back();
    }

    int ans = 0;
    for (int i = 0; i <= M / 2; ++i) {
        int n = sz(A[i]);
        if (i * 2 % M == 0) {
            ans += n / 2;
            continue;
        }
        int j = M - i;
        int m = sz(A[j]);
        int ma = 0;
        // i同士でp個作る
        for (int p = 0; p <= B[i]; ++p) {
            // 残り
            int nn = n - p * 2;
            // mod M = 0
            int cnt = min(nn, m);
            int q = min((m - cnt) / 2, B[j]);
            smax(ma, cnt + p + q);
        }
        ans += ma;
    }
    cout << ans << endl;
}
### Prompt

Your task is to create a CPP solution 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
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
#define vv(a,b,c,d) vector<vector<a> >(b,vector<a>(c,d))
#define vvv(a,b,c,d,e) vector<vector<vector<a> > >(b,vv(a,c,d,e))
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

int N, M, X[100005];
vi A[100005];
// same val
int B[100005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    cin >> N >> M;
    rep(i, N) {
        cin >> X[i];
        A[X[i] % M].push_back(X[i]);
    }
    rep(i, M) {
        sort(all(A[i]));
        int pre = 0, suc = 0;
        A[i].push_back(0);
        each(x, A[i]) {
            if (x != pre) {
                // 同じ値
                B[i] += suc / 2;
                suc = 1;
                pre = x;
            } else suc++;
        }
        A[i].pop_back();
    }

    int ans = 0;
    for (int i = 0; i <= M / 2; ++i) {
        int n = sz(A[i]);
        if (i * 2 % M == 0) {
            ans += n / 2;
            continue;
        }
        int j = M - i;
        int m = sz(A[j]);
        int ma = 0;
        // i同士でp個作る
        for (int p = 0; p <= B[i]; ++p) {
            // 残り
            int nn = n - p * 2;
            // mod M = 0
            int cnt = min(nn, m);
            int q = min((m - cnt) / 2, B[j]);
            smax(ma, cnt + p + q);
        }
        ans += ma;
    }
    cout << ans << endl;
}
```