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

传统 1000 ms 512 MiB

$83$ 通过 $155$ 提交

题目描述

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

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