섬 건너가기

헥토르와 친구들은 근처 호수 한가운데에 있는 섬으로 소풍을 가기로 했습니다. 섬으로 건너가려면 작은 나룻배 대여 업체의 배를 이용해야 합니다.

이 업체는 두 종류의 배를 빌려줍니다.

• 1종 배는 한 번에 최대 두 명까지 태울 수 있으며, 두 사람의 몸무게 합이 $M$ kg을 넘으면 안 됩니다. 1종 배를 한 번 이용하는 비용은 $A$입니다.
• 2종 배는 더 튼튼하지만 좌석이 하나뿐이라 한 번에 한 명만 태울 수 있습니다. 몸무게에 상관없이 아무나 한 명을 태울 수 있으며, 한 번 이용하는 비용은 $B$입니다.

각 참가자의 몸무게가 주어질 때, 모든 참가자를 섬으로 실어 나르는 데 드는 최소 총비용을 구하세요.

첫째 줄에 테스트 세트의 개수를 나타내는 자연수 $Z$ ($1 \le Z \le 10$)가 주어집니다. 이어서 각 테스트 세트가 차례로 주어집니다.

각 테스트 세트의 첫째 줄에는 공백으로 구분된 네 자연수 $N$, $A$, $B$, $M$ ($1 \le N, M \le 10^6$, $1 \le A, B \le 1000$)이 주어집니다. 각각 소풍 참가자 수, 1종 배를 한 번 이용하는 비용, 2종 배를 한 번 이용하는 비용, 1종 배에 탄 승객들의 몸무게 합의 최댓값을 뜻합니다.

각 테스트 세트의 둘째 줄에는 공백으로 구분된 $N$개의 자연수 $w_i$ ($1 \le w_i \le 10^6$)가 주어지며, 각 참가자의 몸무게를 나타냅니다.

각 테스트 세트마다 모든 참가자를 섬으로 실어 나르는 최소 총비용을 한 줄에 하나씩 출력하세요.