#1521. [POI2006]Est

题目描述

第一行输入M,N 代表文章的某一行的总宽度不能超过M.N代表有N个句子 第二行给出N个数,代表这N个句子各自的长度 你的任务就是进行文章排版操作.使文章的不合谐度最小.对于下面这个图,其不合谐度为 XXXX XXX XX XXXXX |6-4|+|5-6|=3.如果文章只有一行的话,则不合谐度为0.你可以将多个连续的句子放到同一行去,任两个句子间用一个空格格开,但它们的总长度不能超过M. 1<=M<=10^6,1<=N<=2000,1<=Ai<=M

输入格式

输出格式

样例

样例输入

6 4  

4 3 2 5

样例输出

3

数据范围与提示