logo AlgoBeat OnlineJudge
登录 注册

#101521. [BZOJ 1521] [POI2006]Est

内存限制:64 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题意翻译

现在, 我们有一个由 个单词组成的英文文本。但是它们都挤在一行里,单词间以一个半角空格分隔,就像丑陋的压行代码。你可以把他们通过 次换行分割成 行的文本并去除行首行末空格。为方便题意表述,我们以一个长度为 的数列 ,表示第 到第 个单词放在第 行,第 到第 个单词放在第 行,以此类推。

不过,为了让新的文本更加美妙,你希望在满足每一行的长度不大于 的情况下相邻行长度之差的和最小。具体地,令 表示第个单词的长度, 表示第 行的长度,则:

你需要求得的答案 为:

现在输入单词数 ,行长度限制 ,每个单词的长度 ,请输出答案。

输入格式

The first line of the standard input contains the numbers and , ,, separated by a single space. The second, last line of the standard input contains integers, denotingthe lengths of subsequent words, for , separated by single spaces.

输出格式

The first and only line of the standard output should contain exactly one integer: the minimumcoefficient of aestheticism for those decompositions, whose every line's length does not exceed .

样例

样例输入 #1

6 4
4 3 2 5

样例输出 #1

3