在《崩坏：星穹铁道》这款回合制游戏中，存在一种玩法叫做“模拟宇宙”，玩家需要选择去信仰一位星神。illume 最喜欢的星神是丰饶，因为她的祝福具有强大的回血能力，能够保证玩家几乎不会战死！ 为什么说《崩坏：星穹铁道》是一款好游戏？是因为玩家可以使用 AI 操作进行自动挂机。作为一名懒惰的微氪玩家，illume 在模拟宇宙中总是采用“AI 操作，自动挂机”的方式进行游戏。 在第 $10^{100000}$ 个模拟宇宙中，illume 遇到了一个棘手的 Boss，其血量为 $10^{100000}$，而 illume 每回合的攻击力仅为 $1$。但由于信仰了强大的丰饶星神，因此他认为自己在有生之年内一定能消灭这个 Boss。 丰饶的回血有两种方式：一种是“精确操作”，会在第 $x$ 个回合给 illume 回血；另一种是“周期操作”，会从第 $x$ 个回合开始，每隔 $y$ 个回合就给 illume 回一次血，换言之，“周期操作”在第 $x+k\cdot y$ $(k \ge 0,k\in \Z)$ 回合均会给 illume 回血。 illume 发现，尽管丰饶星神十分强大，但 AI 却特别的笨，因为它不会考虑“周期操作”，因而总是会浪费“精确操作”，导致出现连续回血多次的情况。我们把在同一回合进行“精确操作”和“周期操作”的情况定义为**浪费**。 已知在这局游戏中，回合数从 $1$ 开始计数，AI 总共将进行 $n$ 次“精确操作”，第 $i$ 次“精确操作”将在第 $A_i$ 个回合进行回血。而“周期操作”将从第 $x$ 个回合开始，每隔 $y$ 个回合回一次血。illume 总共有 $m$ 次将“精确操作”提前的机会，换句话说，他可以任选 $m$ 个 $i \in [1,n]$ 并让 $A_i$ 变为 $[1,A_i]$ 之内的任意一个整数。 请问，借助这 $m$ 次机会，AI 浪费的回血次数所能变成的最小值是多少？ 注：“精确操作”有冷却时间，因此“精确操作”只会出现在**不同的回合**内。 

第一行包含四个正整数 $n,x,y,m$. 第二行包含 $n$ 个正整数 $A_1,A_2,\cdots,A_n$. - $1 \le m \le n \le 10^5$ - $1 \le x,y \le 10^{15}$ - $1 \le A_i \le 10^{15}$ - $\forall_{i \ne j} \quad A_i \ne A_j$

一个整数，表示 AI 浪费的回血次数所能变成的最小值。


2023-05 多校联合训练 ZJNU站 正式赛