题目背景

虽然 luanmenglei 已经是成熟的高中生了，但每次提起 luanmenglei 八年级的女朋友时，luanmenglei 都会沉浸在美好的回忆中，不可自拔。

题目描述

给定 $n, k$ 和序列 $\{a_n\}$，你同时有一个临时变量 $x$，你可以进行以下操作若干次（也可以是 $0$ 次），一次操作的流程是：

1. 选定一个区间 $[l,r]$，$\forall i\in[l,r]$，$x\leftarrow \gcd(a_l,a_{l+1},\cdots,a_r)$。
2. $\forall i\in[l,r]$，$a_i\leftarrow x$。

简而言之，你每次可以选定一个区间并将其中每个数变成这个区间的 $\gcd$。

一次操作的代价是 $r-l+1+k$，现在你希望把这个序列的每个数都变成相等的，求最小代价和。

---

如果您不了解 $\gcd$ 或者多元 $\gcd$ 的含义，可以参照如下定义：

• $\gcd(a_1,a_2,\dots, a_k)$ 表示 $a_1,a_2,\dots, a_k$ 的最大公约数，即最大的能同时整除 $a_1,a_2,\dots, a_k$ 的正整数。

输入格式

第一行两个非负整数 $n,k$。

第二行 $n$ 个数，表示 $\{a_n\}$。

输出格式

一行一个数，表示答案。

10 3
2 2 2 1 2 2 2 1 2 2 

13

10 0
2 2 2 1 2 2 2 1 2 3 

9

11 0
2 2 2 1 2 2 2 1 1 3 3 

10

提示

【样例 1 解释】

操作一次，选择区间 $[1,10]$。

【样例 4】

见附加文件中的 old/old4.in 与 old/old4.out。

该样例满足测试点 $9\sim 12$ 的限制。

【样例 5】

见附加文件中的 old/old5.in 与 old/old5.out。

该样例满足测试点 $13\sim 16$ 的限制。

【数据范围与提示】

对于所有数据，保证 $1\leq n\leq 4\times 10^6$，$0\leq k\leq 10^9$，$1\leq a_i\leq 10^9$。

每个测试点的具体限制见下表：

测试点编号	$n\leq$	$k,a_i\leq$	特殊性质
$1$	$10^6$	$10^9$	所有数都相等
$2\sim 4$	$4$		无
$5\sim 8$	$100$
$9\sim 12$	$1000$
$13\sim 16$	$10^6$
$17\sim 20$	$4\times 10^6$

本题的读入量较大，请选择较快的读入方式，下面提供一种读入策略：

请在代码的开头加入此行：std::ios::sync_with_stdio(false);std::cin.tie(0);。

请注意，加入本行后 cin/cout 的效率将大幅提高，保证其能在 250 ms 内读入所有数据，但使用后你仅能使用 cin/cout 流读入数据。