Problem A: 开卷有益
Memory Limit：512 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：30
Solved：0
Description
我最爱去的书店
她也没撑过这个夏天
回忆文字流淌着怀念
可是已没什么好怀念
【题目描述】
David Tao 的学校图书馆中有个圆形的桌子，沿着桌边放着一圈书，共有 n 本，这
些书构成了一个环形的结构，沿顺时针方向依次编号为 1, 2, · · · , n，且第 n 本书第 1 本
书也是相邻的。
David 有 m 个学习 OI 的朋友，他觉得朋友们看屏幕时间太久了，需要多看看书。于
是 David 决定把这些书推荐给他们，为了方便，他打算把桌上的书分成 m 段连续的区间，
在总数不超过 n 的前提下，每个区间可以包含任意多本书，但每本书至多属于一个区间。
这样每个区间内的书，就打包在一起，送给某个朋友。
虽然 David 不是 OIer，但他隐约知道 OIer 有一些奇怪的偏好，比如喜欢绿色封面
的书，不喜欢红色封面的书；又比如喜欢书名中有“AC”，不喜欢有“WA”之类的关键
词。他努力给了每本书一个好感值，比如绿色封面的书的好感值就为正数，红色封面的
书的好感值就为负数。
最后，David 希望自己选择的赠书方案的好感值总和尽可能大，请问这个最大值是多
少？
她也没撑过这个夏天
回忆文字流淌着怀念
可是已没什么好怀念
【题目描述】
David Tao 的学校图书馆中有个圆形的桌子，沿着桌边放着一圈书，共有 n 本，这
些书构成了一个环形的结构，沿顺时针方向依次编号为 1, 2, · · · , n，且第 n 本书第 1 本
书也是相邻的。
David 有 m 个学习 OI 的朋友，他觉得朋友们看屏幕时间太久了，需要多看看书。于
是 David 决定把这些书推荐给他们，为了方便，他打算把桌上的书分成 m 段连续的区间，
在总数不超过 n 的前提下，每个区间可以包含任意多本书，但每本书至多属于一个区间。
这样每个区间内的书，就打包在一起，送给某个朋友。
虽然 David 不是 OIer，但他隐约知道 OIer 有一些奇怪的偏好，比如喜欢绿色封面
的书，不喜欢红色封面的书；又比如喜欢书名中有“AC”，不喜欢有“WA”之类的关键
词。他努力给了每本书一个好感值，比如绿色封面的书的好感值就为正数，红色封面的
书的好感值就为负数。
最后，David 希望自己选择的赠书方案的好感值总和尽可能大，请问这个最大值是多
少？
Input
第一行包含两个正整数 n 和 m，分别表示书本数量与朋友数量。
第二行包含 n 个整数，其中第 i 个整数 Fi 表示第 i 本书的好感值。数据保证至少有
m 本书的好感值是正数，即最后得到的好感值总和总是可以大于 0 的。
第二行包含 n 个整数，其中第 i 个整数 Fi 表示第 i 本书的好感值。数据保证至少有
m 本书的好感值是正数，即最后得到的好感值总和总是可以大于 0 的。
Output
输出一行一个正整数，表示 David 能选择的赠书方案的最大好感值总和。
Sample Input Copy
10 3
‐1 6 ‐2 7 ‐3 8 ‐4 9 ‐5 10
Sample Output Copy
37HINT
共有 10 本书，其好感值依次为 −1, 6, −2, 7, −3, 8, −4, 9, −5, 10，David 需要从中选
出 3 个区间，依次为：第 10, 1, 2, 3, 4 本书构成的区间，第 6、第 8 本书单独构成的两个
区间，第 1 个区间的好感值为 10 + (−1) + 6 + (−2) + 7 = 20，后两个区间的好感值分别
出 3 个区间，依次为：第 10, 1, 2, 3, 4 本书构成的区间，第 6、第 8 本书单独构成的两个
区间，第 1 个区间的好感值为 10 + (−1) + 6 + (−2) + 7 = 20，后两个区间的好感值分别
为 8 和 9，故总体好感值为 20 + 8 + 9 = 37，可以证明这是最优的选择方案。
对于 100% 的数据，保证 1 ⩽ n ⩽ 3 × 105, 1 ⩽ m ⩽ 105, −100 ⩽ Fi ⩽ 100 且 Fi ̸= 0。
测试点数量 n ⩽ m ⩽
25% 30 10
50% 3000 1000
此外每一档数据内部，各有 20% 的数据保证 m = 1，还有 20% 的数据保证 m = 2，
另有 20% 的数据保证 m ⩽ 10。