Problem Background

Although luanmenglei is already a mature high school student, every time he mentions his eighth-grade girlfriend, luanmenglei gets lost in beautiful memories, unable to extricate himself.

Problem Description

Given \( n, k \) and the sequence \( \{a_n\} \), you have a temporary variable \( x \). You can perform the following operations any number of times (including zero times). The process of one operation is:
1. Select an interval \([l, r]\), for all \( i \in [l, r] \), \( x \leftarrow \gcd(a_l, a_{l+1}, \cdots, a_r) \).
2. For all \( i \in [l, r] \), \( a_i \leftarrow x \).

In summary, you can select an interval and set each number in the interval to the \(\gcd\) of that interval.

The cost of one operation is \( r - l + 1 + k \). You want to make all numbers in the sequence equal, and you need to find the minimum total cost.

If you are unfamiliar with \(\gcd\) or multivariate \(\gcd\), refer to the following definition:
- \(\gcd(a_1, a_2, \dots, a_k)\) represents the greatest common divisor of \( a_1, a_2, \dots, a_k \), which is the largest positive integer that divides \( a_1, a_2, \dots, a_k \) simultaneously.

Input Format

The first line contains two non-negative integers \( n, k \).

The second line contains \( n \) numbers, representing the sequence \( \{a_n\} \).

Output Format

Output a single number, which is the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

13

Sample Input #2

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

Sample Output #2

9

Sample Input #3

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

Sample Output #3

10

Notes

Sample 1 Explanation

Perform one operation, selecting the interval \([1, 10]\).

Sample 4

See the additional files old/old4.in and old/old4.out.

This sample meets the constraints of test points \(9 \sim 12\).

Sample 5

See the additional files old/old5.in and old/old5.out.

This sample meets the constraints of test points \(13 \sim 16\).

Data Range and Hints

For all data, it is guaranteed that \( 1 \leq n \leq 4 \times 10^6 \), \( 0 \leq k \leq 10^9 \), \( 1 \leq a_i \leq 10^9 \).

The specific constraints for each test point are as follows:

The input for this problem is large, so please choose a fast input method. Here is a suggested input strategy:

Add this line at the beginning of your code: std::ios::sync_with_stdio(false); std::cin.tie(0);.

Please note that adding this line will significantly increase the efficiency of cin/cout, ensuring that all data can be read within 250 ms. However, after using this, you can only use cin/cout for input.

见题面 Input 部分

见题面 Output 部分