/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は N 区間からなる長距離ドライブの計画を立てています。区間には先頭から順に 1, 2, \ldots, N の番号が付いており、第 i 区間を走行するには A_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-bit 符号付き整数に収まる
入力
入力は以下の形式で与えられます。
N K A_1 A_2 \cdots A_N
1 行目には、区間の数 N と休憩を挟む間隔 K がスペース区切りで与えられます。
2 行目には、第 i 区間の走行時間 A_i が空白区切りで与えられます。
出力
すべての区間を走り終えるまでにかかる合計時間を 1 行で出力してください。
入力例 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
Score : 200 pts
Problem Statement
Takahashi is planning a long-distance drive consisting of N segments. The segments are numbered 1, 2, \ldots, N from the beginning, and it takes A_i hours to drive through segment i. Takahashi drives through the segments in order: segment 1, segment 2, …, segment N.
For safety, Takahashi takes breaks according to the following rule:
- Immediately after finishing segment K, segment 2K, segment 3K, …, that is, immediately after finishing a segment whose number is a multiple of K, he takes a 1-hour break if there are still remaining segments to drive. He does not take breaks at any other time.
Find the total time (the sum of driving time and break time) it takes to finish driving all segments. Note that the total time is always an integer.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 1 \leq A_i \leq 10^9
- All inputs are integers
- Under these constraints, the answer fits in a 64-bit signed integer
Input
The input is given in the following format:
N K A_1 A_2 \cdots A_N
The first line contains the number of segments N and the break interval K, separated by a space.
The second line contains the driving time A_i for segment i, separated by spaces.
Output
Print the total time it takes to finish driving all segments in one line.
Sample Input 1
5 2 3 1 4 1 5
Sample Output 1
16
Sample Input 2
4 4 7 2 8 3
Sample Output 2
20
Sample Input 3
10 3 5 9 2 6 5 3 5 8 9 7
Sample Output 3
62
Sample Input 4
20 6 12 7 25 4 18 9 3 14 11 6 20 5 8 17 13 2 10 16 19 15
Sample Output 4
237
Sample Input 5
1 1 1000000000
Sample Output 5
1000000000