题目描述

小明有一排书，从左到右按“吸引力”不下降排好。共有 $n$ 本，第 $i$ 本的吸引力为 $k_i$。 他有 $t$ 分钟阅读时间。每本书他可以：

• 花 $a$ 分钟完整读完，得到的收获等于这本书的吸引力；
• 花 $b$ 分钟只看封面，不计收获。

他从最左边开始读，当前这本处理完（完整读完或只看封面）才会读右边下一本。 如果开始读了一本书，但没能在第 $t$ 分钟前完成当前选择的方式，这本书不产生收获。

问 $t$ 分钟后，能得到的最大收获是多少？（收获为完整读完的书的吸引力之和）

输入格式

第一行：四个整数 $n,t,a,b$。 第二行：$n$ 个整数 $k_1,\ldots,k_n$，且 $k_i \le k_{i+1}$。

输出格式

输出一个整数，表示最大收获。

输入输出样例 #1

输入 #1

3 5 2 1
2 2 4

输出 #1

6

样例1解释

例如：完整读第 1、3 本，只看第 2 本，可得到最大收获。

输入输出样例 #2

输入 #2

2 10 3 1
3 3

输出 #2

6

输入输出样例 #3

输入 #3

4 10 3 2
3 4 5 6

输出 #3

12

数据范围

对于30%的数据：$n \le 2000$；$t,a,b,k_i \le 10^6$

对于100%的数据：$0\le n \le 2\times 10^5$；$1\le t,a,b,k_i \le 10^9$