D. 修改序列(gcd)

D. 修改序列(gcd)

暂无测试数据。

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

「scoj2020」Round 1

未参加
状态
已结束
规则
ACM/ICPC
题目
4
开始于
2021-07-01 08:30
结束于
2021-07-02 22:30
持续时间
38.0 小时
主持人
参赛人数
2