Logo Quest Online Judge

QOJ

时间限制:1 s 空间限制:512 MB

#2223. Wall

统计

题目描述

吉吉国国王有一个伟大墙国梦,为了增加他的霸权统治,他决定让你搭建一面墙,墙共有 $ n $ 块墙排成一排,第 $ i $ 块墙的高度为 $ H_i $,也就是由 $ H_i $ 块砖头组成,你得一块一块砖头搭建。每次你至多能携带 $ k $ 块砖头,由任意一块墙的底端开始,可以向上移动或者向左右两座塔的同高度移动(前提是那些位置上有砖块),也可以在那些位置摆上砖块(即使是悬空的),并且一旦摆上砖块你就得立刻移动过去。请问你最少需要多少次才能搭建完呢?

输入格式

第一行两个整数 $ n,k $,表示有 $ n $ 块墙,每次你可以携带 $ k $ 块砖头。
第二行有 $ n $ 个整数表示 $ H_i $。

输出格式

一行一个整数表示答案。

样例

样例输入

5 10
2 1 2 1 2

样例输出

3

数据范围与提示

对于 $ 20\% $ 的数据 $ n \leq 4, H_i \leq 5 $;

对于 $ 50\% $ 的数据满足 $ n \leq 5000 $;

对于 $ 100\% $ 的数据满足 $ n \leq 100000, 0 \leq H_i \leq 10 ^ 9 , 1 \leq k \leq 10 ^ 9 $。