← 返回题目列表

Codeforces · 472/B

B. 设计教程:从生活中学习

中文机器翻译题面 查看原题

创建任务的一种方法是从生活中学习。你可以选择一些现实生活中的经验,将其形式化,然后你就会得到一个新的任务。

我们想一下现实生活中的一个场景:有很多人在电梯前等待,每个人都想去某个楼层。我们可以通过以下方式将其形式化。我们有 n 个人站在一楼,第 i 个人想去五楼。不幸的是,只有一部电梯,其容量等于k(即最多k人可以同时使用它)。最初电梯位于一楼。电梯需要 |a - b|从a层移动到b层的秒数(我们不计算人们上下电梯所需的时间)。

将所有人员运送到相应楼层,然后电梯返回一楼,最少需要多少秒?

输入

第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 2000) — 人数和电梯的最大容量。

下一行包含 n 个整数:f1, f2, ..., fn (2 ≤ fi ≤ 2000),其中 fi 表示第 i 个人的目标楼层。

输出

输出一个整数——实现目标所需的最短时间。

示例

输入 #1

3 2
2 3 4

输出 #1

8

输入 #2

4 2
50 100 50 100

输出 #2

296

输入 #3

10 3
2 2 2 2 2 2 2 2 2 2

输出 #3

8

注意

在第一个示例中,最佳解决方案是:

1. 电梯搭载#1 人和#2 人。
2. 前往二楼。
3. 两人走出电梯。
4. 电梯返回一楼。
5. 然后电梯搭载#3 人。
6. 然后它去二楼。
7. 它接载#2 人。
8. 然后去三楼。
9.#2 出去。
10. 然后到 4 楼,#3 出去。
11. 电梯返回一楼。