Under construction

Still being built. Things may change

The Crossing

Interview

Time limit2sMemory limit128 MB

Summary
Pair at most two riders per shared boat within the weight limit or send each alone, and find the lowest total fare.
Level

Medium5 of 10

Topics
Greedy, Sorting, Two pointers
Solved
No attempts yet

Problem

Hektor and his friends decided to take a trip to an island in the middle of a nearby lake. To cross to the island, they must hire boats from a small ferry service.

The service rents out two kinds of boats:

  • A first-kind boat carries at most two passengers, and the sum of their weights must not exceed MM kg. Each single use of such a boat costs AA.
  • A second-kind boat is sturdier but has only one passenger seat, so it carries exactly one person (of any weight) per trip. Each single use costs BB.

Given the weight of every participant, compute the minimum total cost of ferrying all of them to the island.

Input

The first line contains a natural number ZZ (1≤Z≤101 \le Z \le 10), the number of test sets. The test sets follow, one after another.

The first line of each test set contains four space-separated natural numbers NN, AA, BB, MM (1≤N,M≤1061 \le N, M \le 10^6, 1≤A,B≤10001 \le A, B \le 1000): the number of participants, the cost of one use of a first-kind boat, the cost of one use of a second-kind boat, and the maximum combined weight of the passengers in a first-kind boat, respectively.

The second line of each test set contains NN space-separated natural numbers wiw_i (1≤wi≤1061 \le w_i \le 10^6), the weights of the participants.

Output

For each test set, print on its own line the minimum total cost of ferrying all participants to the island.

Examples1

  1. Example 1

    Input
    2
3 3 2 100
55 80 45
3 3 2 100
55 80 50
    Expected output
    5
6