409810: GYM103785 E Hostel Cleaning

All the rooms of Shankar Bhawan are dirty - as they have not been cleaned since the start of the semester! Help Utkarsh clean the bhavan.

There are $$$N$$$ rooms in Shankar Bhawan - numbered from $$$1$$$ to $$$N$$$. They are laid out in a circular format - such that room $$$1$$$ is adjacent to room $$$2$$$, room $$$2$$$ is adjacent to room $$$3$$$, ... , room $$$N-1$$$ is adjacent to room $$$N$$$ and room $$$N$$$ is adjacent to room $$$1$$$.

Utkarsh has somehow managed to get $$$N$$$ sweepers to clean the hostel. Each sweeper can sweep $$$K$$$ rooms in a row, and it is guaranteed that $$$K$$$ is a factor of $$$N$$$. The $$$i^{th}$$$ sweeper can clean $$$K$$$ rooms starting from room $$$i$$$. So, they can clean $$$i$$$, $$$i + 1$$$, $$$i + 2$$$, and so on. (Note than room $$$1$$$ comes after room $$$N$$$).

Moreover, the $$$i^{th}$$$ sweeper charges $$$A_i$$$ rupees for cleaning this set of $$$K$$$ rooms.

Utkarsh wants to hire the minimum number of sweepers for accomplishing the task of cleaning all the rooms. Moreover, he wants to hire these sweepers in such a way that the amount of money he spends is also minimized!

Help Utkarsh find the minimum cost for cleaning the hostel.

The first line of input contains two integers $$$N (1 \leq N \leq 2 \cdot 10^5)$$$ - the number of rooms, and $$$K (1 \leq K \leq N)$$$, the number of rooms in a row each sweeper can clean. It is guaranteed that $$$N$$$ is a multiple of $$$K$$$.

The next line contains $$$N$$$ space-separated integers representing the cost of cleaning the rooms for each sweeper. $$$(1 \leq A_{i} \leq 10^9)$$$.

Output a single integer - the minimum cost to clean the entire hostel.

Note : The answer may exceed 32-bit data types. Consider using 64-bit data types, such as long long in C++!

6 3
2 2 1 3 2 4

4

In this case, it is optimum to hire sweepers $$$2$$$ and $$$5$$$. Sweeper $$$2$$$ will clean the rooms $$$2,3,4$$$ and sweeper $$$5$$$ will clean the rooms $$$5, 6, 1$$$. The total cost is $$$2 + 2 = 4$$$ rupees.