题目描述

Bob 正在图书集市，他一共购买了 $n$ 本书，第 $i$ 本书的吸引力为 $k_i$。Bob 按照吸引力从左到右单调不减的方式，将所有的书放在了书架上。

Bob 将要花费 $t$ 分钟阅读这些书。对于每一本书，他可以花费 $a$ 分钟完整阅读以获得灵感值，也可以花费 $b$ 分钟，只通过封面了解内容（这种方式不产生灵感值）。

他将从最左侧的书籍开始阅读，当他读完当前的书后（完整阅读或通过封面了解内容），他开始阅读紧靠右侧的下一本书。Bob 获得的灵感值与他完整阅读的书的吸引力之和相等。请问 $t$ 分钟后，Bob 的灵感值最大是多少？

注意：如果 Bob 开始阅读一本书，但是没有在第 $t$ 分钟结束前读完，这本书将不会对 Bob 的灵感值产生贡献。

输入格式

第一行包含四个整数 $n, t, a, b$ —— 分别表示书的数目、Bob 阅读的总时间、完整阅读一本书所需要的时间，以及阅读一本书封面所需要的时间。

第二行包含 $n$ 个整数 $k_1, k_2, \dots, k_n$ —— 表示从左到右每本书的吸引力。

输出格式

输出一行，一个整数，表示 $t$ 分钟后 Bob 能获得的灵感最大值。

样例输入 1

3 5 2 1
2 2 4

样例输出 1

6

样例输入 2

2 10 3 1
3 3

样例输出 2

6

样例输入 3

4 10 3 2
3 4 5 6

样例输出 3

12

说明

样例解释

在第一个样例中，Bob 可以选择完整阅读第 $1$ 本和第 $3$ 本书（耗时 $2 \times 2 = 4$ 分钟），并只阅读第 $2$ 本书的封面（耗时 $1$ 分钟）。这样总耗时为 $4 + 1 = 5 \le t$ 分钟。他获得的灵感值为 $k_1 + k_3 = 2 + 4 = 6$，可以证明这是能够达到的最大灵感值。

数据范围

对于所有测试点，保证:

• $1 \le n \le 2 \times 10^5$。
• $1 \le t \le 10^9$。
• $1 \le b < a \le 10^9$。
• $1 \le k_i \le 10^9$。
• 保证书籍的吸引力是单调不减的，即 $k_i \le k_{i+1}$。
• 保证所有的输入数值均为整数。