该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定 $n$ 个数的数组 $a$，请你在 $n$ 个数中挑选 $3$ 个数 $a_i、a_j、a_k$，使这 $3$ 个数符合以下要求：

• $i \neq j \neq k$
• $a_i + a_j + a_k$ 是 $m$ 的倍数
• $a_i \% m \neq a_j \% m \neq a_k \% m$

请求出所有符合要求的 $a_i + a_j + a_k$ 的最大值。

格式要求

输入格式

第一行输入 $2$ 个正整数 $n, m(3 \leq n \leq 10^5, 1 \leq m \leq 10^3)$。

第二行输入 $n$ 个正整数 $a_i(1 \leq a_i \leq 10^9)$。

输出格式

输出一个整数，代表符合要求的总和的最大值。如果没有符合要求的总和则输出 0。

样例

4 3
1 2 3 4

9