Problem Description

When Xiao Lan was shopping, he encountered a lottery event.

At the beginning, there are $n$ balls arranged in a row from left to right. The $i$-th ball has an integer $a_i$ written on it.

Xiao Lan bought $k$ lottery chances in total. In each lottery, he can choose one ball from the remaining balls and take it away, but only balls that satisfy the following conditions can be taken:

Suppose this ball is currently the $i$-th ball from left to right among the remaining balls. Let:

• $L_i$ be the number of remaining balls to the left of this ball.
• $R_i$ be the number of remaining balls to the right of this ball.

Then this ball must satisfy both:

• $R_i > 0$.
• $L_i$ is an integer multiple of $R_i$ (in particular, $0$ is considered an integer multiple of any non-zero integer).

After taking a ball each time, the remaining balls will be rearranged into a row while keeping their original relative order.

Xiao Lan can perform at most $k$ lotteries, and he may also perform fewer than $k$ times. Please compute the maximum possible sum of the integers on the balls he can take.

Input Format

The input has two lines.

The first line contains two positive integers $n, k$.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, representing the integer on each ball.

Output Format

Output one line with one integer, representing the maximum sum of integers Xiao Lan can obtain after at most $k$ lotteries.

7 2
2 8 2 4 2 6 3

10

Hint

Sample Explanation

One feasible plan is:

• In the first time, take the current $4$-th ball and get $4$.
• The remaining balls become $2, 8, 2, 2, 6, 3$.
• In the second time, take the current $5$-th ball and get $6$.

The total sum is $4 + 6 = 10$.

Another feasible plan is:

• In the first time, take the current $1$-st ball and get $2$.
• The remaining balls become $8, 2, 4, 2, 6, 3$.
• In the second time, take the current $1$-st ball again and get $8$.

The total sum is also $2 + 8 = 10$.

Constraints

For $100\%$ of the data, it is guaranteed that $1 \le k \le n \le 20$ and $1 \le a_i \le 100$.

Translated by ChatGPT 5