#6101. 「2017 山东二轮集训 Day1」第二题

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

题目描述

小火车沉迷垃圾手游不能自拔,他还在玩碧蓝航线。

为了庆祝小火车打捞出了加贺赤城,他决定让你搭建一座纪念塔群,纪念塔共有 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