Sashka has a sequence of positive integers, a positive integer , and an arithmetic progression (A sequence is an arithmetic progression if and only if for all for some constant .), defined by its first element and the difference between its consecutive elements , 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 of denoted as .
Write a program that calculates the minimal sum of respective multiplications of such a subsequence with the first entries of the arithmetic progression, meaning the following sum is minimized:
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 type for bit integers. The header file contains overloaded definitions for the and operators, allowing the use of , and for variables.
输入格式
Input format:
line 1: ;
line 2: .
输出格式
Output format:
line 1: one integer, equal to the answer returned by \verb|solve|
样例
样例输入 1
3 2 1 1
5 1 4
样例输出 1
7
样例输入 2
3 2 6 1
5 1 4
样例输出 2
34
样例输入 3
6 4 4 6
18 12 8 14 19 11
样例输出 3
562
数据范围与提示
Comment 1
The arithmetic progression is . We choose , and we get the optimal result:
Comment 2
The arithmetic progression is . We choose , and we get the optimal result:
Comment 3
The arithmetic progression is . We choose , and we get the optimal result:
Constraints
Subtasks
Subtask
Points
Required subtasks
Other constraints
The sample tests.
is obtained by uniformly shuffling a sequence that is chosen by the author for the given test.
The points for a given subtask are obtained only if all the tests for it and the required subtasks are successfully passed.
