The famous store "Second Food" sells groceries only two days a month. And the prices in each of days differ. You wanted to buy $n$ kilos of potatoes for a month. You know that on the first day of the month $1$ kilo of potatoes costs $a$ coins, and on the second day $b$ coins. In "Second Food" you can buy any integer kilograms of potatoes.

Fortunately, "Second Food" has announced a promotion for potatoes, which is valid only on the first day of the month — for each $m$ kilos of potatoes you buy, you get $1$ kilo as a gift! In other words, you can get $m + 1$ kilograms by paying for $m$ kilograms.

Find the minimum number of coins that you have to spend to buy at least $n$ kilos of potatoes.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10000$). Description of the test cases follows.

The first line of each test case contains two integers $a$ and $b$ $(1 \leq a, b \leq 10^9)$ — the prices of $1$ kilo of potatoes on the first and second days, respectively.

The second line contains two integers $n$ and $m$ $(1 \leq n, m \leq 10^9)$ — the required amount of potatoes to buy and the amount of potatoes to use the promotion.


-----Output-----

For each test case print one integer — the minimum number of coins that you have to pay to buy at least $n$ kilos of potatoes.


-----Examples-----

Input
5
5 4
3 1
5 4
3 2
3 4
3 5
20 15
10 2
1000000000 900000000
1000000000 8
Output
9
10
9
135
888888888900000000


-----Note-----

In the first test case, on the first day you buy $1$ kilo and get $1$ more for a promotion. On the second day, you can buy $1$ kilo of potatoes. Thus, you will spend $5+4=9$ coins in total.

In the second test case, on the first day you buy $2$ kilo and get another $1$ more for a promotion. This way you will spend $2 \cdot 5 = 10$ coins.

Difficulty: EASY
Tags: Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys
input = lambda : sys.stdin.readline().rstrip()
T = int(input())
res = []
for _ in range(T):
	(day1, day2) = map(int, input().split())
	(need, firstadd) = map(int, input().split())
	if need < firstadd:
		if day1 < day2:
			res.append(day1 * need)
		else:
			res.append(day2 * need)
	elif firstadd * day1 < (firstadd + 1) * day2:
		fv = need // (firstadd + 1) * (firstadd * day1)
		f = need // (firstadd + 1) * (firstadd + 1)
		if day1 < day2:
			res.append(fv + (need - f) * day1)
		else:
			res.append(fv + day2 * (need - f))
	else:
		res.append(day2 * need)
print('\n'.join(map(str, res)))


import sys
input = sys.stdin.readline

def solve():
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	if m >= n:
		print(min(n * a, n * b))
	elif a * m >= b * (m + 1):
		print(n * b)
	else:
		k = n // (m + 1)
		r = n % (m + 1)
		print(k * m * a + r * min(a, b))
t = int(input())
for _ in range(t):
	solve()


import sys, math, cmath, time
from bisect import bisect_left
start_time = time.time()

def solve():
	(a, b) = map(int, inps())
	(n, m) = map(int, inps())
	if a <= b:
		k = n // (m + 1) * m
		print(k * a + (n - k - n // (m + 1)) * a)
		return
	if b - (a - b) * m > 0:
		k = n // (m + 1) * m
		left = n - k - n // (m + 1)
		print(k * a + left * b)
		return
	else:
		print(n * b)

def main():
	testcases = 1
	testcases = inp()
	for each_testcase in range(testcases):
		solve()

def inp():
	return int(input())

def inps():
	return input().split()
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


import sys
sys_input = sys.stdin.readline
sys_print = sys.stdout.write

def testcase():
	(a, b) = map(int, sys_input().split())
	(n, m) = map(int, sys_input().split())
	n_group = n // (m + 1)
	ng = n_group * (m + 1)
	pg = n_group * m * a
	first = min(pg + a * (n - ng), (ng + 1) * a * m)
	second = pg + b * (n - ng)
	third = n * b
	print(min(first, second, third))
t = int(sys_input())
for _ in range(t):
	testcase()


import sys

def solve():
	inp = sys.stdin.readline
	(a, b) = map(int, inp().split())
	(n, m) = map(int, inp().split())
	u = n * b
	v = (n // (m + 1) * m + n % (m + 1)) * a
	w = n // (m + 1) * m * a + n % (m + 1) * b
	print(min(u, v, w))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	(d1, d2) = (0, 0)
	d2 = n * b
	if n >= m:
		val = n // (m + 1)
		rem = n - val * (m + 1)
		print(min(min(a * val * m + b * rem, b * n), a * val * m + a * rem))
	else:
		print(min(n * a, n * b))


def solve(a, b, n, m):
	res = 0
	if n > m and a * m < b * (m + 1):
		z = n // (m + 1)
		n -= z * (m + 1)
		res += z * m * a
	res += min(a, b) * n
	return res
t = int(input())
ans = []
for ti in range(t):
	(a, b) = [int(x) for x in input().split()]
	(n, m) = [int(x) for x in input().split()]
	ans.append(solve(a, b, n, m))
for a in ans:
	print(a)


import sys
import math
inp = [a.strip() for a in sys.stdin.readlines()]
t = int(inp[0])
line = 0
for case in range(0, t):
	line += 1
	(a, b) = [int(x) for x in inp[line].split()]
	line += 1
	(n, m) = [int(x) for x in inp[line].split()]
	promos = math.floor(n / (m + 1))
	left = n - promos * (m + 1)
	case1 = promos * a * m + a * left
	case2 = promos * a * m + b * left
	case3 = b * n
	print(min(case1, case2, case3))


import sys
from collections import Counter
from collections import defaultdict
input = lambda : sys.stdin.readline().rstrip()
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	ans = 0
	promo_time = int(n // (m + 1))
	remain = n - (m + 1) * promo_time
	if a <= b and n > m:
		ans += a * promo_time * m + a * remain
	if a <= b and n <= m:
		ans += a * n
	if a > b and n <= m:
		ans += b * n
	if a > b and n > m:
		if a * m >= b * (m + 1):
			ans += b * n
		else:
			ans += a * m * promo_time + b * remain
	print(ans)


t = int(input())
otps = []
for i in range(t):
	(a, b) = (int(s) for s in input().split(' '))
	(n, m) = (int(s) for s in input().split(' '))
	if b > a:
		otps.append((n // (m + 1) * m + n % (m + 1)) * a)
	elif m * a < (m + 1) * b:
		otps.append(n // (m + 1) * m * a + n % (m + 1) * b)
	else:
		otps.append(n * b)
for i in range(t):
	print(otps[i])


tests = int(input())
res = []
for test in range(tests):
	(a, b) = [int(x) for x in input().split()]
	(n, m) = [int(x) for x in input().split()]
	q = n // (m + 1)
	r = n - q * (m + 1)
	coins = int(q * min(a * m, b * (m + 1)) + r * min(a, b))
	res.append(coins)
for i in res:
	print(i)


def no_of_coins(a, b, n, m):
	if (m + 1) * b < m * a:
		return n * b
	elif a > b:
		return a * m * (n // (m + 1)) + b * (n % (m + 1))
	else:
		return a * m * (n // (m + 1)) + a * (n % (m + 1))
n = int(input())
l = []
for i in range(n):
	temp1 = input()
	temp2 = input()
	(a, b) = map(int, temp1.split())
	(n, m) = map(int, temp2.split())
	l.append(no_of_coins(a, b, n, m))
for j in range(0, len(l)):
	print(l[j])


t = int(input())
ans = []
for _ in range(t):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	s = min((n // (m + 1) * m + n % (m + 1)) * a, n // (m + 1) * m * a + n % (m + 1) * b, n * b)
	ans.append(s)
print(*ans, sep='\n')


import sys
from os import path

def input():
	return sys.stdin.readline().strip()

def main():
	testcases = int(input())
	for _ in range(testcases):
		(prix_1, prix_2) = str(input()).split()
		(besoin, promo) = str(input()).split()
		prix_1 = int(prix_1)
		prix_2 = int(prix_2)
		besoin = int(besoin)
		promo = int(promo)
		cout = 0
		nb_patates_bonus = promo + 1
		nb_utilisations_bonus = besoin // nb_patates_bonus
		reste = besoin % nb_patates_bonus
		cout = min(nb_utilisations_bonus * (promo * prix_1) + reste * min(prix_1, prix_2), besoin * min(prix_1, prix_2))
		print(cout)

def is_clean(tower):
	i = 0
	while i < len(tower):
		if tower[i] == last:
			return False
		last = tower[i]
		i += 1
	return True
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
main()


import sys

def main():
	try:
		sys.stdin = open('input.txt', 'r')
	except:
		pass
	T = int(sys.stdin.readline().strip())
	while T > 0:
		(a, b) = [int(x) for x in sys.stdin.readline().strip().split(' ')]
		(n, m) = [int(x) for x in sys.stdin.readline().strip().split(' ')]
		x = int(n / (m + 1)) * a * m + min(n % (m + 1) * a, n % (m + 1) * b)
		y = n * b
		print(min(x, y), end='\n')
		T -= 1
main()


import sys
input = sys.stdin.readline
for i in range(int(input())):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	if n <= m:
		print(min(a, b) * n)
	elif a * m >= b * (m + 1):
		print(n * b)
	else:
		x = n // (m + 1)
		s = x * a * m
		if n - (m + 1) * x != 0:
			t = n - (m + 1) * x
			s += min(a, b) * t
		print(s)


t = int(input())
result = []
for i in range(1, t + 1, 1):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	sum = 0
	if a <= b:
		if n <= m:
			sum = n * a
		else:
			k = int((n - n % (m + 1)) / (m + 1))
			sum = (n - k) * a
	elif n <= m:
		sum = n * b
	else:
		k = int((n - n % (m + 1)) / (m + 1))
		sum1 = m * k * a + (n - m * k - k) * b
		sum2 = n * b
		if sum1 <= sum2:
			sum = sum1
		else:
			sum = sum2
	result.append(sum)
for i in range(0, t, 1):
	print(result[i])


k = int(input())
x = []
for i in range(k):
	s = input().split()
	a = int(s[0])
	b = int(s[1])
	l = input().split()
	n = int(l[0])
	m = int(l[1])
	if a <= b:
		if m < n:
			z = n // (m + 1) * a * m + n % (m + 1) * a
		else:
			z = a * n
	elif m < n:
		if m * a < (m + 1) * b:
			z = n // (m + 1) * a * m + n % (m + 1) * b
		else:
			z = b * n
	else:
		z = b * n
	x.append(z)
for i in range(k):
	print(x[i])


n = int(input())
l = []
for i in range(n):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	cos = 0
	if a < b:
		c = a
	else:
		c = b
	if n < m:
		l.append(n * c)
		continue
	else:
		if m * a <= b * (m + 1):
			x = m + 1
			o = n // x
			o1 = n % x
			cos += a * o * m + o1 * c
		else:
			cos += n * c
		l.append(cos)
for i in l:
	print(i)


t = int(input())
ans = []
for i in range(t):
	(a, b) = list(map(int, input().split()))
	(n, m) = list(map(int, input().split()))
	a1 = a * (n // (m + 1)) * m + (a if a < b else b) * (n % (m + 1))
	a2 = n * (a if a < b else b)
	ans.append(min(a1, a2))
for i in ans:
	print(i)


n = int(input())
fprice = []
sprice = []
need = []
sales = []
for i in range(n):
	(fkg, skg) = list(map(int, input().split()))
	(npotato, sale) = list(map(int, input().split()))
	fprice.append(fkg)
	sprice.append(skg)
	need.append(npotato)
	sales.append(sale)
for i in range(n):
	fkg = fprice[i]
	skg = sprice[i]
	nkg = need[i]
	sale = sales[i]
	if sale >= nkg:
		print(min(fkg * nkg, skg * nkg))
		continue
	if sale * fkg >= (sale + 1) * skg:
		print(skg * nkg)
		continue
	ans = nkg // (sale + 1) * sale * fkg
	nkg -= (sale + 1) * (nkg // (sale + 1))
	if fkg > skg:
		ans += nkg * skg
	else:
		ans += nkg * fkg
	print(ans)


import sys
T = int(sys.stdin.readline())
for i in range(T):
	(a, b) = map(int, sys.stdin.readline().split())
	(n, m) = map(int, sys.stdin.readline().split())
	if n < m:
		print(min(a * n, b * n))
	elif n == m:
		print(min(a * n, b * n))
	else:
		one = a * m * (n // (m + 1)) + a * (n % (m + 1))
		two = a * m * (n // (m + 1)) + b * (n % (m + 1))
		three = b * n
		print(min(one, two, three))


t = int(input())
output = []
for i in range(t):
	lst = list(map(int, input().split()))
	a = lst[0]
	b = lst[1]
	lst2 = list(map(int, input().split()))
	n = lst2[0]
	m = lst2[1]
	if m + 1 <= n:
		if a * m <= b * (m + 1):
			if a < b:
				cost = a * m * (n // (m + 1)) + a * (n - (m + 1) * (n // (m + 1)))
			else:
				cost = a * m * (n // (m + 1)) + b * (n - (m + 1) * (n // (m + 1)))
		else:
			cost = b * n
	else:
		cost = min(a * n, b * n)
	output.append(cost)
for i in range(t):
	print(output[i])


import sys

def read(func=int):
	return func(sys.stdin.readline().strip())

def read_array(func=int):
	return list(map(func, read(str).split()))
t = read()
for _ in range(t):
	(a, b) = read_array()
	(n, m) = read_array()
	ans = 0
	while n:
		if n > m:
			vx = n // (m + 1)
			p1 = a * m * vx
			p2 = b * (m + 1) * vx
			ans += min(p1, p2)
			n -= (m + 1) * vx
		else:
			p1 = a * n
			p2 = b * n
			ans += min(p1, p2)
			n = 0
	print(ans)


t = input('')
output = ''
for _ in range(int(t)):
	(a, b) = [int(x) for x in input().split(' ')]
	(n, m) = [int(x) for x in input().split(' ')]
	res = min(n // (m + 1) * m * a + min(n % (m + 1) * a, n % (m + 1) * b), n * b)
	output += str(res) + '\n'
print(output[:len(output) - 1])


k = int(input())
res = []
while k > 0:
	x = input().split(' ')
	(a, b) = (int(x[0]), int(x[1]))
	x = input().split(' ')
	(n, m) = (int(x[0]), int(x[1]))
	cur = 0
	target = n
	times = int(n / (m + 1))
	cur += a * times * m
	n -= (m + 1) * times
	cur += min(n * a, n * b)
	res.append(min(cur, target * a, target * b))
	k -= 1
for x in res:
	print(x)


t = int(input())
ans = []
for _ in range(t):
	(a, b) = list(map(int, input().split()))
	(n, m) = list(map(int, input().split()))
	if n < m + 1:
		ans.append(n * min(a, b))
	elif a * m > b * (m + 1):
		ans.append(n * b)
	else:
		kol = n // (m + 1)
		kg = kol * m + kol
		ans.append(kol * m * a + min(a, b) * (n - kg))
print(*ans, sep='\n')


def calc(a, b, n, m):
	if n >= m:
		payed = n // (m + 1) * (a * m) + n % (m + 1) * min(b, a)
	else:
		payed = n * min(a, b)
	return min(payed, n * b)
l = []
n = int(input())
for i in range(n):
	prices = list(map(int, input().split()))
	kilos = list(map(int, input().split()))
	(a, b) = (prices[0], prices[1])
	(n, m) = (kilos[0], kilos[1])
	l.append(calc(a, b, n, m))
for i in l:
	print(i)


n = int(input())
prices = []
kilos = []
for _ in range(n):
	(a, b) = list(map(int, input().split()))
	prices.append([a, b])
	(n, m) = list(map(int, input().split()))
	kilos.append([n, m])
for i in range(len(prices)):
	(a, b) = prices[i]
	(n, m) = kilos[i]
	if m >= n:
		print(min(a, b) * n)
	else:
		(div, mod) = divmod(n, m + 1)
		print(min(div * a * m + mod * min(a, b), n * min(a, b)))


import math
import string
import random
import sys
from random import randrange
from collections import deque
from collections import defaultdict
from bisect import bisect, bisect_right, bisect_left

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
t = int(data())
while t > 0:
	t -= 1
	(p1, p2) = mdata()
	(n, m) = mdata()
	day2_p = n * p2
	day1_p = n // (m + 1) * m * p1 + n % (m + 1) * min(p1, p2)
	print(min(day1_p, day2_p))


def pri(a, b, n, m):
	h = n // (m + 1)
	punda = min(a, b) * n
	if h == 0:
		print(punda)
	else:
		print(min(punda, a * h * m + (n - h * (m + 1)) * min(a, b)))
t = int(input())
l = []
for i in range(t):
	l1 = [int(x) for x in input().split(' ', 1)]
	l2 = [int(x) for x in input().split(' ', 1)]
	l.append([l1, l2])
for i in l:
	pri(i[0][0], i[0][1], i[1][0], i[1][1])


a = int(input())
b = []
c = []
for i in range(a):
	x = input()
	split = x.split(' ')
	for i in range(len(split)):
		split[i] = int(split[i])
	b.append(split)
	x = input()
	split = x.split(' ')
	for i in range(len(split)):
		split[i] = int(split[i])
	c.append(split)
for i in range(a):
	if c[i][0] <= c[i][1]:
		print(c[i][0] * min(b[i][0], b[i][1]))
	else:
		n = int(c[i][0] / (c[i][1] + 1))
		if b[i][0] * c[i][1] < b[i][1] * (c[i][1] + 1):
			print(n * b[i][0] * c[i][1] + (c[i][0] - n * (c[i][1] + 1)) * min(b[i][0], b[i][1]))
		else:
			print(c[i][0] * min(b[i][0], b[i][1]))


def main():
	t = int(input())
	for _ in range(t):
		res = alg()
		print(res)

def alg():
	(a, b) = input().split()
	(n, m) = input().split()
	a = int(a)
	b = int(b)
	n = int(n)
	m = int(m)
	res = 0
	r = n % (m + 1)
	q = n // (m + 1)
	res = min(q * m * a, q * (m + 1) * b)
	res += min(r * a, r * b)
	return res
main()


t = int(input())
for nouse in range(t):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	ans = 0
	if (m + 1) * b >= a * m:
		tmp = n // (m + 1)
		n -= tmp * (m + 1)
		ans += tmp * a * m
	if a >= b:
		ans += n * b
	else:
		ans += n * a
	print(ans)


I = input
for _ in [0] * int(I()):
	(a, b, n, m) = map(int, (I() + ' ' + I()).split())
	k = m + 1
	print(n // k * min(a * m, b * k) + n % k * min(a, b))


t = int(input())

def mincoin(a, b, n, m):
	if a >= b:
		if a * m - b * (m + 1) >= 0:
			i = 0
			a2 = i * (a * m - b * (m + 1)) + b * n
		else:
			i = n // (m + 1)
			a2 = i * (a * m - b * (m + 1)) + b * n
	else:
		a2 = a * (m * (n // (m + 1))) + a * (n % (m + 1))
	print(a2)
for i in range(t):
	(a, b) = input().split()
	(n, m) = input().split()
	a = int(a)
	b = int(b)
	m = int(m)
	n = int(n)
	mincoin(a, b, n, m)


t = int(input().strip())
for test in range(t):
	(a, b) = map(int, input().strip().split())
	(n, m) = map(int, input().strip().split())
	c1 = n // (m + 1)
	c2 = n % (m + 1)
	ans1 = c1 * a * m + c2 * a
	ans2 = n * b
	ans3 = c1 * a * m + c2 * b
	print(min(ans1, ans2, ans3))


def solve():
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	if m >= n:
		print(min(a, b) * n)
	elif a <= b:
		tot = n
		ans = 0
		k = n // (m + 1)
		ans += a * k * m
		tot -= k * (m + 1)
		ans += a * tot
		print(ans)
	elif a * m <= b * (m + 1):
		tot = n
		ans = 0
		k = n // (m + 1)
		ans += a * k * m
		tot -= k * (m + 1)
		ans += b * tot
		print(ans)
	else:
		print(b * n)
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	res = int(1e+20)
	if a <= b:
		res = min(res, n // (m + 1) * m * a + n % (m + 1) * a)
	else:
		res = min(res, n // (m + 1) * m * a + n % (m + 1) * b, n * b)
	print(res)


iter = int(input())
for _ in range(iter):
	(a, b) = list(map(int, input().split(' ')))
	(n, m) = list(map(int, input().split(' ')))
	if a <= b:
		print(a * m * (n // (m + 1)) + a * (n % (m + 1)))
	elif a * m <= b * (m + 1):
		print(a * m * (n // (m + 1)) + b * (n % (m + 1)))
	else:
		print(b * n)


def exe():
	if m >= n:
		x = min(a, b)
		return n * x
	else:
		x = m * a
		y = (m + 1) * b
		if x < y:
			z = n // (m + 1)
			x = x * z
			j = n % (m + 1)
			u = min(a, b) * j
			return x + u
		else:
			return min(a, b) * n
for i in range(int(input())):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	print(exe())


for i in range(int(input())):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	if b * (m + 1) > a * m:
		print(n // (m + 1) * m * a + n % (m + 1) * min(a, b))
	else:
		print(n * min(a, b))


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	if a <= b:
		print(a * (n - n // (m + 1)))
	elif a * m < b * (m + 1):
		print(a * (m * (n // (m + 1))) + b * (n % (m + 1)))
	else:
		print(b * n)


for _ in range(int(input())):
	(xx, yy) = list(map(int, input().split()))
	(tr, ui) = list(map(int, input().split()))
	ans = yy * tr
	ans_2 = xx * (tr // (ui + 1)) * ui
	ans_2 += min((tr % (ui + 1) * xx, tr % (ui + 1) * yy))
	otp = min(ans_2, ans)
	print(otp)


def solution(a, b, n, m):
	if a <= b:
		if n - 1 >= m:
			return n // (m + 1) * m * a + (n - n // (m + 1) * (m + 1)) * a
		return n * a
	if n - 1 < m:
		return n * b
	return min(n // (m + 1) * m * a + (n - n // (m + 1) * (m + 1)) * b, n * b)
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	print(solution(a, b, n, m))


def main():
	n = int(input())
	ans = []
	for i in range(n):
		(a, b) = list(map(int, input().split()))
		(n, m) = list(map(int, input().split()))
		if a < b:
			p = (n // (m + 1) * m + n % (m + 1)) * a
			print(p)
			continue
		if m * a > b * (m + 1):
			p = b * n
			print(p)
			continue
		p = n // (m + 1) * m * a + n % (m + 1) * b
		print(p)
main()


for _ in range(int(input())):
	(first, second) = map(int, input().split(' '))
	(n, m) = map(int, input().split(' '))
	cost = 0
	while n > 0:
		if n > m and m * first < second * (m + 1):
			cost += n // (m + 1) * m * first
			n = n % (m + 1)
		else:
			cost += n * min(first, second)
			n = 0
	print(cost)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	if m > n:
		print(min(n * a, n * b))
	else:
		k = n // (m + 1)
		r = n % (m + 1)
		print(min(b * n, k * m * a + r * min(a, b)))


t = int(input())
for _ in range(t):
	(a, b) = tuple(map(int, input().split()))
	(n, m) = tuple(map(int, input().split()))
	if a < b:
		x = n // (m + 1)
		print((n - x) * a)
	elif m * a < (m + 1) * b:
		x = n // (m + 1)
		print(x * m * a + (n - x * (m + 1)) * b)
	else:
		print(n * b)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	(x, y) = map(int, input().split())
	(n, m) = map(int, input().split())
	if m >= n:
		print(min(x, y) * n)
	else:
		ele = m + 1
		ans = 0
		q = n // ele
		rem = n % ele
		ans += q * x * m
		ans += rem * min(x, y)
		print(min(ans, n * y))


T = int(input())
for t in range(0, T):
	(a, b) = map(int, input().split(' '))
	(n, m) = map(int, input().split(' '))
	abs = 0
	if m >= n:
		ans = min(a * n, b * n)
	else:
		x = n // (m + 1)
		y = n % (m + 1)
		val = min(m * a, (m + 1) * b)
		ans = x * val
		ans += y * min(a, b)
	print(ans)


t = int(input())
while t:
	(a, b) = [int(x) for x in input().split()]
	(n, m) = [int(x) for x in input().split()]
	d = n // (m + 1)
	p = d * m * a + (n - d * (m + 1)) * min(a, b)
	p_2 = n * min(a, b)
	print(min(p, p_2))
	t -= 1


for i in range(int(input())):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	ans = 0
	if n < m:
		ans = min(a * n, b * n)
	else:
		temp1 = b * (m + 1)
		temp2 = a * m
		if temp2 < temp1:
			rem = n // (m + 1)
			ans += rem * temp2
			n = n % (m + 1)
			ans += n * min(a, b)
		else:
			ans = b * n
	print(ans)


k = int(input())
for _ in range(k):
	p = [int(x) for x in input().split()]
	(n, m) = [int(x) for x in input().split()]
	print(min(p[1] * n, p[0] * m * (n // (m + 1)) + n % (m + 1) * p[0], p[0] * m * (n // (m + 1)) + n % (m + 1) * p[1]))


t = int(input())
for _ in range(t):
	x = input().split(' ')
	(a, b) = (int(x[0]), int(x[1]))
	y = input().split(' ')
	(n, m) = (int(y[0]), int(y[1]))
	coins = 0
	if m > n:
		if a > b:
			coins += b * n
		else:
			coins += a * n
	else:
		offer = m + 1
		div = n // offer
		coins += a * div * m
		left = n - div * offer
		if a > b:
			coins += left * b
		else:
			coins += left * a
	withoutOffer = b * n
	print(min(coins, withoutOffer))


t = int(input())
for _ in range(t):
	(d1, d2) = list(map(int, input().split()))
	(required, promotion) = list(map(int, input().split()))
	normal = min(d1, d2) * required
	greed = required // (promotion + 1) * (promotion * d1) + required % (promotion + 1) * min(d1, d2)
	print(min(normal, greed))


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	(m, n) = map(int, input().split())
	f = b * m
	c = 0
	d = n + 1
	e = m % d
	g = m // d
	c = c + g * a * n
	if e != 0:
		c = c + e * min(a, b)
	ans = min(c, f)
	print(ans)


times = int(input())
price = 0
need = 0
dayone = 0
daytwo = 0
n = 0
m = 0
total = 0
for i in range(times):
	price = input().split()
	need = input().split()
	dayone = int(price[0])
	daytwo = int(price[1])
	n = int(need[0])
	m = int(need[1])
	if n >= m + 1:
		total = min(m * dayone * (n // (m + 1)) + min(dayone, daytwo) * (n % (m + 1)), n * min(dayone, daytwo))
	else:
		total = n * min(dayone, daytwo)
	print(total)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	temp = n // (m + 1)
	t = temp * a * m
	rem = n % (m + 1)
	if rem != 0:
		t += min(rem * a, rem * b)
	print(min(n * a, n * b, t))


t = int(input())
for z in range(t):
	amt = 0
	tempamt = 0
	(a, b) = [int(x) for x in input().split()]
	(n, m) = [int(x) for x in input().split()]
	if n <= m:
		if a <= b:
			amt = a * n
		else:
			amt += b * n
	elif n > m:
		x = n // (m + 1)
		amt += a * m * x
		n -= (m + 1) * x
		tempamt += b * (m + 1) * x
		if amt > tempamt:
			amt = tempamt
		if n > 0:
			if a > b:
				amt += b * n
			else:
				amt += a * n
	print(amt)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	if m < n:
		x = n // (m + 1)
		p = x * m * a + (n - x * m - x) * min(a, b)
		p = min(p, n * min(a, b))
	else:
		p = n * min(a, b)
	print(p)


def f(a, b, n, m):
	alp = n // (m + 1)
	alp_co = alp * m
	beta = n - alp * (m + 1)
	if b >= a:
		c = a * (alp_co + beta)
	elif a > b:
		slope = a * m - b * (m + 1)
		if slope < 0:
			c = alp * slope + b * n
		else:
			c = b * n
	print(c)
for i in range(int(input())):
	inp1 = list(map(int, input().split(' ')))
	a = inp1[0]
	b = inp1[1]
	inp2 = list(map(int, input().split(' ')))
	n = inp2[0]
	m = inp2[1]
	f(a, b, n, m)


from math import *
for z in range(int(input())):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	t = n // (m + 1)
	print(min(b * n, a * (t * m) + min(a, b) * (n - t * (m + 1))))


import math

def solve():
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	z1 = n // (m + 1)
	if a < b:
		n1 = n - n // (m + 1)
		return a * n1
	if (a - b) * m - b > 0:
		return b * n
	n1 = z1 * m
	n2 = n - (n1 + z1)
	cost = n1 * a + n2 * b
	return cost
T = int(input())
for t in range(T):
	print(solve())


import sys
sys.setrecursionlimit(10 ** 9)
for i in range(int(input())):
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	if l1[0] > l1[1]:
		if l2[0] <= l2[1]:
			print(l1[1] * l2[0])
		else:
			print(min(l1[1] * (l2[0] - l2[0] % (l2[1] + 1)), l1[0] * (l2[0] // (l2[1] + 1) * l2[1])) + l1[1] * (l2[0] % (l2[1] + 1)))
	else:
		print(l1[0] * (l2[0] // (l2[1] + 1) * l2[1] + l2[0] % (l2[1] + 1)))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	q = n % (m + 1)
	p = n // (m + 1)
	ans = min(a * m, b * (m + 1)) * p + min(a, b) * q
	print(ans)


test = int(input())
for t in range(test):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	d1 = n // (m + 1) * a * m + n % (m + 1) * a
	d2 = b * n
	s = n // (m + 1) * m * a + n % (m + 1) * b
	if n <= m:
		print(min(a * n, b * n))
	else:
		print(min(s, min(d1, d2)))


def solver(day_1, day_2, potatoes, promo):
	cost = 0
	bag = 0
	result = 0
	day_2_total_cost = day_2 * potatoes
	day_1_total_cost = day_1 * potatoes
	if day_2_total_cost < day_1_total_cost:
		result = day_2_total_cost
	else:
		result = day_1_total_cost
	discount = promo + 1
	bag = potatoes // discount * promo
	leftover = potatoes % discount
	cost += day_1 * bag
	if day_1 < day_2:
		cost += day_1 * leftover
	else:
		cost += day_2 * leftover
	if cost < result:
		return cost
	else:
		return result
numTest = int(input())
for test in range(numTest):
	prices = input().split()
	day_1 = int(prices[0])
	day_2 = int(prices[-1])
	amount = input().split()
	potatoes = int(amount[0])
	promo = int(amount[-1])
	print(solver(day_1, day_2, potatoes, promo))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	q = n // (m + 1)
	r = n - q * (m + 1)
	print(q * min(a * m, b * (m + 1)) + r * min(a, b))


def main(args):

	def solution():
		n = int(input())
		for i in range(n):
			price = [int(x) for x in input().split()]
			(a, b) = (price[0], price[1])
			amount = [int(x) for x in input().split()]
			(n, m) = (amount[0], amount[1])
			d1 = n // (m + 1)
			d2 = n - d1 * (m + 1)
			print(min(b * n, d1 * a * m + d2 * b, d1 * a * m + d2 * a))
	solution()
import sys
sys.exit(main(sys.argv))


t = int(input())
for z in range(t):
	(a, b) = [int(x) for x in input().split()]
	(n, m) = [int(x) for x in input().split()]
	if m >= n:
		if a >= b:
			print(b * n)
		else:
			print(a * n)
	else:
		if a * m < b * (m + 1):
			ans = n // (m + 1) * a * m + n % (m + 1) * min(a, b)
		else:
			ans = min(a, b) * n
		print(ans)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split(' '))
	(n, m) = map(int, input().split(' '))
	q = int(n / (m + 1))
	r = n - q * (m + 1)
	print(q * min(a * m, b * (m + 1)) + r * min(a, b))


T = int(input())
for _ in range(T):
	(A, B) = map(int, input().split())
	(n, M) = map(int, input().split())
	prom = A * M
	nonprom = B * (M + 1)
	if prom < nonprom:
		ans = n // (M + 1) * A * M
		if A < B:
			ans += n % (M + 1) * A
		else:
			ans += n % (M + 1) * B
	else:
		ans = n * B
	print(ans)


_ = int(input())
for i in range(_):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	p1 = n // (m + 1) * a * m + min(a, b) * (n % (m + 1))
	p2 = n * b
	print(min(p1, p2))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	if n <= m:
		print(n * min(a, b))
	elif m * a <= (m + 1) * b:
		kilo1 = n // (m + 1)
		kilo2 = n % (m + 1)
		total = kilo1 * a * m
		total += kilo2 * min(a, b)
		print(total)
	else:
		print(n * b)


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split(' '))
	(n, m) = map(int, input().split(' '))
	print(min(n // (m + 1) * m * a + n % (m + 1) * min(a, b), n * b))


t = int(input())
for i in range(t):
	(a, b) = [int(i) for i in input().split()]
	(n, m) = [int(i) for i in input().split()]
	minp = min(a, b)
	day1 = n // (m + 1) * m
	print(min(day1 * a + n % (m + 1) * minp, n * minp))


testCount = input()
for i in range(int(testCount)):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	price = 0
	if a <= b:
		(curNa_pre, curNa_comm) = divmod(n, m + 1)
		curNa_pre *= m
		price = (curNa_comm + curNa_pre) * a
	elif a > b:
		if n <= m:
			price = n * b
		elif n > m:
			if m * a // (m + 1) < b:
				(curNa, curNb) = divmod(n, m + 1)
				curNa *= m
				price = curNa * a + curNb * b
			else:
				price = n * b
	print(price)


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split(' '))
	(n, m) = map(int, input().split(' '))
	if n <= m:
		print(min(n * a, n * b))
	else:
		x1 = m * a
		x2 = (m + 1) * b
		if x1 < x2:
			count = n // (m + 1)
			pricePromotion = count * m * a
			left = n % (m + 1)
			leftPrice = min(left * a, left * b)
			print(leftPrice + pricePromotion)
		else:
			print(min(n * a, n * b))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(n, m) = map(int, input().split())
	x = m * (n // (m + 1)) * a + n % (m + 1) * min(a, b)
	y = b * n
	print(min(x, y))


it = int(input())
for i in range(it):
	L1 = [int(x) for x in input().split()]
	a = L1[0]
	b = L1[1]
	L2 = [int(x) for x in input().split()]
	n = L2[0]
	m = L2[1]
	if m >= n:
		ans = min(a, b) * n
	elif a < b:
		ans = (m * (n // (m + 1)) + n % (m + 1)) * a
	elif b * (m + 1) <= a * m:
		ans = b * n
	else:
		ans = a * m * (n // (m + 1)) + n % (m + 1) * b
	print(ans)


def solve():
	t = int(input())
	while t:
		t -= 1
		(a, b) = [int(x) for x in input().split()]
		(n, m) = [int(x) for x in input().split()]
		if n <= m:
			result = min(n * a, n * b)
		else:
			divi = int(n / (m + 1))
			modu = n % (m + 1)
			result = min(m * divi * a + modu * a, m * divi * a + modu * b, n * b)
		print(result)
solve()


for _ in range(int(input())):
	(a, b) = [int(i) for i in input().split()]
	(n, m) = [int(i) for i in input().split()]
	print(min(a * m * (n // (m + 1)) + n % (m + 1) * a, min(n * b, a * m * (n // (m + 1)) + n % (m + 1) * b)))