# Unicorns & Dragons

**The Problem**

Once upon a time, there lived D dragons and U unicorns in a mystical land which was separated from the rest of the world by a magical river. The dragons and unicorns wanted to cross the river, using a magical ship that could carry a maximum of K creatures at a time.

However if the dragons ever outnumbered the unicorns on either side of the river, or in the ship, the dragons would eat the unicorns. The ship needed X amount of fuel for each trip from one side of the river to the other and there should be at least one dragon or unicorn to row the ship. Find the minimum amount of fuel needed to get all the dragons and unicorns safely across the other side.

Note that when the ship reached shore, all the creatures in the ship temporarily disembarked to determine whether the dragons outnumbered the unicorns.

**Input**

First line contains t, the number of test cases.

Each test case contains four integers U, D, K and X, separated by space.

**Output**

For each testcase, you have to print the minimum amount of fuel needed.

If it is not posssible to get all the creatures safely across the river, print -1.

**Constraints**

- 2<= D, U, K<=50
- D <= U
- 1<= X <= 100

**Sample Input**

```
```

3

3 3 2 10

5 5 2 90

35 18 8 10

**Sample Output**

```
```

110

-1

150

**Explanation**

CASE #1:

Two dragons cross; one dragon comes back : 2 crossings

Two dragons cross; one dragon comes back : 2 crossings

Two unicorns cross; one unicorn and one dragon comes back : 2 crossings

Two unicorns cross; one dragon comes back : 2 crossings

Two dragons cross; one dragon comes back : 2 crossings

Two dragons cross : 1 crossing

Total number of crossings is 2+2+2+2+2+1 = 11

Amount of fuel needed = 11*10 = 110

*Problem Setter : Rohan Laishram*

*Problem Tester : Shikhar Sharad*

**Languages:**Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Ruby,Text