2243: 圣诞节的花环
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：0
题目描述
圣诞节就要到了。现在有个困难的任务摆在你眼前——装饰房间。
你手头上有n朵大小相同的花，第i朵花的重量为wi。现在打算用一根绳将这n朵花按顺序穿起来，挂在天花板上。绳子被m个点固定，也就是绳子的一头被固定在1号点，另外一头固定在m号点，中间部分需要固定在剩余的点。当然，装饰还有一些规则要注意：
（i） 每一段需要包含非0的偶数个花朵。正因如此，我们可以将每一段划分为两个半段。
（ii） 为了减小你的客人撞到花环的可能，花环不能挂的太低：也就是说，每个半段不能超过d朵花。
（iii） 最后，你需要让所有半段的重量的最大值最小。
下图是一个不错的安排方案，圈中的数字代表花朵的重量。
输入
第一行包含三个正整数n，m和d（1 ≤ n ≤ 15000,2 ≤ m ≤ 10000，1 ≤ d ≤ 2000，且n*d ≤ 5000000）。
接下来一行包含n个正整数w1，w2，…，wn（1 ≤ wi ≤ 10000），代表对应花的重量。
输出
输出一行一个整数，代表最小的所有半段重量的最大值。如果没有方案满足条件，那么你只要输出“BAD”（不包括引号）。
样例输入 复制
4 3 10
10 10 20 20
样例输出 复制
20提示
样例输入3：
6 3 10
1 1 100 100 1 1
样例输出3：
200
样例输入4：
1 2 2
333
样例输出4：
BAD