题目描述

小珅和小美打算给花园里的 $n$ 株植物浇水。

植物排成一行，从左到右依次编号为 $1$ 到 $n$。对于第 $i$ 株植物（$1\le i\le n$），其位置为 $x=i$，需要浇水 $w_i$ 升。

小珅和小美每人都有一个水罐。小珅的水罐容量为 $A$ 升，小美的水罐容量为 $B$ 升。初始时，两个水罐都装满了水。

• 小珅从左向右浇水，从第 $1$ 株植物开始；
• 小美从右向左浇水，从第 $n$ 株植物开始；
• 两人同时开始浇水。

他们给植物浇水时，每分钟浇 $1$ 升水。也就是说，每经过一分钟，水罐中的水量减少 $1$ 升，当前植物还需要的水量也减少 $1$ 升。

当一株植物需要的水量变为 $0$ 时，浇水者立即移动到下一株植物：小珅移动到编号大 $1$ 的植物，小美移动到编号小 $1$ 的植物。移动所需的时间忽略不计。

如果浇水过程中水罐里的水耗尽，一个超强水泵会花费 $T$ 分钟将水罐重新灌满，之后继续浇水。

如果一个人到达某株植物时，另一个人已经先到达该植物，那么只由先到达的人为这株植物浇水。如果两人同时到达，则由小珅完成这株植物的浇水。

请计算所有植物完成浇水所需的时间。

输入格式

第一行包含四个正整数 $n,A,B,T$。

第二行包含 $n$ 个正整数 $w_1,w_2,\ldots,w_n$，其中 $w_i$ 表示第 $i$ 株植物需要浇水的升数。

输出格式

输出一行一个整数，表示所有植物完成浇水所需的时间。

样例输入

5 1 9 5
7 3 2 3 2

样例输出

37

样例解释

小珅的水罐容量只有 $1$ 升。第 $1$ 株植物需要浇水 $7$ 升，因此小珅需要重新灌水 $6$ 次，共用时

$7+5\times 6=37$

分钟。第 $37$ 分钟时，小珅到达第 $2$ 株植物，此时水罐中没有水。

小美的水罐容量为 $9$ 升。她依次用 $2,3,2$ 分钟完成第 $5,4,3$ 株植物的浇水，中途不需要重新灌水。第 $7$ 分钟时，小美到达第 $2$ 株植物，水罐中还剩 $2$ 升水。

由于小美先到达第 $2$ 株植物，因此由她完成这株植物的浇水。她先用剩余的 $2$ 升水浇水，再花费 $5$ 分钟将水罐灌满，最后再浇 $1$ 升水，共花费 $8$ 分钟。

小珅共用时 $37$ 分钟，小美共用时 $15$ 分钟。所有植物完成浇水的时间为 $37$ 分钟。

数据范围

• 对于 $50\%$ 的数据，答案不超过 $10^6$；
• 对于 $100\%$ 的数据：
  • $1\le n\le 10^5$；
  • $1\le w_i,T\le 10^6$；
  • $1\le A,B\le 10^9$。

1 1 1 1
1

1

5 1 9 5
7 3 2 3 2

37

5 8 3 4
10 6 2 5 5

26