It's Ramadan and the store owner has decided to make a generous offer to the customers.
There are $n$ products in the store, the cost of the $i^{th}$ product is a positive integer $a_i$ (0-indexed).
The owner gives Ali a positive integer $k$ and asks him to pick an integer $p$ ($0\le p \le n-1$), and he will get the products at positions $p, p+k, p+2k, p+3k, ...$ for free.
Ali will take advantage of such offers so he wants to calculate the minimum possible cost he has to pay to buy all the $n$ products, using the offer at most once.
The first line of input contains two positive integers $n$ and $k$ ( $1\le k \le n \le 10^3$ ) - the number of products, and the integer given by the owner respectively.
The second line contains $n$ space separated integers $a_0,a_1,a_2,...a_{n-1}$ ( $1 \le a_i \le 10^9$ ) - the costs of the products.
The output should contain one integer, the minimum possible cost Ali has to pay to buy all the $n$ products, using the offer at most once.
| Input | Output |
|---|---|
5 2 1 2 3 4 5 Copy
|
6 Copy
|
It's always better for us to use the offer because the costs are all positive.
First, we define $S$ to be the sum of all costs of products, and $F_i$ to be the sum of costs of products that can be taken for free using the offer when $p=i$.
To get the minimum cost we need $F_i$ to be the maximum possible.
Note that the maximal $F_i$ can be achieved only if $0 \le i \lt k$, because $F_i \ge F_{i+k}$, since $F_i=F_{i+k}+a_i>F_{i+k}$ because $a_i$ is positive.
That simply means that we don't care about $F_i$ for $k \le i \le n-1$.
All we have to do now is to calculate $F_i$ for $0 \le i \lt k$ using a loop, and then take the maximum value among them, let's call it $M$. The cost we have to pay is $S-M$.
Time complexity is $O(n)$, because every product will be iterated only once.
You brute force the answer since the constraints are low.