问题描述

“今天双十一，商店打折，你有什么想买的吗？”Marvolo望着网页上琳琅满目的打折商品，问一旁刷题的Mike。

“现在巧克力什么价位？”Mike头也不抬的说。

“今天是光棍节，你买巧克力干什么？难不成……”

Marvolo露出恍然大悟的神色。

“不是我想买，是我想卖，喏，那边有一抽屉我在情人节攒下的巧克力” “……”

Mike在之前攒下了很多巧克力，可惜他本人对于巧克力研究不多。查阅了资料后发现，巧克力的美味值是可以定量分析的。因此他打算制作一些精美可口的巧克力给自己吃。他有N块巧克力，每一块有一个可口度Vi，现在Mike想将连续的一段区间的巧克力打包，制成M个大的巧克力。也就是将这N块巧克力分为M段。定义大巧克力的美味值为Y=a*x+b（a,b>0）,x为这一段区间的巧克力的可口度之和。因为巧克力吃多了会很腻，所以Mike想让这M块巧克力中最大的美味值尽可能小，求这个最小值。

【输入格式】

第一行有四个整数a,b,N,M，含义如上文描述。

接下来n行，第i+1行有一个整数vi，含义如上文描述。

【输出格式】

一个整数，表示最大的美味度的最小值。

【样例输入】

3 2 5 2
2 1 3 4 5

【样例输出】

29

【数据范围】

对于20%的数据，n,m<=10，a,b<=10

对于40%的数据，n,m<=2000，a,b<=1000

对于80%的数据，n,m<=50000，a,b<=10000

对于100%的数据，n,m<=100000，0<a,b<=100000 vi<=1000