Description

第一行输入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

Input

Output

Samples

6 4
4 3 2 5

3