题目描述

薯条哥需要走路从城市的一端前往另一端。城市可以视为一个长条形，共有$n$个街区，按顺序排成一列，每个街区的右侧紧挨着下一个街区的左侧。

初始时，薯条哥位于第$1$个街区的左侧，他的目标是到达第$n$个街区的右侧。步行通过第$n$个街区时，薯条哥需要花费的时间为$a_n$。

同时，薯条哥可以选择坐最多$m$次地铁。每个街区的左侧都有地铁站，每次坐地铁可以穿越前方最少$1$个，最多$k$个连续的街区。

坐地铁穿越任何一个街区所需的时间都是一个常数$b$(如果穿越$2$个街区，所需的时间是$2\times b$，以此类推)，进地铁站、出地铁站、等待地铁均不耗费时间。

输入描述

第一行输入一个整数$n(1\le n\le 10)$，表示街区数量

第二行输入一个整数$k(1\le k\le n)$，表示最多穿越的街区数量

第三行输入 $n$ 个整数$a_1,a_2,...a_n(1\le a_i\le 10^4)$表示步行穿过每个街区所消耗的时间

第四行输入一个整数$b(0\le b\le 10^4)$，表示穿越任何一个街区所需的时间

第五行输入一个整数$m(1\le m\le 10)$，表示最多乘坐的地铁次数

输出描述

一个整数，表示穿越整个城市花费的最短时间。

样例1

输入

5
1
3 7 5 3 6
0
2

输出

11

样例解释

总共$5$个街区，坐地铁每次只能通过$1$个街区，坐地铁消耗时间为$0$，最多可以坐$2$次地铁。最少消耗的方案为:坐地铁通过第$2$个和第$5$个街区，其余街区步行，最终消耗时间为$3+0+5+3+0=11$。

样例2

输入

5
2
1 2 1 2 2
3
2

输出

8

样例解释

全程走路，不坐地铁，最终消耗时间为$1+2+1+2+2=8$。

样例3

输入

10
2
4 1 12 1 6 7 2 4 4 4
3
2

输出

29

样例解释

坐地铁两次，分别穿越第$3$个街区以及第$5-6$个街区，最终消耗时间为$4+1+3$(地铁)$+1+3×2$(地铁)$+2+4+4+4=29$。