花环 Garlands
题意翻译
圣诞节就要到了。现在有个困难的任务摆在你眼前——装饰房间。
你手头上有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”（不包括引号）。
样例输入1：
4 3 10
10 10 20 20
样例输出1：
20
样例输入2：
6 4 10
1 1 100 100 1 1
样例输出2：
100
样例输入3：
6 3 10
1 1 100 100 1 1
样例输出3：
200
样例输入4：
1 2 2
333
样例输出4：
BAD
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=447&page=show_problem&problem=4189
[PDF](https://uva.onlinejudge.org/external/14/p1443.pdf)