3282. 巧克力

【题目描述】

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

来源:mike的模拟赛

数据规模:

对于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