arithmetic_progression

Sashka has a sequence $A_0, A_1, ..., A_{N-1}$ of $N$ positive integers, a positive integer $K$, and an arithmetic progression, 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 of length $K$ of $A$ denoted as $B_0, B_1, ..., B_{K-1}$. Write a program 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:

A sequence $P_0, P_1, ...$ is an arithmetic progression if and only if $P_i = D + P_{i-1}$ for all $i \geq 1$ for some constant $D$.

A subsequence of a sequence is obtained by removing zero or more elements from it, without changing the order of the remaining elements.

Implementation details

You should implement the function solve:

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

• $A$: vector, containing $A_0, A_1, ..., 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 __int128 type for 128 bit integers. The header file arithmetic_progression.h contains overloaded definitions for the << and >> operators, allowing the use of std::cin, std::cout, and std::cerr, for __int128 variables.

Constraints and clarifications

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

Local testing

Input format:

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

Output format:

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

Example 1

stdin

3 2 1 1
5 1 4

stdout

7

Explanation

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

Example 2

stdin

3 2 6 1
5 1 4

stdout

34

Explanation

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

Example 3

stdin

6 4 4 6
18 12 8 14 19 11

stdout

562

Explanation

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