题目描述

小Z和朋友们去了回转寿司店大快朵颐！店里专门有一个餐盘回收处，这里会根据回收的餐盘数量进行奖品的分发。

小Z和朋友们吃剩的餐盘数量为 $a_i$，他们会依次将自己的餐盘放到回收处。

假设回收处的餐盘数量当前为 $cur(0\le cur<k)$，如果投入了一定数量的餐盘 $a_i$，使得 $cur+a_i\geq k$，那么就会获得一个奖品。然后回收处的餐盘数量就会变成除以 $k$ 的余数：$cur\leftarrow (cur+a_i)\mod k$。注意，即使 $cur+a_i$ 可能跨越多个 $k$，也只会获得一份奖品。

为了最大化所有人获得奖品的数量，小Z决定等到回收处的初始餐盘数量为 $p$ 时，再带领大家去排队。求问他们总共能获得的最多奖品数量是多少。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示所有同学的人数和餐盘回收处的 $k$。

第二行包含 $n$ 个整数 ，其中 $a_i$ 表示第 $i$ 名同学准备回收的餐盘数量。

输出格式

他们在最优的 $p$ 开始排队后，获得的奖品最多的数量。

输入输出样例

5 10
4 17 3 6 2

4

样例 $\tt \#1$说明

当他们在回收处初始有 $p=8$ 个盘子开始排队：

1. 第 $1$ 个人投入 $4$ 个盘子，总数变为 $8+4=12\ge10$，获得 $1$ 个奖品，然后数量变为 $12\mod 10=2$
2. 第 $2$ 个人投入 $17$ 个盘子，总数变为 $2+17=19\ge10$，获得 $1$ 个奖品，然后数量变为 $19\mod 10=9$
3. 第 $3$ 个人投入 $3$ 个盘子，总数变为 $9+3=12\ge10$，获得 $1$ 个奖品，然后数量变为 $12\mod 10=2$
4. 第 $4$ 个人投入 $6$ 个盘子，总数变为 $2+6=8<10$，没有奖品
5. 第 $5$ 个人投入 $2$ 个盘子，总数变为 $8+2=10\ge10$，获得 $1$ 个奖品，然后数量变为 $10\mod 10=0$

此时获得奖品的总数量最多为 $4$

数据范围

$40\%:1\le n,k\le 2000$

另外 $10\%:a_i< k$

$100\%:1\le n,k\le 2\times10^5,1\le a_i\le 10^9$