#P2219. 展板排版
展板排版
本题需要文件读写
文件 IO 为:输入文件
layout.in,输出文件layout.out。请使用上述文件名读入和输出。
问题描述
市科技节需要制作一块介绍各项活动的展板。展板上有 个词条,必须按照给定的顺序,从左到右、从上到下排列。第 个词条的宽度为 ,所有词条的高度相同。
设计师准备把这些词条排成恰好 行,每行至少有一个词条,具体要求如下:
- 每个词条必须完整地放在一行中,不能拆开,也不能改变词条顺序。
- 同一行中,相邻两个词条之间留出宽度为 的空隙。
- 每行的开头和末尾不额外留空隙。若一行包含词条 ,该行的宽度为 。
展板各行的可用宽度统一为 ,每一行的实际宽度都不能超过 。请你求出满足要求的最小整数 。
输入格式
第一行包含两个正整数 ,分别表示词条数量和需要排成的行数。
第二行包含 个正整数 ,表示每个词条的宽度。
输出格式
输出一行一个整数,表示最小可用宽度 。
样例输入 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。
评测数据规模
对于 的数据,保证 ,,所有输入均为整数。
各测试点的附加限制如下表所示:
| 测试点编号 | 特殊性质 | ||
|---|---|---|---|
| 无 | |||
| A | |||
| B | |||
| C | |||
| 无 |
- 特殊性质 A:。
- 特殊性质 B:。
- 特殊性质 C:。
本题共 个独立测试点,每点 分。