Совсем скоро наступит Международный женский день! Поликарп готовится к празднику.
В магазине продается \(n\) коробок с конфетами, в \(i\)-й коробке \(d_i\) конфет.
Поликарп хочет подготовить максимальное количество подарков для \(k\) подруг. Каждый подарок будет состоять из ровно двух коробок конфет. Чтобы \(k\) девушек могли поделить подарок поровну, сумма количеств конфет в подарке (в паре коробок) должна делится на \(k\). Иными словами, две коробки \(i\) и \(j\) (\(i \ne j\)) можно объединить в подарок, если \(d_i + d_j\) делится на \(k\).
Сколько максимум коробок сможет подарить Поликарп? Конечно, каждая коробка может быть в составе не более одного подарка. Поликарп не может использовать коробки «частично» или перераспределять конфеты между ними.
Выходные данные
Выведите одно целое число — максимальное количество коробок конфет, сколько сможет подарить Поликарп.
Примечание
В первом тестовом примере Поликарп сможет подарить следующие пары коробок (пары представлены номерами соответствующих коробок):
- \((2, 3)\);
- \((5, 6)\);
- \((1, 4)\).
Таким образом, ответ равен \(6\).
Во втором тестовом примере Поликарп сможет подарить следующие пары коробок (пары представлены номерами соответствующих коробок):
- \((6, 8)\);
- \((2, 3)\);
- \((1, 4)\);
- \((5, 7)\).
Таким образом, ответ равен \(8\).
В третьем тестовом примере Поликарп сможет подарить следующие пары коробок (пары представлены номерами соответствующих коробок):
Таким образом, ответ равен \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 2
1 2 2 3 2 4 10
|
6
|
|
2
|
8 2
1 2 2 3 2 4 6 10
|
8
|
|
3
|
7 3
1 2 2 3 2 4 5
|
4
|