#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define ld  double
#define ll long long
#define int long long


using namespace std;

const int MAXN = 301 * 1001  , MOD = 1e9 + 7 , sq = 333  ;

int a[MAXN] , b[MAXN] ;

int aa[MAXN] ;

int solve(int t1 , int p1 , int t2 , int p2 )
{
    int ans = 0 ;
    for(int i = 0 ; i <= p1 ; i ++ )
    {
        int T = t1 - 2 * i ;
        int k = i + min(T,t2-2*p2) ;
        if(T<=t2-2*p2)
        {
            ans = max(ans,k+p2) ;
            continue ;
        }
        ans = max(ans,k+p2);
        T -= t2-2*p2 ;
        if(T>=2*p2)
        {
            ans = max(ans,k+2*p2) ;
            continue ;
        }
        ans = max(ans,k+T/2+p2) ;
    }
   // cout<<ans<<'\n';
    return ans ;
}

int32_t main()
{
   ios::sync_with_stdio(0);cin.tie(0);

   int n , m ;
   cin >> n >> m ;
   for(int i = 0 ; i < n ; i ++ )
    cin >> aa[i] , a[aa[i]%m]++;
   sort(aa,aa+n);
   for(int i = 0 ; i < n ; i ++ )
   {
       if(i&&aa[i]==aa[i-1])
       {
           b[aa[i]%m]++;
           aa[i] = -1 ;
       }
   }

   int ans = a[0] / 2  ;
   for(int i = 1 ; i < (m+1) / 2 ; i ++ )
   {
      // cout<<a[i]<<' '<<b[i]<<' '<<a[m-i]<<' '<<b[m-i]<<'\n';
        ans += solve(a[i],b[i],a[m-i],b[m-i]);
   }
   if(m%2==0)
    ans += a[m/2] / 2  ;
   cout<<ans;



}

### Prompt

Create a solution in Cpp for 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>

#define F first
#define S second
#define pb push_back
#define ld  double
#define ll long long
#define int long long


using namespace std;

const int MAXN = 301 * 1001  , MOD = 1e9 + 7 , sq = 333  ;

int a[MAXN] , b[MAXN] ;

int aa[MAXN] ;

int solve(int t1 , int p1 , int t2 , int p2 )
{
    int ans = 0 ;
    for(int i = 0 ; i <= p1 ; i ++ )
    {
        int T = t1 - 2 * i ;
        int k = i + min(T,t2-2*p2) ;
        if(T<=t2-2*p2)
        {
            ans = max(ans,k+p2) ;
            continue ;
        }
        ans = max(ans,k+p2);
        T -= t2-2*p2 ;
        if(T>=2*p2)
        {
            ans = max(ans,k+2*p2) ;
            continue ;
        }
        ans = max(ans,k+T/2+p2) ;
    }
   // cout<<ans<<'\n';
    return ans ;
}

int32_t main()
{
   ios::sync_with_stdio(0);cin.tie(0);

   int n , m ;
   cin >> n >> m ;
   for(int i = 0 ; i < n ; i ++ )
    cin >> aa[i] , a[aa[i]%m]++;
   sort(aa,aa+n);
   for(int i = 0 ; i < n ; i ++ )
   {
       if(i&&aa[i]==aa[i-1])
       {
           b[aa[i]%m]++;
           aa[i] = -1 ;
       }
   }

   int ans = a[0] / 2  ;
   for(int i = 1 ; i < (m+1) / 2 ; i ++ )
   {
      // cout<<a[i]<<' '<<b[i]<<' '<<a[m-i]<<' '<<b[m-i]<<'\n';
        ans += solve(a[i],b[i],a[m-i],b[m-i]);
   }
   if(m%2==0)
    ans += a[m/2] / 2  ;
   cout<<ans;



}

```