#include<map>
#include<set>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<chrono>
#include<stack>
#include<fstream>
#include<list>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll> 
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) 
#define UNIQUE_ARRAY(a,x) unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;


struct querys
{
	long long type; long long ord; long long from; long long to; long long name;
	bool operator<(const querys& rhs) const {
		if (ord != rhs.ord) {
			return ord < rhs.ord;
		}
		else {
			return type < rhs.type;
		}
	}
};
ll const MAX = 1e5 + 5;
ll a[MAX];
ll b[MAX] = {};
ll c[MAX] = {};
int main() {
	ll n, m;
	cin >> n >> m;
	REP(i, 1, n) {
		cin >> a[i];
	}
	SORT(a, n);
	a[n+1] = 1e9;
	ll cur = 0;
	REP(i, 1, n) {
		ll x = a[i] % m;
		b[x]++;
		cur++;
		if (a[i] != a[i + 1]) {
			c[x] += cur / 2;
			cur = 0;
		}
	}
	ll ans = 0;
	ans += b[0] / 2;
	if (m % 2 == 0) {
		ans += b[m / 2] / 2;
	}
	for (ll i = 1; i < m - i; i++) {
		ll j = m - i;
		if (b[i] > b[j]) {
			swap(b[i], b[j]);
			swap(c[i], c[j]);
		}
		ans += b[i];
		b[j] -= b[i];
		ans += min(b[j] / 2, c[j]);
	}
	cout << ans << endl;

}
### Prompt

Your challenge is to write 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<map>
#include<set>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<chrono>
#include<stack>
#include<fstream>
#include<list>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll> 
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) 
#define UNIQUE_ARRAY(a,x) unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;


struct querys
{
	long long type; long long ord; long long from; long long to; long long name;
	bool operator<(const querys& rhs) const {
		if (ord != rhs.ord) {
			return ord < rhs.ord;
		}
		else {
			return type < rhs.type;
		}
	}
};
ll const MAX = 1e5 + 5;
ll a[MAX];
ll b[MAX] = {};
ll c[MAX] = {};
int main() {
	ll n, m;
	cin >> n >> m;
	REP(i, 1, n) {
		cin >> a[i];
	}
	SORT(a, n);
	a[n+1] = 1e9;
	ll cur = 0;
	REP(i, 1, n) {
		ll x = a[i] % m;
		b[x]++;
		cur++;
		if (a[i] != a[i + 1]) {
			c[x] += cur / 2;
			cur = 0;
		}
	}
	ll ans = 0;
	ans += b[0] / 2;
	if (m % 2 == 0) {
		ans += b[m / 2] / 2;
	}
	for (ll i = 1; i < m - i; i++) {
		ll j = m - i;
		if (b[i] > b[j]) {
			swap(b[i], b[j]);
			swap(c[i], c[j]);
		}
		ans += b[i];
		b[j] -= b[i];
		ans += min(b[j] / 2, c[j]);
	}
	cout << ans << endl;

}
```