시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 0 0 0 0.000%

문제

Hektor z przyjaciółmi postanowił zorganizować wycieczkę na wyspę leżącą na środku pobliskiego jeziora. Aby dostać się na wyspę, należy skorzystać z usług firmy transportowej Łódeczka.

Łódeczka oferuje przewóz dwoma rodzajami łódek:

  • Łódki pierwszego rodzaju pozwalają przewieźć maksymalnie dwóch pasażerów, przy czym ich łączna waga nie może przekraczać M kg. Jednorazowe skorzystanie z takiej łodzi kosztuje A zł.
  • Łódku drugiego rodzaju mają większą wyporność, ale tylko jedno miejsce pasażerskie. Jednorazowo można taką łódką przewieźć dowolną (jedną) osobę za cenę B zł.

Znając wagi poszczególnych uczestników wyprawy, oblicz minimalny łączny koszt transportu na wyspę wszystkich uczestników.

입력

W pierwszej linii wejścia znajduje się liczba naturalna Z ( 1 <= Z <= 10 ) opisująca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

Pierwsza linia opisu zestawu testowego zawiera cztery oddzielone spacjami liczby naturalne NAB, M ( 1 <= N, M <= 1000000, 1 <= A, B <= 1000), oznaczające kolejno: liczbę uczestników wycieczki, koszt jednokrotnego skorzystania z łodzi pierwszego rodzaju, koszt jednokrotnego skorzystania z łodzi drugiego rodzaju oraz maksymalną łączną waga pasażerów łodzi pierwszego rodzaju.

W drugiej linii opisu zestawu znajduje się N oddzielonych spacjami liczb naturalnych wi ( 1 <= wi <= 1000000) oznaczających wagi kolejnych uczestników wycieczki.

출력

Dla każdego testu należy w osobnej linii wypisać minimalny łączny koszt przeprawy na wyspę wszystkich uczestników.

예제 입력 1

2
3 3 2 100
55 80 45
3 3 2 100
55 80 50

예제 출력 1

5
6

출처

Contest > Spot > HotSpot 2011 2-2번