空白之恐怖演算能力

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

3785-2

 

空白的世界没有败北。

 

3785-1

 

白具有超强的记忆力和数学推演能力,在与世上最强国际象棋程序交换先后手的较量中,获得了 20 连胜的成绩。其原因其实是她超强的大脑心算能力,并且是并行的。也就是说她可以一次处理多个事件。现在给你 n 个事件和她最多能一次处理的事件数 m。然后每个事件都会有 num 个步数,每处理一个步数就需要花费 1 分钟(1 分钟只能处理 1 个事件的 1 个步骤,但可以同时处理 m 个不同的事件)。现在你来计算一下她最少需要多少分钟处理完这 n 个事件。

Input

输入数据有多组(数据组数不超过 20),到 EOF 结束。

对于每组数据:

  • 第一行包含两个以空格分隔开的正整数 n, m (1 <= n, m <= 40000)。
  • 第二行包含 n 个数,表示每个事件需要处理的步数。每个数介于 1~40000 之间。

Output

对于每组数据,输出一个整数,表示她完成这 n 个事件需要的最少分钟数。

Sample Input

3 2
2 2 2
10 6
1 2 3 4 5 6 7 8 9 10

Sample Output

3
10

Hint

对于第 1 组数据,可以按照如下方式得到答案(方法不唯一):

初始:2 2 2
第 1 分钟:1 1 2
第 2 分钟:0 1 1
第 3 分钟:0 0 0

Source

【SDUT Round #2 - 2017 新春大作战】UMR