4950: 小L的试卷
[Creator : ]
Description
小L期末考试结束，高高兴兴放假回家了，可是那么多试卷，老师还要加班批改，有 $n$ 份试卷由 $k$ 个老师批改。
$n$ 份试卷进行了密封编号，由于试卷上的做题情况和书写的规范程序不一样，批改不同的试卷用时也可能不一样，每个老师批改试卷的编号顺序是连续的，每位老师批改完分配给自己的试卷就可以离开，问最后离开的老师，最短可能的用时是多少，假定一份试卷让任何一位老师批改用时都是一样的。
现在请你设计一种分配方案，使得最后离开的老师用时最短。
$n$ 份试卷进行了密封编号，由于试卷上的做题情况和书写的规范程序不一样，批改不同的试卷用时也可能不一样，每个老师批改试卷的编号顺序是连续的，每位老师批改完分配给自己的试卷就可以离开，问最后离开的老师，最短可能的用时是多少，假定一份试卷让任何一位老师批改用时都是一样的。
现在请你设计一种分配方案，使得最后离开的老师用时最短。
Input
第一行两个整数 $n,\ k\ (0 < k ≤ n ≤ 1,000,000)$
第二行 $n$ 个整数，第 $i$ 个整数表示批改第 $i$ 份试卷的用时 $x_i\ (1 ≤ x_i ≤ 10^9)$。
第二行 $n$ 个整数，第 $i$ 个整数表示批改第 $i$ 份试卷的用时 $x_i\ (1 ≤ x_i ≤ 10^9)$。
Output
输出一个整数，表示最后离开的老师所用的最短时间。
Sample 1 Input
9 3
1 2 3 4 5 6 7 8 9
Sample 1 Output
17
题目中有几个重要信息：每个老师批改试卷的编号顺序是连续的。要求求最后离开的老师用时最少。那么最后离开的老师耗时，肯定是这 $k$ 个老师中用时最多的。
根据这个意思。我们可以知道，将考卷分为 $k$ 份，每个老师该一份。然后再这个组合中找出答案。
最后分配方案如下：
（1）考卷为 1 2 3 4 5。这个老师将耗时 $15$。
（2）考卷为 6 7。这个老师将耗时 $13$。
（3）考卷为 8 9。这个老师将耗时 $17$。
没有比这个方案更好的。所以答案为 $17$。
根据这个意思。我们可以知道，将考卷分为 $k$ 份，每个老师该一份。然后再这个组合中找出答案。
最后分配方案如下：
（1）考卷为 1 2 3 4 5。这个老师将耗时 $15$。
（2）考卷为 6 7。这个老师将耗时 $13$。
（3）考卷为 8 9。这个老师将耗时 $17$。
没有比这个方案更好的。所以答案为 $17$。