Problem Description

Sashka has a sequence $A_0,A_1,\dots,A_{N-1}$ of $N$ positive integers, a positive integer $K$, and an arithmetic progression (A sequence $P_0, P_1,\dots$ is an arithmetic progression if and only if $P_i = D + P_{i-1}$ for all $i \geq 1$ for some constant $D$.), defined by its first element $S$ and the difference between its consecutive elements $D$, which are both positive integers.

She is interested in the subsequences (A subsequence of a sequence is obtained by removing zero or more elements from it, without changing the order of the remaining elements.) of length $K$ of $A$ denoted as $B_0, B_1,\dots,B_{K-1}$.

Write a program $\texttt{arithmetic\_progression}$ that calculates the minimal sum of respective multiplications of such a subsequence with the first $K$ entries of the arithmetic progression, meaning the following sum is minimized:

Implementation details

You should implement the function $\verb|solve|$:

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

• $A$: vector, containing $A_0,A_1, \dots, A_{N-1}$
• $K$: the length of the subsequence
• $S$: the first entry of the arithmetic progression
• $D$: the difference of the arithmetic progression

Your function should return the minimal possible sum of the described type. As it may be too large, your function should return the variable of the non-standard $\texttt{\_\_int128}$ type for $128$ bit integers. The header file $\texttt{arithmetic\_progression.h}$ contains overloaded definitions for the $\texttt{<<}$ and $\texttt{>>}$ operators, allowing the use of $\verb|std::cin|$, $\verb|std::cout|$ and $\verb|std::cerr|$ for $\verb|__int128|$ variables.

Input Format

Input format:

• line 1: $N$ $K$ $S$ $D$;
• line 2: $A_0\ A_1\ A_2\ ...\ A_{N-1}$.

Output Format

Output format:

• line 1: one integer, equal to the answer returned by \verb|solve|

3 2 1 1
5 1 4

7

3 2 6 1
5 1 4

34

6 4 4 6
18 12 8 14 19 11

562

Hint

Comment 1

The arithmetic progression is $\{1,2\}$. We choose $B=\{5,1\}$, and we get the optimal result: $5 \times 1 + 1 \times 2 = 7$

Comment 2

The arithmetic progression is $\{6,7\}$. We choose $B=\{1,4\}$, and we get the optimal result: $1 \times 6 + 4 \times 7 = 34$

Comment 3

The arithmetic progression is $\{4,10,16,22\}$. We choose $B=\{18,12,8,11\}$, and we get the optimal result: $18 \times 4 + 12 \times 10 + 8 \times 16 + 11 \times 22 = 562$

Constraints

• $1 \leq K \leq N \leq 300\ 000$
• $1 \leq D \leq 10^9$
• $1 \leq A_i, S \leq 10^{15}$

Subtasks

The points for a given subtask are obtained only if all the tests for it and the required subtasks are successfully passed.