#CSPXSD2024D. 刷题 (question)

刷题 (question)

【题目描述】

比赛之路多艰,做题方得提升。努力刷题的人在比赛中往往能取得很好的成绩,小红就是这样的人。

为了继续提升自己的编程实力,小红整理了一份刷题题单,并选中了题单中的 n 道编程题,将它们从 1 到 n 编号,计划用 m 天时间按照题目编号顺序做完所有的题目(一道题目只能在同一天完成,不可以使用多天完成同一道题目)。

在小红的计划中,她完成第 i 道题目的时间为 aia_i。因为题目有难有易,小红做题时可以找好朋友小明帮忙解题,通过询问小明一道题目的解法,可以省去这个题目的做题时间。当然了,小红做题是为了提升自己,而不是提升小明。因此小决定一天最多求助小明一次。

本题 m 天中,小红做题时间最长一天的总耗时定义为 T(小明帮忙做的题目不计入小红的做题总时间)。请你帮小红求出 T 的最小值是多少?

【输入格式】

输入文件为 question.in。

第一行两个正整数 n, m 分别表示小红做的题目以及小红刷完这些题目计划所用天数。

第二行 n 个正整数,分别表示每个题目解题所用时间 aia_i

【输出格式】

输出文件为 question.out。

输出仅一行, m 天中耗时最长一天的总耗时 T 的最小值。

【样例 1 输入】

4 2
1 2 3 3

【样例 1 输出】

3

【样例 2 输入】

3 4
999 999 999

【样例 2 输出】

0

【数据范围】

30% 的数据,n1000n ≤ 1000; 60% 的数据,n10000n ≤ 10000; 100% 的数据,n100000,0ai10000,1m1000n ≤ 100000,0 ≤ ai ≤ 10000,1 ≤ m ≤ 1000