← 返回题目列表

Codeforces · 54/A

A. 礼物

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

刺猬喜欢送礼物给他的朋友,但他也喜欢收到礼物。

今天又收到一份礼物,刺猬突然明白自己没地方放了,因为柜子里的特制架子已经没有地方了。他将不得不选择另一个架子,但他应该选择哪一个,它应该有多大?

为了了解这一点,刺猬要求你为他编写一个程序,计算他在接下来的 N 天内将收到的礼物的估计数量。此外,他遵循以下原则:

- 在每个假期,刺猬一定会收到一份礼物,
- 他至少每 K 天收到礼物(即,如果他在第 i 天收到礼物,他将不迟于第 i + K 天收到下一份礼物)。

对于给定的 N 和 K,以及接下来 N 天的假期列表,计算可以送给刺猬的最小礼物数量。今天的天数为零,您应该将今天的礼物视为已经给出(即,您不应该将其计入答案中)。

输入

第一行包含整数 N 和 K (1 ≤ N ≤ 365, 1 ≤ K ≤ N)。

第二行包含数字 C,表示假期数 (0 ≤ C ≤ N)。然后在同一行中跟随从 1 到 N 的 C 数字,它们是假期的天数。数字按递增顺序给出,其中没有重复的数字。

输出

打印一个数字——刺猬在接下来的 N 天内收到的礼物的最少数量。

示例

输入 #1

5 2
1 3

输出 #1

3

输入 #2

10 1
3 6 7 8

输出 #2

10