题目类型说明

这是一道 提交函数题。

你需要实现如下函数：

__int128 solve(std::vector<long long> A, int K, long long S, int D);

其中：

• A：长度为 N 的正整数序列；
• K：需要选出的子序列长度；
• S：等差数列首项；
• D：等差数列公差。

函数需要返回最小可能的加权和。

特别地，答案可能非常大，因此返回值类型为 __int128。 原题提供的头文件中已经重载了 << 与 >>，可以直接使用 std::cin、std::cout、std::cerr 处理 __int128。

---

题目描述

给定一个长度为 N 的正整数序列 A_0, A_1, ..., A_{N-1}，以及一个无限长的正整数等差数列：

$$S,\ S + D,\ S + 2D,\ \dots$$

其中首项为 S，公差为 D。

现在，你需要从序列 A 中选出一个 长度恰好为 K 的子序列。 这里的“子序列”指的是：保持原有相对顺序，但不要求连续。

设选出的子序列为：

$$B_0, B_1, \dots, B_{K-1}$$

你的目标是最小化下式：

$$\sum_{i=0}^{K-1} B_i \times (S + iD)$$

请你求出这个最小值。

---

本地评测说明

输入格式

第一行输入四个整数 N, K, S, D。 第二行输入 N 个整数 A_0, A_1, A_2, ..., A_{N-1}。

输出格式

输出一行一个整数，表示 solve 函数返回的答案。

---

数据范围

• 1 \le K \le N \le 300000
• 1 \le D \le 10^9
• 1 \le A_i, S \le 10^{15}

---

子任务

子任务	分值	前置子任务	N 范围	特殊限制
0		-		样例
1	5	0	<= 20	无
2	6	0-1	<= 500
3		0-2	<= 3000
4	1	-	<= 100000	K = N
5	4	4		K >= N - 1
6		4-5		K >= N - 2
7	5	-		A 由出题人选定的某个序列随机均匀打乱得到
8		0-7		无
9	67	0-8	<= 300000

只有当某个子任务及其要求的前置子任务全部通过时，才能获得该子任务的分数。

---

样例 1

输入

3 2 1 1
5 1 4

输出

7

说明

等差数列前两项为 {1, 2}。

选择子序列 {5, 1}，得到：

$$5 \times 1 + 1 \times 2 = 7$$

这是最优解。

---

样例 2

输入

3 2 6 1
5 1 4

输出

34

说明

等差数列前两项为 {6, 7}。

选择子序列 {1, 4}，得到：

$$1 \times 6 + 4 \times 7 = 34$$

这是最优解。

---

样例 3

输入

6 4 4 6
18 12 8 14 19 11

输出

562

说明

等差数列前四项为 {4, 10, 16, 22}。

选择子序列 {18, 12, 8, 11}，得到：

$$18 \times 4 + 12 \times 10 + 8 \times 16 + 11 \times 22 = 562$$

这是最优解。