暂无测试数据。

Description

下课了，老师离开了教室， $\text{Scarral}$ 决定修改黑板上的式子，这样当老师下节课算的时候就会非常麻烦（恶搞qwq

原来黑板上有一个由 $n$ 个数字成的序列 $A$ ，定义了一个函数如下：
$f(x) = \sum_{i=1}^{x-1}\sum_{j=i+1}^x\gcd(A_i,A_j)$

由于下课的时间比较短， $\text{Scarral}$ 只能将其中至多 $k$ 个数改为 $[L,R]$ 区间内的任一整数。为了使老师算得最麻烦， $\text{Scarral}$ 决定最大化 $f(n)$ ，现在 $\text{Scarral}$ 想知道修改后 $f(n)$ 的最大值是多少。

Input

第 $1$ 行 $4$ 个正整数，分别表示 $n$ ， $k$ ， $L$ 和 $R$ 。
第 $2$ 行 $n$ 个正整数，第 $i$ 个正整数表示 $A_i$ 。

经过至多 $k$ 次修改后的最大值。

待填坑

待填坑

本题共 $10$ 个测试点。

测试点	$n\le$	$k\le$	$L,R\le$
$1$ ~ $5$	$100$	$10$	$1000$
$6$ ~ $10$	$10^5$	$40$	$10^9$

在下列比赛中: