暂无测试数据。

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\)。

---

Output

经过至多 \(k\) 次修改后的最大值。

---

Sample

Sample input

待填坑

Sample output

待填坑

---

Hint

本题共 \(10\) 个测试点。

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