#P2219. 展板排版

展板排版

本题需要文件读写

文件 IO 为:输入文件 layout.in,输出文件 layout.out。请使用上述文件名读入和输出。

问题描述

市科技节需要制作一块介绍各项活动的展板。展板上有 nn 个词条,必须按照给定的顺序,从左到右、从上到下排列。第 ii 个词条的宽度为 LiL_i,所有词条的高度相同。

设计师准备把这些词条排成恰好 mm 行,每行至少有一个词条,具体要求如下:

  • 每个词条必须完整地放在一行中,不能拆开,也不能改变词条顺序。
  • 同一行中,相邻两个词条之间留出宽度为 11 的空隙。
  • 每行的开头和末尾不额外留空隙。若一行包含词条 l,l+1,…,rl,l+1,\ldots,r,该行的宽度为 Ll+Ll+1+⋯+Lr+(r−l)L_l+L_{l+1}+\cdots+L_r+(r-l)。

展板各行的可用宽度统一为 WW,每一行的实际宽度都不能超过 WW。请你求出满足要求的最小整数 WW。

输入格式

第一行包含两个正整数 n,mn,m,分别表示词条数量和需要排成的行数。

第二行包含 nn 个正整数 L1,L2,…,LnL_1,L_2,\ldots,L_n,表示每个词条的宽度。

输出格式

输出一行一个整数,表示最小可用宽度 WW。

样例输入 1

13 3
9 5 2 7 1 8 8 2 1 5 2 3 6

样例输出 1

26

样例输入 2

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

样例输出 2

10000000009

样例输入 3

30 8
8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32 60

样例输出 3

189

说明

公开分档大样例:下载 samples.zip。

评测数据规模

对于 100%100\% 的数据,保证 1≤m≤n≤2×1051\le m\le n\le2\times10^5,1≤Li≤1091\le L_i\le10^9,所有输入均为整数。

各测试点的附加限制如下表所示:

测试点编号 n≤n\le Li≤L_i\le 特殊性质
1∼41\sim4 2020 10910^9 无
5∼85\sim8 500500
9∼109\sim10 2×1052\times10^5 A
11∼1211\sim12 B
13∼1413\sim14 C
15∼2015\sim20 无
  • 特殊性质 A:m=1m=1。
  • 特殊性质 B:m=nm=n。
  • 特殊性质 C:L1=L2=⋯=LnL_1=L_2=\cdots=L_n。

本题共 2020 个独立测试点,每点 55 分。