All Submissions


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

Time Limit: 4 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0