题目描述

小蓝在逛街时遇到了一个抽奖活动。

初始时，有 $n$ 个小球按从左到右的顺序排成一排，第 $i$ 个小球上写有一个整数 $a_i$。

小蓝一共购买了 $k$ 次抽奖机会。在每次抽奖中，他可以从当前剩余的小球里选择一个拿走，但只有满足以下条件的小球才可以被拿走：

设该小球在当前剩余小球中从左到右排在第 $i$ 个，记：

• $L_i$ 为该小球左侧剩余的小球个数；
• $R_i$ 为该小球右侧剩余的小球个数。

那么该小球必须同时满足：

• $R_i > 0$；
• $L_i$ 是 $R_i$ 的整数倍（特别地，$0$ 视为任意非零整数的整数倍）。

每次拿走一个小球后，剩余小球会重新按原有相对顺序排成一排。

小蓝最多可以进行 $k$ 次抽奖，也可以少于 $k$ 次。请你计算，他最多能拿走的小球上整数之和是多少。

输入格式

输入共两行。

第一行包含两个正整数 $n, k$。

第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示每个小球上的整数。

输出格式

输出一行，一个整数，表示最多 $k$ 次抽奖后，小蓝能够获得的最大整数之和。

7 2
2 8 2 4 2 6 3

10

解释 #1

一种可行方案是：

• 第一次拿走当前第 $4$ 个小球，得到 $4$；
• 剩余小球变为 $2, 8, 2, 6, 3$；
• 第二次拿走当前第 $5$ 个小球，得到 $6$。

总和为 $4 + 6 = 10$。

另一种可行方案是：

• 第一次拿走当前第 $1$ 个小球，得到 $2$；
• 剩余小球变为 $8, 2, 4, 2, 6, 3$；
• 第二次再拿走当前第 $1$ 个小球，得到 $8$。

总和同样为 $2 + 8 = 10$。

数据范围

对于 $100\%$ 的数据，保证 $1 \le k \le n \le 20$，$1 \le a_i \le 100$。