大样例下载

题目描述

你正在玩跳格子游戏。

一排有无数个格子，自左向右依次编号为 $0, 1, 2,$ ……

初始时，你位于 $0$ 号格子中。你不断地向右跳跃，但你每次跳的格子数是有限制的。你每次跳的格子数不能小于 $a$，不能大于 $b$。假如你当前正在 $x$ 号格子，每次跳跃，你可以向右跳 $r$ 个格子，落在 $x+r$ 号格子中。其中 $a ≤ r ≤ b$。

有 $M$ 个格子是你不愿意落脚的，这些格子被称作 Bad 格子，它们的编号为 $c_1, c_2, ……, c_M$。

当你第一次跳到编号不小于 $N$ 号的格子时，游戏结束。

问：你至少可能跳到多少个 Bad 格子中？

输入格式

• 第 $1$ 行：包含一个整数 $N$
• 第 $2$ 行：包含三个整数 $a, b, M$
• 第 $3$ 行：包含 M 个整数 $c_1, c_2, ……, c_M$。数据保证这些整数两两不同，且均为小于 $N$ 的正整数。

输出格式

一个整数，表示答案

样例输入

10
2 3 5
3 2 5 7 6

样例输出

2

数据范围

• 30% 的数据：$1 ≤ N ≤ 10^4$；
• 100% 的数据：$1 ≤ N ≤ 10^9; 1 ≤ a ≤ b ≤ 10; 1 ≤ M ≤ 100; 0 < c_i < N$。