题目描述

你正在管理一台自动加工机。它需要按照固定顺序完成 $n$ 个订单，其中第 $i$ 个订单原本需要加工 $a_i$ 个单位时间。

如果你在时刻 $t$ 启动第 $i$ 个订单，那么机器会在时间区间 $(t,t+a_i)$ 内加工该订单，并在时刻 $t+a_i$ 完成它。一个订单完成之后，机器会停止等待，直到你启动下一个订单。所有订单都必须按照编号从小到大依次完成。第 $n$ 个订单完成后，你还需要亲自确认并提交最终报告。

机器可以一直工作，但你本人需要休息。你的作息以 $d=x+y$ 为周期。对于任意非负整数 $k$：

• 在时间区间 $[kd,kd+x]$ 内，你处于可操作状态；
• 在时间区间 $(kd+x,kd+x+y)$ 内，你处于休息状态。

你只有在可操作状态下，才能启动下一个订单或提交最终报告。

此外，你有 $m$ 张加速券。每使用一张加速券，可以选择一个当前加工时间非零的订单，将它的加工时间减少 $1$。加速券可以在一开始任意分配到各个订单上。

你在时刻 $0$ 获得这台机器。请问，在所有订单按顺序完成，并且你成功提交最终报告的前提下，最早可以在什么时刻完成提交？

输入格式

第一行包含两个整数 $o,t$，分别表示测试点编号和数据组数。

对于每组数据：

第一行包含四个非负整数 $n,x,y,m$。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示每个订单的初始加工时间。

输出格式

对于每组数据，输出一行一个非负整数，表示最早完成提交的时刻。

样例 1 输入

0 6
2 1 2 2
1 1
2 16 8 27
23 20
3 7 10 1
7 4 2 
4 4 10 5
8 2 3 9 
4 1 9 2
1 3 5 10 
8 2 8 9
6 4 6 8 3 5 9 8

样例 1 输出

0
16
18
28
30
50

数据范围

对于所有测试点，保证：

$$2\le n\le 2000,$$ $$1\le x\le 10^9,\qquad 2\le y\le 10^9,$$ $$0\le m\le 10^{10},\qquad 1\le a_i\le 10^9,\qquad t\le 5.$$

测试点编号	$n\leq$	$x,y,a_i\leq$	$m\leq$
$1\sim 2$	$20$	$10^3$	$10^3$
$3\sim 4$		$10^5$
$5\sim 6$		$10^9$	$10^5$
$7\sim 9$			$10^{10}$
$10\sim 12$	$50$
$13\sim 15$	$300$
$16\sim 20$	$2000$