题目描述

Eli 正在玩一个修改版的 Super Mario 游戏。在这个游戏中，她需要穿过 $N$ 个格子，可以踩在其中一些格子上。她从最左边格子之前开始，当走到最右边格子之后时结束。

每一步，玩家只能从当前位置向右跳 $1$ 到 $K$ 个格子的距离。每当踩到某个格子时，需要支付该格子的价格 $C_i$，每个格子的价格预先已知。

例如，某一关有 $6$ 个格子，从左到右价格为：

最大跳跃长度为 $K=2$。第一步只能跳到第一个或第二个格子，分别支付 $2$ 或 $3$。Eli 会选择第二个格子，虽然支付更高价格，但能到达更靠右的位置。接着她跳到第四个格子（支付 $1$），再跳到第五个格子（支付 $2$），最后跳出棋盘。总价格为 $6$，这也是该关能达到的最小值。

Eli 想在游戏所有关卡中创造纪录，以给 Stancho 留下深刻印象。请帮助她编写程序 supermario，求最优路径的价格。

输入格式

第一行输入两个整数 $N,K$，分别表示格子数量和最大跳跃长度。

第二行输入四个整数 $F,A,B,M$，用于生成每个格子的价格：

• 第一个格子的价格为 $C_1=F$；
• 对于每个 $i=2,\dots,N$，

输出格式

输出一行一个整数，表示 Eli 通过该关卡所需支付的最小总和。

数据范围

• $1 \le N \le 10000000$；
• $1 \le K \le 1000000$；
• $1 \le M \le 1000000007$；
• $0 \le F,A,B<M$；
• 在 $30\%$ 的测试中，$N \le 5000$；
• 在 $60\%$ 的测试中，$N \le 1000000$。

样例

输入

20 5
7 3 8 23

输出

18

样例解释

格子上的数字从左到右为：

7 6 3 17 13 1 11 18 16 10 15 7 6 3 17 13 1 11 18 16

最优路径经过下标为 $3,6,10,14,17$ 的格子，贡献分别为：

随后跳出棋盘，因此答案为 $18$。