Вам дано послідовність цілих невід’ємних чисел \(A=(a_1 ​ ,a_2 ​ ,…,a_N ​ )\).

Нехай \(S\) — набір цілих невід’ємних чисел, які можуть бути сумою \(K\) членів у \(A\) (з різними індексами).

Знайдіть найбільше кратне \(D\) у \(S\). Якщо \(D\) у \(S\) немає, виведіть -1.

Обмеження

• \(1≤K≤N≤100\)
• \( 1≤D≤100\)
• \(0≤a_i ​ ≤10^9\)
• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить цілі числа \(N,K,D\).

Наступний   рядок містить цілі числа \(a_i\).

Формат вихідних даних

У вихідний потік виведіть відповідь.

Приклад вхідних даних

4 2 2
1 2 3 4

Приклад вихідних даних

6

Ось усі способи вибрати два доданки в \(A\).

• Виберіть \(a_1\) ​ і \(a_2\) ​, сума яких дорівнює 1 + 2=3.
• Виберіть \(a_1\) і \(a_3\), сума яких дорівнює 1 + 3=4.
• Виберіть \(a_1\) ​ і \(a_4\) ​ , сума яких дорівнює 1 +4 = 5.
• Виберіть \(a_2\) і \(a_3\) , сума яких дорівнює 2 +3=5.
• Виберіть \(a_2\) і \(a_4\) , сума яких дорівнює 2 +4=6.
• Виберіть \(a_3\) ​ і \(a_4\) ​ , сума яких дорівнює 3 +4 = 7.

Таким чином, маємо \(S={3,4,5,6,7}\). Найбільше кратне 2 у \(S\) дорівнює 6, тому ви повинні вивести 6.

Приклад вхідних даних

3 1 2
1 3 5

Приклад вихідних даних

-1

У цьому прикладі ми маємо \(S={1,3,5}\). Ніщо в \(S\) не є кратним 2.