题目描述

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,...,a_n$ 和一个参数 $k$，你可以将其分成连续的若干段，使得每一段的元素和均不超过给定参数 $k$ .

请问，如何分段，才能使得相邻两段元素和的差值的绝对值之和最小。

输入格式

输入共两行： 第一行，两个正整数 $n,k$ 第二行，$n$ 个正整数 $a_1,...,a_n$

输出格式

输出共一行，一个整数，表示答案

6 10
7 3 7 2 6 5

5

样例解释 1

分成四段：7 3|7 2|6|5 ANS=|10-9|+|9-6|+|6-5|=5

6 10
7 3 7 2 5 6

4

样例解释 2

分成四段：7 3|7|2 5|6 ANS=|10-7|+|7-7|+|7-6|=4

6 10
7 3 6 4 2 8

0

数据范围

• 对于 $30\%$ 的数据，$1 \leq n \leq 10$
• 对于 $60\%$ 的数据，$1 \leq n \leq 100,1 \leq a_i,k \leq 100$
• 对于 $100\%$ 的数据，$1 \leq n \leq 10^3,1 \leq a_i,k \leq 10^6$