3.金明的游戏方案

Tyvj2012寒假模拟赛 
【问题描述】
金明今天很开心，他住进了他的新房，新房里有一间金明自己专用的很宽敞的房间。
金明通过金明的预算买到了许许多多的东西——包括一台电脑。更让他高兴的是，妈妈昨
天对他说：“你想玩多久电脑就玩多久，你说了算，只要别忘了睡觉就行。”
以一天为例，他把一天等分成了N 个时间段，在每个时间段玩游戏能获得的开心值各
不相同，在第i 个时间段能获得w[i]个开心值。因为要抽出时间睡觉，所以金明决定自己
一天只玩M 个时间段。
令金明万万没有想到的是，他没有考虑到很重要的一点，那就是网速！极不给力的网
速让金明感觉非常不爽。金明为了在接近1kbps（为什么不是1kb/s？1kbps 要比1kb/s
慢7 倍！）的网速中玩得更加舒畅一些，经过多次实验，他发现：每个游戏打开的时候都需
要一个时间段，多个游戏一起打开，也只需要一个时间段；只要打开游戏之后，玩起来就
不会卡。
因此，金明决定：先分配好M 个时间段（这M 个时间段可以是连续的，也可以是分散
的，只要让总的开心值尽可能得大就行），在每个连续一段玩游戏时间的第一个时间段打开
整段时间要玩的游戏。也就是说，他如果在i~j 中的所有时间段都玩游戏了，那么获得的
开心值就是SUM{w[k]}(i+1<= k <= j)（因为第i 个时间段用来打开所有要玩的游戏了，所
以不能获得开心值w[i]）
所有的时间段都是环形相连的，即第N 个时间段后是第1 个时间段。
金明想知道他能获得的最大开心值是多少？
【输入】
输入包含2 行。第一行两个正整数N,M，含义如题所述。
第二行N 个由一个空格隔开的非负整数w[i]。
【输出】
输出仅1 行，表示金明能获得的最大开心值。
【样例输入】
8 4
0 8 0 4 0 8 0 4
【样例输出】
16
【样例解释】
选择第1、2、5、6 个时间段，每个连续时间段的第一个时间段即第1、5 个时间段打
开网站，获得的最大开心值是w[2]+w[6]=8+8=16
【数据范围】
对于20%的数据，N <=20
对于50%的数据，N <=200

对于100%的数据，N <=5,000,M <= N,w[i] <= 10,000