E. Monster
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Man, this Genshin boss is so hard. Good thing they have a top-up of $$$6$$$ coins for only $$$ \$4.99$$$. I should be careful and spend no more than I need to, lest my mom catches me...

You are fighting a monster with $$$z$$$ health using a weapon with $$$d$$$ damage. Initially, $$$d=0$$$. You can perform the following operations.

  • Increase $$$d$$$ — the damage of your weapon by $$$1$$$, costing $$$x$$$ coins.
  • Attack the monster, dealing $$$d$$$ damage and costing $$$y$$$ coins.

You cannot perform the first operation for more than $$$k$$$ times in a row.

Find the minimum number of coins needed to defeat the monster by dealing at least $$$z$$$ damage.

Input

The first line contains a single integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases.

The only line of each test case contains 4 integers $$$x$$$, $$$y$$$, $$$z$$$, and $$$k$$$ ($$$1\leq x, y, z, k\leq 10^8$$$) — the first operation's cost, the second operation's cost, the monster's health, and the limitation on the first operation.

Output

For each test case, output the minimum number of coins needed to defeat the monster.

Example
Input
4
2 3 5 5
10 20 40 5
1 60 100 10
60 1 100 10
Output
12
190
280
160
Note

In the first test case, $$$x = 2$$$, $$$y = 3$$$, $$$z = 5$$$, and $$$k = 5$$$. Here's a strategy that achieves the lowest possible cost of $$$12$$$ coins:

  • Increase damage by $$$1$$$, costing $$$2$$$ coins.
  • Increase damage by $$$1$$$, costing $$$2$$$ coins.
  • Increase damage by $$$1$$$, costing $$$2$$$ coins.
  • Attack the monster, dealing $$$3$$$ damage, costing $$$3$$$ coins.
  • Attack the monster, dealing $$$3$$$ damage, costing $$$3$$$ coins.

You deal a total of $$$3 + 3 = 6$$$ damage, defeating the monster who has $$$5$$$ health. The total number of coins you use is $$$2 + 2 + 2 + 3 + 3 = 12$$$ coins.

In the second test case, $$$x = 10$$$, $$$y = 20$$$, $$$z = 40$$$, and $$$k = 5$$$. Here's a strategy that achieves the lowest possible cost of $$$190$$$ coins:

  • Increase damage by $$$5$$$, costing $$$5\cdot x$$$ = $$$50$$$ coins.
  • Attack the monster once, dealing $$$5$$$ damage, costing $$$20$$$ coins.
  • Increase damage by $$$2$$$, costing $$$2\cdot x$$$ = $$$20$$$ coins.
  • Attack the monster $$$5$$$ times, dealing $$$5\cdot 7 = 35$$$ damage, costing $$$5\cdot y$$$ = $$$100$$$ coins.

You deal a total of $$$5 + 35 = 40$$$ damage, defeating the monster who has exactly $$$40$$$ health. The total number of coins you use is $$$50 + 20 + 20 + 100 = 190$$$ coins.