#P2163. 2024.10.10-XC-第3题-数组分割

2024.10.10-XC-第3题-数组分割

题目内容

塔塔拿到了一个长度为nn的数组aia_i，请你在不改变元素原有顺序的情况下将其分成恰好mm个非空子数组，

对mm个子数组分别计算数组内所有元素的gcdgcd值，请问这mm个非空子数组内部的gcdgcd值之和的最大值是多

最大公约数(gcdgcd) 指能够整除多个非零整数的最大正整数。

分割指的是将数组分成若干个连续的子数组，每个元素都必须分到一个子数组中，且子数组之间不能有

重叠部分，子数组的并集要能够完全覆盖整个数组。

输入描述

第一行两个整数表示n,mn,m。

第二行n个整数表示数组aia_i。 1≤m≤n≤400,1≤a≤1000001≤m≤n≤400,1≤a≤100000。

输出描述

输出一行一个整数表示答案.

样例1

输入

4 2
5 6 3 2

输出

6

知识点:*****

查看知识点以及同类型题目

Statistics