← 返回题目列表

AtCoder · awc0065_a

A. 长途驾驶的休息计划

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

分数: 200 分

问题陈述

高桥正在计划一次长途驾驶,包括 N 段。段已编号 1, 2, \ldots, N 从头开始,需要 A_i 开车经过路段的小时数 i。高桥按顺序驾驶穿过各个路段: 路段 1,段 2, …, 段 N.

为了安全起见,高桥按照以下规则休息:

  • 段结束后立即 K,段 2K,段 3K, …,即在完成编号为 的倍数的段之后立即 K,他采取了 1- 如果仍有剩余路段要行驶,则休息一小时。其他时间他都不会休息。

求完成所有路段行驶所需的总时间(行驶时间和休息时间之和)。请注意,总时间始终是整数。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq A_i \leq 10^9
  • 所有输入均为整数
  • 在这些约束下,答案适合 64 位有符号整数

输入

输入按以下格式给出:

N K
A_1 A_2 \cdots A_N

第一行包含段数 N 和休息时间间隔 K,用空格分隔。

第二行包含行驶时间 A_i 段 i,用空格分隔。

输出

打印完成驱动一行中所有段所需的总时间。


示例输入 1

5 2
3 1 4 1 5

示例输出 1

16

示例输入 2

4 4
7 2 8 3

示例输出 2

20

示例输入 3

10 3
5 9 2 6 5 3 5 8 9 7

示例输出 3

62

示例输入 4

20 6
12 7 25 4 18 9 3 14 11 6 20 5 8 17 13 2 10 16 19 15

示例输出 4

237

示例输入 5

1 1
1000000000

示例输出 5

1000000000