#include <bits/stdc++.h>

using namespace std;

#define forn(i,n) for (int i = 0; i < int(n); i++)
#define ford(i,n) for (int i = int(n) - 1; i >= 0; i--)
#define fore(i,l,r) for (int i = int(l); i < int(r); i++)
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define mp make_pair
#define pb push_back
#define x first
#define y second

template<typename X> inline X abs(const X& a) { return a < 0 ? -a : a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
const ld PI = acosl(ld(-1));

mt19937 mt(time(NULL));

const int N = 100 * 1000 + 13;
int n, m;
int a[N];

inline bool read()
{
	if (scanf ("%d%d", &n, &m) != 2)
		return false;
		
	forn (i, n)
		assert(scanf ("%d", &a[i]) == 1);

	return true;
}

vector<pt> q[N];
int sum[N];
int cnt[N];

inline void solve()
{
	forn (i, n)
		cnt[ a[i] ]++;
		
	forn (i, N)
	{
		q[i % m].pb(mp(cnt[i], i));
		sum[i % m] += cnt[i];
	}
	
	int ans = 0;
	forn (i, m)
	{
		int ri = m - i;
		if (ri == m)
			ri = 0;
			
		if (i > ri)
			break;
		
		if (i == ri)
		{
			int cnt = 0;
			forn (j, sz(q[i]))
			{
				if (q[i][j].x & 1)
				{
					q[i][j].x--;
					cnt++;
				}
				
				ans += q[i][j].x / 2;
			}
			
			ans += cnt / 2;
			
			continue;
		}

		int cnt1 = 0, cnt2 = 0;
		forn (j, sz(q[i]))
			if (q[i][j].x & 1)
			{
				q[i][j].x--;
				cnt1++;
			}
		forn (j, sz(q[ri]))
			if (q[ri][j].x & 1)
			{
				q[ri][j].x--;
				cnt2++;
			}
			
		int need = max(cnt1, cnt2);
		need = min(need, min(sum[i], sum[ri]));
 
		forn (it, need)
		{
			if (cnt1)
				cnt1--;
			else
			{
				while (!q[i].empty() && q[i].back().x == 0)
					q[i].pop_back();
				assert(!q[i].empty());
				q[i].back().x--;
				if (q[i].back().x == 0)
					q[i].pop_back();
			}
			
			if (cnt2)
				cnt2--;
			else
			{
				while (!q[ri].empty() && q[ri].back().x == 0)
					q[ri].pop_back();			
				assert(!q[ri].empty());
				q[ri].back().x--;
				if (q[ri].back().x == 0)
					q[ri].pop_back();
			}
 
			ans++;	
		}
		
		for (auto it: q[i])
			ans += it.x / 2;
		for (auto it: q[ri])
			ans += it.x / 2;
	}
	
	cout << ans << endl;
}

int main()
{
#ifdef SU2_PROJ
	assert(freopen("input.txt", "r", stdin));
	assert(freopen("output.txt", "w", stdout));
#endif

	cout << setprecision(25) << fixed;
	cerr << setprecision(10) << fixed;

	assert(read());
	solve();

#ifdef SU2_PROJ
	cerr << "TIME: " << clock() << endl;
#endif

	return 0;
}

### Prompt

Develop a solution in cpp 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 forn(i,n) for (int i = 0; i < int(n); i++)
#define ford(i,n) for (int i = int(n) - 1; i >= 0; i--)
#define fore(i,l,r) for (int i = int(l); i < int(r); i++)
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define mp make_pair
#define pb push_back
#define x first
#define y second

template<typename X> inline X abs(const X& a) { return a < 0 ? -a : a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
const ld PI = acosl(ld(-1));

mt19937 mt(time(NULL));

const int N = 100 * 1000 + 13;
int n, m;
int a[N];

inline bool read()
{
	if (scanf ("%d%d", &n, &m) != 2)
		return false;
		
	forn (i, n)
		assert(scanf ("%d", &a[i]) == 1);

	return true;
}

vector<pt> q[N];
int sum[N];
int cnt[N];

inline void solve()
{
	forn (i, n)
		cnt[ a[i] ]++;
		
	forn (i, N)
	{
		q[i % m].pb(mp(cnt[i], i));
		sum[i % m] += cnt[i];
	}
	
	int ans = 0;
	forn (i, m)
	{
		int ri = m - i;
		if (ri == m)
			ri = 0;
			
		if (i > ri)
			break;
		
		if (i == ri)
		{
			int cnt = 0;
			forn (j, sz(q[i]))
			{
				if (q[i][j].x & 1)
				{
					q[i][j].x--;
					cnt++;
				}
				
				ans += q[i][j].x / 2;
			}
			
			ans += cnt / 2;
			
			continue;
		}

		int cnt1 = 0, cnt2 = 0;
		forn (j, sz(q[i]))
			if (q[i][j].x & 1)
			{
				q[i][j].x--;
				cnt1++;
			}
		forn (j, sz(q[ri]))
			if (q[ri][j].x & 1)
			{
				q[ri][j].x--;
				cnt2++;
			}
			
		int need = max(cnt1, cnt2);
		need = min(need, min(sum[i], sum[ri]));
 
		forn (it, need)
		{
			if (cnt1)
				cnt1--;
			else
			{
				while (!q[i].empty() && q[i].back().x == 0)
					q[i].pop_back();
				assert(!q[i].empty());
				q[i].back().x--;
				if (q[i].back().x == 0)
					q[i].pop_back();
			}
			
			if (cnt2)
				cnt2--;
			else
			{
				while (!q[ri].empty() && q[ri].back().x == 0)
					q[ri].pop_back();			
				assert(!q[ri].empty());
				q[ri].back().x--;
				if (q[ri].back().x == 0)
					q[ri].pop_back();
			}
 
			ans++;	
		}
		
		for (auto it: q[i])
			ans += it.x / 2;
		for (auto it: q[ri])
			ans += it.x / 2;
	}
	
	cout << ans << endl;
}

int main()
{
#ifdef SU2_PROJ
	assert(freopen("input.txt", "r", stdin));
	assert(freopen("output.txt", "w", stdout));
#endif

	cout << setprecision(25) << fixed;
	cerr << setprecision(10) << fixed;

	assert(read());
	solve();

#ifdef SU2_PROJ
	cerr << "TIME: " << clock() << endl;
#endif

	return 0;
}

```