题目描述

一辆测试车要在一条路上行驶 $n$ 分钟。第 $0$ 分钟车速为 $0$；之后每分钟车速可以比上一分钟增加 $1$、减少 $1$ 或保持不变，并且始终不超过 $k$，也不小于 $0$。

路上有 $q$ 个服务点，第 $i$ 个服务点在第 $a_i$ 分钟出现。测试车经过服务点时可以停车：停车的那一刻车速必须为 $0$，并且连续行驶的时间从 $0$ 重新开始计算。也可以不停车直接通过。只有在服务点停车才能清零连续行驶时间，在其他分钟即使车速为 $0$ 也仍然计入连续行驶时间。

规定连续行驶的时间不能达到 $m$ 分钟。行驶结束时，车速不需要降回 $0$。请安排每分钟的车速，使这 $n$ 分钟的车速之和最大。

输入格式

第一行四个整数 $n,m,k,q$，含义如上所述。

第二行 $q$ 个整数 $a_1,a_2,\dots,a_q$，表示服务点出现的时间，保证严格递增。

数据保证测试车一定可以到达终点。

输出格式

输出一个整数，表示每分钟车速之和的最大值。

样例

6 3 2 3
2 4 6

5

9 12 3 2
4 7

24

7 4 5 2
2 5

6

样例解释

样例 1 中，连续行驶不能达到 $3$ 分钟，选择在第 $2,4$ 分钟停车，之后不用再停，速度可以是 $1,0,1,0,1,2$，和为 $5$。

样例 2 中，整个行程只有 $9$ 分钟、小于 $m=12$，可以不停车，速度受上限 $k=3$ 限制，为 $1,2,3,3,3,3,3,3,3$，和为 $24$。

样例 3 中，在第 $2,5$ 分钟各停车一次，之后加速到 $2$，速度可以是 $1,0,1,1,0,1,2$，和为 $6$。

数据范围与约定

对于 $100\%$ 的数据，$1\le q\le 1000$，$1\le n,m,k\le 10^9$，$1\le a_i\le n$。