小R的飞行之旅

时间限制：1s

空间限制：256MB

Description

\(小R\)有一架自己的低空飞行器，这一天她打算从当前的城市开始全国飞行。

行途上有\(n\)个供油站，每个站点都可以为她的油箱加满油，每个站点之间的距离是不一样的，飞行一公里大概消耗油量\(j\)升，她的油箱在出发时是加满油的状态，并且飞行器油箱的最大容量为\(s\)升。

因为沿途的风景都太好看啦，她不想浪费时间停靠，所以她只打算停靠\(k\)个站点，请问她在停靠\(k\)个站点去加油的情况下，她旅途的最大里程是多少？

注：忽略飞行器降落和起飞过程中消耗的油量。

Input Format

第一行包含一个整数\(n(1 \le n \le 10)\)，即所有的供给站的数量,和每公里耗油量\(j\)、油箱的最大容量\(s\)、和\(小R\)停靠的站点个数\(k\)。

第二行包含\(n-1\)个两供给站相邻两个的距离\(l_i\)

其中\(l_0\)表示第一个供给站与第二个供给站之间的距离，并且 \(j\) 和 \(l_i\) 是浮点数。

Output Format

输出一个浮点数，表示\(小R\)旅途的最大里程，保留 \(6\) 位有效数字。

Data Range

• \(1 \le k \le n \le 50\),\(1 \le j \le 5\),\(1 \le s \le 1000\)

• \(1 \le l_i \le 100\)

Input Example #1：

6 2 371 2
90 120 60 80 180

Output Example #1：

455.5

Note

在第一此段飞行后，油量只剩下191升，不够飞下一段旅程，所以这一站必须下去加油，刚好与飞行第二站和第三站所需的油量接近，所以第二站不需要加油，以此类推，还能在第三站加一次油。