Maximum Divisor Sum from Prime Power Partition

You are given a sequence (a_1,a_2,\ldots,a_n) of positive integers (each (\ge 2)). You need to choose a contiguous subarray (i.e. an interval) ([l,r]) such that (\max{a_l,\ldots,a_r} - \min{a_l,\ldots,a_r} \le k). Let the product of the numbers in the chosen subarray be (P=\prod_{i=l}^{r}a_i). Then, you must represent (P) as a product of (m) distinct numbers, i.e. find (m) (a positive integer) and (m) distinct integers (p_1,p_2,\ldots,p_m) satisfying

[ \prod_{i=l}^{r}a_i = \prod_{j=1}^{m}p_j, ]

with the restriction that each (p_j) is a positive integer power of a prime (i.e. (p_j = q^{e}) for some prime (q) and integer (e \ge 1)).

For any representation satisfying the condition, define the score as the sum of the number of divisors of each (p_j). Note that a number of the form (q^e) has (e+1) divisors. Moreover, note that if a prime (q) appears in (P) with exponent (E), you are free to partition (E) into a sum of (t) distinct positive integers (e_1,e_2,\ldots,e_t) (where (t\ge 1) and (e_1+e_2+\cdots+e_t=E)) so that the corresponding contribution to the score is ((e_1+1)+(e_2+1)+\cdots+(e_t+1)=E+t). It is always optimal to choose the maximum possible (t) subject to the constraint that the (e_i)’s are distinct. In fact, the maximum number (t) for a given (E) is the largest integer satisfying

[ \frac{t(t+1)}{2} \le E. ]

Thus, if a prime (q) appears in (P) with exponent (E), its optimal contribution to the overall score is

[ E + \Big\lfloor\frac{-1+\sqrt{1+8E}}{2}\Big\rfloor. ]

Your task is to choose an interval ([l,r]) (satisfying the difference condition) so that the overall score (i.e. the sum over all primes in the factorization of (P) of (E + \lfloor(-1+\sqrt{1+8E})/2\rfloor)) is maximized. Output the maximum possible score.

Input Format:

• The first line contains two integers \(n\) and \(k\) (where \(n\) is the length of the sequence and \(k\) is the maximum allowed difference between the maximum and minimum in the interval).
• The second line contains \(n\) integers \(a_1,a_2,\ldots,a_n\), each at least 2.

Output Format:

• Output a single integer which is the maximum possible score.

Note: It is guaranteed that there is at least one valid interval (i.e. a contiguous subarray satisfying the condition).

inputFormat

The first line contains two space-separated integers \(n\) and \(k\). The second line contains \(n\) space-separated integers \(a_1,a_2,\ldots,a_n\). \(2 \le a_i \le 10^5\) (assumed) and \(1 \le n \le 10^5\) (assumed).

outputFormat

A single integer representing the maximum achievable score.

sample

3 2
2 3 4

7