[Solution] Progressions Covering solution codeforces

Progressions Covering solution codeforces – You are given two arrays: an array 𝑎a consisting of 𝑛n zeros and an array 𝑏b consisting of 𝑛n integers.

[Solution] Progressions Covering solution codeforces

You can apply the following operation to the array 𝑎a an arbitrary number of times: choose some subsegment of 𝑎a of length 𝑘k and add the arithmetic progression 1,2,,𝑘1,2,…,k to this subsegment — i. e. add 11 to the first element of the subsegment, 22 to the second element, and so on. The chosen subsegment should be inside the borders of the array 𝑎a (i.e., if the left border of the chosen subsegment is 𝑙l, then the condition 1𝑙𝑙+𝑘1𝑛1≤l≤l+k−1≤n should be satisfied). Note that the progression added is always 1,2,,𝑘1,2,…,k but not the 𝑘,𝑘1,,1k,k−1,…,1 or anything else (i.e., the leftmost element of the subsegment always increases by 11, the second element always increases by 22 and so on).

Your task is to find the minimum possible number of operations required to satisfy the condition 𝑎𝑖𝑏𝑖ai≥bi for each 𝑖i from 11 to 𝑛n. Note that the condition 𝑎𝑖𝑏𝑖ai≥bi should be satisfied for all elements at once.

Input

The first line of the input contains two integers 𝑛n and 𝑘k (1𝑘𝑛31051≤k≤n≤3⋅105) — the number of elements in both arrays and the length of the subsegment, respectively.

The second line of the input contains 𝑛n integers 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn (1𝑏𝑖10121≤bi≤1012), where 𝑏𝑖bi is the 𝑖i-th element of the array 𝑏b.

[Solution] Progressions Covering solution codeforces

Print one integer — the minimum possible number of operations required to satisfy the condition 𝑎𝑖𝑏𝑖ai≥bi for each 𝑖i from 11 to 𝑛n.

Examples
input

Copy
3 3
5 4 6
output

Copy
5
input

Copy
6 3
1 2 3 2 2 3
output

Copy
3
input

Copy
6 3
1 2 4 1 2 3
output

Copy
3
input

Copy
7 3
50 17 81 25 42 39 96
output

Copy
92

Progressions Covering solution codeforces

Consider the first example. In this test, we don’t really have any choice, so we need to add at least five progressions to make the first element equals 55. The array 𝑎a becomes [5,10,15][5,10,15].

Consider the second example. In this test, let’s add one progression on the segment [1;3][1;3] and two progressions on the segment [4;6][4;6]. Then, the array 𝑎a becomes [1,2,3,2,4,6][1,2,3,2,4,6].

 

For Solution

Click here

Leave a Comment