U224150 【D&S R1-1】爆米花机炸爆米花

安吉拉拟将图书馆改造成爆米花厂。

在接下来 $T$ 天中，你要用 $k$ 个[爆米花机](https://zh.moegirl.org.cn/%E7%BD%97%E5%85%B0(%E5%BA%9F%E5%A2%9F%E5%9B%BE%E4%B9%A6%E9%A6%86)#)在第 $i$ 天炸 $p_i$ 份爆米花。每个爆米花机一次只能炸一份爆米花，但是一天内可以炸多次。 爆米花机最初均为精力充沛的，炸出的爆米花美味度为 $a$。在炸过**任意**一次爆米花后，这个爆米花机变为精疲力尽。精疲力尽的爆米花机仍可炸爆米花，炸出的爆米花美味度为 $b$。假如一个筋疲力尽的爆米花机在第 $i$ 天没有炸爆米花，那么他将在第 $i+1$ 天重新精力充沛。 让所有炸出的爆米花美味度之和最大。

第一行四个整数 $k,T,a,b$。 以下一行 $T$ 个整数，表示 $p_i$。

输出一个整数表示答案。

【数据范围与提示】 **本题采用捆绑测试。** | Subtask 编号 | $k$ | $T$ | $a$ | $b$ | $p_i$ | 分数 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $\leq 10$ | $\leq 10$ | $\leq 10$ | $\leq 10$ | $\leq 10$ | $10$ | | $2$ | $\leq 100$ | $\leq 100$ | $\leq 10$ | $\leq 10$ | $\leq 100$ | $15$ | | $3$ | $\leq 10^4$ | $\leq 10^6$ | $\leq 10$ | $\leq 10$ | $\leq 10^6$ | $75$ | 对于 $100\%$ 的数据， $1\leq k\leq 10^4$，$1\leq T\leq 10^6$，$0\leq p_i\leq 10^6$，$0\leq a\leq 10$，$0\leq b\leq 10$。