题目描述

有 $n$ 个出题组参与出题，第 $i$ 个出题组有 $a_{i}$ 个人。他们想要出的题尽量少（这样题目质量会更高)，每个题的出题人最多有 $r$ 个，但是为了让每个出题人尽快投入到工作中，对于任意一个题目的一个出题人，这个题目的出题人中存在另外一个出题人与他来自于同一个出题组。

请问他们最少出多少道题？

输入格式

第一行两个正整数 $n$, $r$。

第二行 $n$ 个正整数表示第 $i$ 个出题组的人数。

输出格式

仅一行一个整数，表示最少出多少道题。

样例

3 4
5 6 7

5

4 4
3 3 3 3

4

子任务

对于所有的数据, $n \leq 2 * 10^{6}, a_{i}, r \leq 10^{9}, 2 \leq a_{i}, 3 \leq r$。

subtask $1(10 \mathrm{pts}): n \leq 2, a_{i} \leq 10^{6}$ 。

subtask $2(20 \mathrm{pts}): n, a_{i}, r \leq 200$ 。

subtask $3(30 \mathrm{pts}): n, a_{i}, r \leq 2000$。

subtask $4(40 \mathrm{pts})$ : 无特殊限制。