eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Задача групування

Задача групування

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Множина складається з n цілих чисел. З довільних k різних елементів Ви можете скласти групу. Дві групи вважаються різними, якщо вони мають хоча б один не спільний елемент. Наприклад, якщо є 4 елементи a, b, c, d і Вам слід скласти групи з двох елементів, то можливими допустимими групами будуть ab, ad, bc, cd. Систему груп будемо називати повною для заданого k, якшо кількість груп в ній максимально можлива. Наприклад, для попереднього прикладу {ab, bc, cd, bd, ad, ac} буде повною системою груп.

Зручність повної системи груп будемо обчислювати наступним чином:

  1. Кожна група робить свій внесок у систему – добуток чисел у групі;

  2. Внески усіх груп додаються;

  3. Зручність системи еквівалентно загальному внеску mod m, де m - обмежуючий параметр

В нашому прикладі для k = 2 зручність дорівнює F[2] = (ab + bc + cd + bd + ad + ac) mod m. При k = 1 зручність дорівнює F[1] = (a + b + c + d) mod m.

Вам слід знайти повну систему груп з максимальною зручністю.

Вхідні дані

Кожен тест починається двома натуральними числами n (2n1000) та m (1m < 2^31). Наступний рядок містить n натуральних чисел, кожне з яких не більше за 1000. Останній тест містить n = m = 0 та не обробляється.

Вихідні дані

Для кожного тесту в окремому рядку вивести максимальне значення зручності серед усіх повних систем груп.

Приклад

Вхідні дані #1
4 10
1 2 3 4
4 100
1 2 3 4
4 6
1 2 3 4
0 0
Вихідні дані #1
5
50
5