#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 

ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x[ohara],y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
map<ll,ll> mp;
map<ll,ll> cou;
map<ll,ll> herasu;
bool vi[ohara];
ll kosuu;
P p[ohara];
ll p_cou;
ll dat[ohara];

//-------------------------↓↓↓↓↓↓------------------------

int main(void){
       cin.tie(0);
    ios::sync_with_stdio(false);

    //[{%m,m}]=個数
    cin>>n>>m;
    rep(i,n)cin>>x[i];
    rep(i,n){
        cou[x[i]]++;
        mp[x[i]%m]++;
    }
    rep(i,n){
        if((x[i]%m)!=m-(x[i]%m)&&x[i]%m!=0){
            //cerr<<i<<" "<<mp[i]<<" ";
            ans+=min(mp[x[i]%m],mp[m-(x[i]%m)]);
            herasu[x[i]%m]+=min(mp[x[i]%m],mp[m-(x[i]%m)]);
            herasu[m-(x[i]%m)]+=min(mp[x[i]%m],mp[m-(x[i]%m)]);
            pos=mp[x[i]%m];
            mp[x[i]%m]-=min(mp[x[i]%m],mp[m-(x[i]%m)]);
            mp[m-(x[i]%m)]-=min(pos,mp[m-(x[i]%m)]);
        }
        else{
            ans+=mp[x[i]%m]/2;
            herasu[x[i]%m]+=(mp[x[i]%m]/2)*2;
            mp[x[i]%m]%=2;
        }
    }
    rep(i,n){
        if(vi[x[i]])continue;
        vi[x[i]]=true;
        p[p_cou++]=m_p(cou[x[i]],x[i]%m);
    }
    sort(p,p+p_cou);
    reverse(p,p+p_cou);
    rep(i,p_cou){
        if(p[i].fi%2==1){
            dat[p[i].se]++;
            p[i].fi--;
        }
        //p[i].fi/=2;
    }
    rep(i,m){
        herasu[i]-=dat[i];
        if(herasu[i]<0)herasu[i]=0;
    }
    rep(i,p_cou){
        if(p[i].fi>=herasu[p[i].se]){
        p[i].fi-=herasu[p[i].se];
        herasu[p[i].se]=0;
        }
        else{
            herasu[p[i].se]-=p[i].fi;
            p[i].fi=0;
        }
    }
    rep(i,p_cou){
        cnt+=p[i].fi/2;
        //cout<<p[i].fi<<"\n";
    }
    //Cerr(cnt);
    //rep(i,m)cnt-=herasu[i],cerr<<herasu[i]<<"\n";
    //rep(i,m)cnt-=herasu[i],cout<<i<<" "<<herasu[i]<<"\n";
    Cout(ans+cnt);
    return 0;
}

### 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
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 

ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x[ohara],y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
map<ll,ll> mp;
map<ll,ll> cou;
map<ll,ll> herasu;
bool vi[ohara];
ll kosuu;
P p[ohara];
ll p_cou;
ll dat[ohara];

//-------------------------↓↓↓↓↓↓------------------------

int main(void){
       cin.tie(0);
    ios::sync_with_stdio(false);

    //[{%m,m}]=個数
    cin>>n>>m;
    rep(i,n)cin>>x[i];
    rep(i,n){
        cou[x[i]]++;
        mp[x[i]%m]++;
    }
    rep(i,n){
        if((x[i]%m)!=m-(x[i]%m)&&x[i]%m!=0){
            //cerr<<i<<" "<<mp[i]<<" ";
            ans+=min(mp[x[i]%m],mp[m-(x[i]%m)]);
            herasu[x[i]%m]+=min(mp[x[i]%m],mp[m-(x[i]%m)]);
            herasu[m-(x[i]%m)]+=min(mp[x[i]%m],mp[m-(x[i]%m)]);
            pos=mp[x[i]%m];
            mp[x[i]%m]-=min(mp[x[i]%m],mp[m-(x[i]%m)]);
            mp[m-(x[i]%m)]-=min(pos,mp[m-(x[i]%m)]);
        }
        else{
            ans+=mp[x[i]%m]/2;
            herasu[x[i]%m]+=(mp[x[i]%m]/2)*2;
            mp[x[i]%m]%=2;
        }
    }
    rep(i,n){
        if(vi[x[i]])continue;
        vi[x[i]]=true;
        p[p_cou++]=m_p(cou[x[i]],x[i]%m);
    }
    sort(p,p+p_cou);
    reverse(p,p+p_cou);
    rep(i,p_cou){
        if(p[i].fi%2==1){
            dat[p[i].se]++;
            p[i].fi--;
        }
        //p[i].fi/=2;
    }
    rep(i,m){
        herasu[i]-=dat[i];
        if(herasu[i]<0)herasu[i]=0;
    }
    rep(i,p_cou){
        if(p[i].fi>=herasu[p[i].se]){
        p[i].fi-=herasu[p[i].se];
        herasu[p[i].se]=0;
        }
        else{
            herasu[p[i].se]-=p[i].fi;
            p[i].fi=0;
        }
    }
    rep(i,p_cou){
        cnt+=p[i].fi/2;
        //cout<<p[i].fi<<"\n";
    }
    //Cerr(cnt);
    //rep(i,m)cnt-=herasu[i],cerr<<herasu[i]<<"\n";
    //rep(i,m)cnt-=herasu[i],cout<<i<<" "<<herasu[i]<<"\n";
    Cout(ans+cnt);
    return 0;
}

```