← 返回题目列表

AtCoder · awc0010_d

D. 岩石破坏

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥在采石场工作。有 N 岩石在采石场排成一排,他需要将它们全部摧毁。

的 i第岩石具有硬度 H_i。高桥按照从上至下的顺序将岩石一颗一颗地加工 1-st 摇滚到 N第岩石。在当前岩石被摧毁之前,他无法继续处理下一块岩石。

每回合,高桥选择并执行以下两个动作之一:

  • 用锤子敲击:降低当前正在加工的岩石的硬度 1。这消耗 1 转。
  • 使用炸药:立即降低当前正在加工的岩石的硬度 0。这消耗 1 转。然而,高桥只有 K 炸药棒,每次使用消耗 1 坚持。当他有以下动作时,不能选择该动作 剩余的 0 棒。

当岩石的硬度变为 0,该岩石被破坏,他继续处理下一块岩石。一旦所有岩石都被摧毁,工作就完成了。

求当高桥表现最佳时摧毁所有岩石所需的最少回合数。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq K \leq N
  • 1 \leq H_i \leq 10^9
  • 所有输入均为整数

输入

N K
H_1 H_2 \ldots H_N
  • 第一行包含一个整数 N 代表岩石的数量和一个整数 K 代表炸药棒的数量,以空格分隔。
  • 第二行包含整数 H_1, H_2, \ldots, H_N 代表每块岩石的硬度,以空格分隔。

输出

打印摧毁一行中所有岩石所需的最小圈数。


示例输入 1

3 1
5 2 8

示例输出 1

8

示例输入 2

5 2
10 3 7 4 6

示例输出 2

15

示例输入 3

8 3
100 5 200 8 150 3 50 300

示例输出 3

169