Top 2000

한 라디오 방송국이 카운트다운 차트를 방송한다. 차트는 정해진 순서대로 재생해야 하는 싱글(곡)들의 목록으로, 인기가 가장 낮은 곡부터 가장 높은 곡까지 순서가 고정되어 있다. 각 싱글의 길이는 분 단위 정수로 주어진다.

방송은 길이가 $M$분인 동일한 블록들로 나뉜다(매시간 광고와 뉴스를 위해 몇 분이 빠지므로 한 블록은 한 시간보다 짧다). 싱글은 순서대로 블록에 배정된다. 각 블록은 목록에서 연속된 구간의 싱글들을 받고, 어떤 싱글도 두 블록에 걸쳐 나뉘지 않으며, 모든 싱글은 정확히 하나의 블록에서 한 번만 재생된다. 블록의 개수는 고정되어 있지 않지만 정수여야 하고, 모든 블록은 완전해야 한다. 즉 블록들이 모든 싱글을 빠짐없이 담아야 한다.

한 블록에 배정된 싱글들의 총 길이가 정확히 $M$분이 되는 경우는 드물다.

• 총 길이가 $M$분을 넘으면 모두 온전히 재생할 수 없어 일부를 잘라내야 한다. 잘라낸 1분마다 $A$의 벌점이 발생한다. 모든 싱글은 최소 1초는 재생되어야 하므로, 어떤 싱글도 완전히 빠지지는 않는다.
• 총 길이가 $M$분보다 짧으면 남는 시간은 DJ의 말로 채운다. 채운 1분마다 $B$의 벌점이 발생한다.

따라서 총 길이가 $L$분인 블록의 벌점은 $L > M$이면 $A \cdot (L - M)$, $L < M$이면 $B \cdot (M - L)$, $L = M$이면 $0$이다.

모든 싱글을 블록들로 배치하여 전체 블록에 대한 벌점의 합이 최소가 되도록 하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다.

• 첫 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다($1 \le N \le 50000$, $15 \le M \le 100$). 각각 싱글의 개수와 한 블록의 길이(분)이다.
• 둘째 줄에 두 정수 $A$와 $B$가 주어진다($1 \le A, B \le 1000$). 각각 잘라낸 음악 1분당 벌점과 DJ가 채운 1분당 벌점이다.
• 셋째 줄에 $N$개의 정수가 주어진다. 재생해야 하는 순서대로 각 싱글의 길이(분)이며, 각 길이 $x$는 $1 \le x \le 20$을 만족한다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 그 차트를 배치할 때 얻을 수 있는 최소 전체 벌점이다.