Top 2000

A radio station broadcasts a countdown chart: a fixed list of singles that must be played in a given order, from the least popular to the most popular. Each single has a known length in whole minutes.

The broadcast is divided into equal blocks of $M$ minutes (every hour a few minutes are reserved for commercials and news, so a block is shorter than a full hour). The singles are handed to the blocks in order: each block receives a contiguous run of singles from the list, no single is split across two blocks, and every single is played in exactly one block. The number of blocks is not fixed, but it must be a whole number, and every block must be complete — together the blocks must contain all of the singles.

The singles assigned to a block rarely add up to exactly $M$ minutes.

• If their total length exceeds $M$, they cannot all be played in full, so some parts must be cut. Cutting costs a penalty of $A$ for every minute removed. At least one second of every single must still be played, so a single is never dropped completely.
• If their total length is less than $M$, the leftover time is filled by a DJ talking, which costs a penalty of $B$ for every minute filled.

Thus, for a block whose singles have total length $L$ minutes, the penalty is $A \cdot (L - M)$ when $L > M$, $B \cdot (M - L)$ when $L < M$, and $0$ when $L = M$.

Schedule all the singles into blocks so that the total penalty, summed over every block, is as small as possible.

The first line contains a single integer $T$: the number of test cases. Each test case consists of three lines.

• A line with two integers $N$ and $M$ ($1 \le N \le 50000$, $15 \le M \le 100$): the number of singles and the number of minutes in one block.
• A line with two integers $A$ and $B$ ($1 \le A, B \le 1000$): the penalty per minute of music that is cut, and the penalty per minute filled by the DJ.
• A line with $N$ integers giving the lengths (in minutes) of the singles, in the order they must be played. Each length $x$ satisfies $1 \le x \le 20$.

For each test case, print a single line with one integer: the minimum possible total penalty for scheduling that chart.