#P9587. 还没出好

    ID: 6202 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-二分答案奇偶性分析固定一个变量消去另一维

还没出好

题目描述

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

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

输入格式

第一行两个正整数 nn, rr。

第二行 nn 个正整数表示第 ii 个出题组的人数。

输出格式

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

样例

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(10pts):n≤2,ai≤1061(10 \mathrm{pts}): n \leq 2, a_{i} \leq 10^{6} 。

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

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

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