Edwardo the florist is cutting paper flowers.
Each paper flower is created by cutting a circular piece of paper with $$$n$$$ digits written on the outside edge where each digit is a number from $$$1$$$ to $$$9$$$. Since the paper is circular, the $$$n$$$th digit is adjacent to the first. The paper will be cut into $$$m$$$ petals, where each of the original numbers is located in exactly one petal, and each petal is represented by a contiguous region of the paper. However, Edwardo likes symmetrical flowers, so all petals have to have the same number of digits on them.
For example, if the $$$n$$$ digits are $$$1 2 3 4 5 6$$$, Edwardo could cut this up into $$$3$$$ petals with values $$$2 3 4$$$, $$$5 6$$$, and $$$1$$$, as shown in the following image:
The ugliness of the flower is equal to the sum of the numbers written on each petal. The ugliness of the example cut is $$$234 + 56 + 1 = 291$$$. Edwardo wants to minimize the ugliness of his flower, so he asks you to find the minimum possible ugliness of his flower after cutting it into $$$m$$$ petals.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^6$$$, $$$1 \leq m \leq n$$$) — denoting the number of digits on the circular paper, and the number of petals in the resulting flower respectively. It is also guaranteed that $$$\frac{n}{m}$$$ is an integer, and that $$$\frac{n}{m} \leq 10^3$$$.
The second line contains $$$n$$$ space-separated integers $$$d_1, d_2, ..., d_n$$$ ($$$1 \leq d_i \leq 9$$$) — where $$$d_i$$$ denotes the $$$i$$$th digit on the circular paper.
Output a single integer, representing the minimum possible ugliness of a flower that Edwardo can create out of $$$m$$$ petals. Note that the answer may not fit in a 64-bit (or even 128-bit) integer.
6 21 2 3 4 5 6
579
6 23 9 6 3 9 1
778
In the first test case, the optimal cutting is to split $$$123456$$$ into $$$123 + 456$$$.
In the second test case, the optimal cutting is $$$139 + 639 = 778$$$.
