题目描述

桃子在开车，她喜欢停靠休息站，具体来说，不能有连续 $m$ 分钟都处于开车状态。汽车每分钟都可以使得速度值增加 1，减少 1，或保持不变，汽车的速度上限为 $k$。现在已知旅程共有 $n$ 分钟，以及第几分钟时会出现休息站，如果想要在休息站停靠，那么此时车速必须降为 0，你可以忽略在休息站休息的时间。现在请你求每分钟车速之和的最大值。

输入格式

输入第一行包含四个正整数 $n,m,k,q$，其中 $q$ 表示休息站的数量。

接下来一行包含 $q$ 个正整数，分别表示休息站出现的时间 $a_i(1 \leq a_i \leq n)$，保证给出的 $q$ 个正整数递增，且保证汽车一定可以到达目的地。

输出格式

输出一行一个整数表示答案。

5 3 3 3
1 3 5

5

8 9 3 2
3 7

21

样例解释 1

不能有连续 3 分钟处于开车状态，所以选择在第 3 分钟时进入休息站（此时速度必须为 0），所以这五分钟的速度分别为 [1,1,0,1,2]，速度之和为 5。注意，若在第 2 分钟加速到速度 2，则无法在第 3 分钟时速度变为 0 进入休息站，所以在第 2 分钟速度保持不变是最合理的选择。

样例解释 2

不能有连续 9 分钟处于开车状态，但是整个旅程只有 8 分钟，所以可以不停靠休息站。这种情况下车的速度只受上限值 $k=3$ 的影响，所以每分钟的车速为 [1,2,3,3,3,3,3,3]，车速之和为 21。

数据规模与约定

对于 10% 的数据，有 $q \leq 3, 1 \leq n,m,k \leq 10$

对于 30% 的数据，有 $q \leq 1000, 1 \leq n,m,k \leq 4000$

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