#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6 + 10;
int cnt[MAX], tot[MAX], a[MAX];
int main(){
	int n, m, x;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; ++i){
		scanf("%d", &x);
		a[i] = x;
		cnt[x%m]++;
		tot[x]++;
	}
	int ans = cnt[0]/2;
	cnt[0]-=ans*2;
	int lf = 1;
	int rg = m-1;	
	while(lf <= rg){
		int mi = min(cnt[lf], cnt[rg]);
		if(lf == rg)mi = cnt[lf]/2;
		cnt[lf]-=mi;
		cnt[rg]-=mi;
		++lf;
		--rg;
		ans+=mi;
	}
	for(int i = 0; i < n; ++i){
		int mi = min(tot[a[i]], cnt[a[i]%m]);
		ans+=mi/2;
			tot[a[i]]-=2*(mi/2);
			cnt[a[i]%m]-=2*(mi/2);	
	}
	printf("%d\n", ans);
}
### 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>
using namespace std;
const int MAX = 1e6 + 10;
int cnt[MAX], tot[MAX], a[MAX];
int main(){
	int n, m, x;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; ++i){
		scanf("%d", &x);
		a[i] = x;
		cnt[x%m]++;
		tot[x]++;
	}
	int ans = cnt[0]/2;
	cnt[0]-=ans*2;
	int lf = 1;
	int rg = m-1;	
	while(lf <= rg){
		int mi = min(cnt[lf], cnt[rg]);
		if(lf == rg)mi = cnt[lf]/2;
		cnt[lf]-=mi;
		cnt[rg]-=mi;
		++lf;
		--rg;
		ans+=mi;
	}
	for(int i = 0; i < n; ++i){
		int mi = min(tot[a[i]], cnt[a[i]%m]);
		ans+=mi/2;
			tot[a[i]]-=2*(mi/2);
			cnt[a[i]%m]-=2*(mi/2);	
	}
	printf("%d\n", ans);
}
```