{"raw_statement":[{"iden":"statement","content":"比赛之路多艰，做题方得提升。努力刷题的人在比赛中往往能取得很好的成绩，小红就是这样的人。\n\n为了继续提升自己的编程实力，小红整理了一份刷题题单，并选中了题单中的 $n$ 道编程题，将它们从 $1$ 到 $n$ 编号，计划用 $m$ 天时间按照题目编号顺序做完所有的题目（一道题目只能在同一天完成，不可以使用多天完成同一道题目）。\n\n在小红的计划中，她完成第 $i$ 道题目的时间为 $a_i$。因为题目有难有易，小红做题时可以找好朋友小明帮忙解题，通过询问小明一道题目的解法，可以省去这个题目的做题时间。当然了，小红做题是为了提升自己，而不是提升小明。因此小红决定一天最多求助小明一次。\n\n本题 $m$ 天中，小红做题时间最长一天的总耗时定义为 $T$（小明帮忙做的题目不计入小红的做题总时间）。请你帮小红求出 $T$ 的最小值是多少？"},{"iden":"input","content":"第一行两个正整数 $n,m$ 分别表示小红做的题目以及小红刷完这些题目计划所用天数。\n\n第二行 $n$ 个正整数，分别表示每个题目解题所用时间 $a_i$。"},{"iden":"output","content":"输出仅一行，$m$ 天中耗时最长一天的总耗时 $T$ 的最小值。"},{"iden":"note","content":"对于 $30\\%$ 的数据，满足 $1 \\leq n \\leq 10^3$。\n\n对于 $60\\%$ 的数据，满足 $1 \\leq n \\leq 10^4$。\n\n对于 $100\\%$ 的数据，满足 $1 \\leq n \\leq 10^5,0 \\leq a_i \\leq 10^4,1 \\leq m \\leq 1000$。"}],"translated_statement":null,"sample_group":[["4 2\n1 2 3 3","3"],["3 4\n999 999 999","0"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}