题目描述

一次程序设计比赛结束后，$n$ 组朋友来到咖啡馆休息。第 $i$ 组有 $a_i$ 个人。咖啡馆里的每张桌子都完全相同，每张桌子有 $r$ 个座位。

大家希望安排座位，使得任何人都不会在某张桌子上独自代表自己的小组。也就是说，对于每一个人，在他所在的桌子上至少还有另一个与他属于同一组的人。

除此之外没有其他限制：

• 不同小组的人可以坐在同一张桌子；
• 同一个小组可以被分到多张桌子；
• 桌子上可以留空位。

请计算让所有人都坐下所需的最少桌子数量。

输入格式

第一行两个整数 $n,r$，满足 $1\le n\le2000$，$3\le r\le2000$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，满足 $2\le a_i\le2000$。

输出格式

输出一个整数，表示最少需要的桌子数量。

样例 1

样例输入

3 4
5 6 7

样例输出

5

样例 2

样例输入

4 4
3 3 3 3

样例输出

4

样例说明

第一组样例的一种安排如下：第一桌坐第 1 组的 3 人；第二桌坐第 1 组 2 人和第 2 组 2 人；第三桌坐第 2 组 4 人；第四桌坐第 3 组 4 人；第五桌坐第 3 组 3 人。空余座位可以不坐人。