Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a matrix $A$ with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$).

You need to fill the matrix with candies in such a way that:
For each cell, the number of candies in this cell is an integer between $0$ and $X$ inclusive.
For each pair of adjacent cells, the number of candies in one cell plus the number of candies in the other cell does not exceed $Y$. Two cells are considered adjacent if they share a side.

Find the maximum number of candies you can place in the given matrix.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains four space-separated integers $N$, $M$, $X$ and $Y$.

------  Output ------
For each test case, print a single line containing one integer ― the maximum number of candies.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N, M ≤ 100$
$1 ≤ X, Y ≤ 10^{4}$

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
2

4 4 4 6

3 4 4 5
----- Sample Output 1 ------ 
48

30

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(n, m, x, y) = map(int, input().split())
	if n * m > 1:
		x = min(x, y)
	y = min(y, 2 * x)
	print((n * m + 1) // 2 * x + n * m // 2 * (y - x))


for __ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	if n * m > 1:
		x = min(x, y)
	y = min(y, 2 * x)
	print((n * m + 1) // 2 * x + n * m // 2 * (y - x))


t = int(input())
for i in range(t):
	(a, b, x, y) = map(int, input().split())
	if a == 1 and b == 1:
		count = x
	elif y > 2 * x:
		count = x * a * b
	elif a * b % 2 == 0:
		count = y * a * b / 2
	elif x > y:
		count = y * (a * b - 1) / 2 + y
	else:
		count = y * (a * b - 1) / 2 + x
	print(int(count))


T = int(input())
for i in range(T):
	(A, B, X, Y) = map(int, input().split())
	if Y > 2 * X:
		counter = X * A * B
	elif A * B == 1:
		counter = X
	elif A * B % 2 == 0:
		counter = Y * A * B / 2
	elif X > Y:
		counter = Y * (A * B - 1) / 2 + Y
	else:
		counter = Y * (A * B - 1) / 2 + X
	print(int(counter))


T = int(input())
for tc in range(T):
	(N, M, X, Y) = map(int, input().split())
	if Y > 2 * X:
		count = X * N * M
	elif N * M == 1:
		count = X
	elif N * M % 2 == 0:
		count = Y * N * M / 2
	elif X > Y:
		count = Y * (N * M - 1) / 2 + Y
	else:
		count = Y * (N * M - 1) / 2 + X
	print(int(count))


for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	if n == 1 and m == 1:
		print(x)
	else:
		x = min(x, y)
		y = min(2 * x, y)
		c = (n * m + 1) // 2 * x
		c += n * m // 2 * (y - x)
		print(c)


for _ in range(int(input())):
	(M, N, X, Y) = map(int, input().split())
	if X + X <= Y:
		ans = X * M * N
	elif M == 1 and N == 1:
		ans = X
	else:
		if X >= Y:
			X = Y
		if M % 2 == 0 or N % 2 == 0:
			ans = Y * M * N / 2
		else:
			ans = Y * (M * N - 1) / 2 + X
	print(int(ans))


def ans(n, m, x, y):
	if n * m > 1:
		x = min(x, y)
	y = min(2 * x, y)
	z = (n * m + 1) // 2 * x
	z2 = n * m // 2 * (y - x)
	print(z + z2)
for _ in range(int(input())):
	(n, m, x, y) = [int(i) for i in input().split()]
	ans(n, m, x, y)


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def ni():
	return int(input())

def si():
	return str(input())
for t in range(ni()):
	(N, M, X, Y) = mi()
	if M == N == 1:
		print(X)
		continue
	a = Y // 2
	b = Y - a
	a = min(X, a)
	b = min(X, b)
	ans = 0
	for k in range(Y + 1):
		temp1 = 0
		temp2 = 0
		a = min(k, X)
		b = min(Y - k, X)
		c = N // 2
		d = N - c
		e = M // 2
		f = M - e
		ans = max(ans, (d * f + c * e) * b + (c * f + d * e) * a)
	print(ans)


for i in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	if x >= y / 2:
		ans = y * (n * m // 2)
		if n * m % 2 == 1:
			if n == 1 and m == 1:
				ans += x
			else:
				ans += min(x, y)
		print(ans)
	else:
		print(x * (n * m))


t = int(input())
for i in range(t):
	(N, M, X, Y) = map(int, input().split())
	ans = 0
	if N * M == 1:
		ans = X
	elif X * 2 <= Y:
		ans = N * M * X
	elif Y >= X:
		if N * M % 2 == 0:
			ans = N * M // 2 * Y
		else:
			ans = N * M // 2 * Y + X
	else:
		ans = (N * M + 1) // 2 * Y
	print(ans)


for i in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	a = n * m
	if m == 1 and n == 1:
		print(x)
		continue
	if a % 2 == 1:
		n = a // 2 + 1
		m = a // 2
	else:
		n = m = a // 2
	if y >= x:
		if y >= 2 * x:
			y = x
		else:
			y = y - x
	else:
		x = y
		y = 0
	print(x * n + y * m)


class CoinGame:

	def findMaxCoins(self, N, M, maxPerField, maxSum):
		if N * M > 1:
			maxPerField = min(maxPerField, maxSum)
		maxSum = min(maxSum, 2 * maxPerField)
		return (N * M + 1) // 2 * maxPerField + N * M // 2 * (maxSum - maxPerField)
solver = CoinGame()
T = int(input())
while T:
	T -= 1
	inputLine = input()
	(N, M, X, Y) = [int(i) for i in inputLine.split(' ')]
	print(solver.findMaxCoins(N, M, X, Y))


t = int(input())
while t > 0:
	t -= 1
	ip = input().split()
	(n, m, x, y) = [int(i) for i in ip]
	nm = n * m
	if n == 1 and m == 1:
		print(x)
		continue
	if y <= x:
		x = y
		y_x = 0
	elif y > x and y <= 2 * x:
		x = max(x, y - x)
		y_x = y - x
	elif y > 2 * x:
		x = x
		y_x = x
	print(nm // 2 * y_x + (nm - nm // 2) * x)


for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	t = n * m
	if n == 1 and m == 1:
		print(x)
	else:
		if t & 1:
			(f, s) = (t // 2 + 1, t // 2)
		else:
			(f, s) = (t // 2, t // 2)
		if x >= y:
			print(f * y)
		elif y - x <= x:
			print(f * x + s * (y - x))
		else:
			print(x * (f + s))


T = int(input())
for i in range(T):
	(p, q, x, y) = map(int, input().split())
	y = min(2 * x, y)
	if p == 1 and q == 1:
		print(x)
		continue
	if p * q % 2 == 0:
		print(p * q // 2 * y)
	else:
		print(min(x, y) + p * q // 2 * y)


from collections import Counter
import string
import math
import bisect
import sys
from fractions import Fraction

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(arrber_of_variables):
	if arrber_of_variables == 1:
		return int(sys.stdin.readline())
	if arrber_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))
testcases = vary(1)
for _ in range(testcases):
	(n, m, x, y) = map(int, input().split())
	if y >= 2 * x:
		print(x * n * m)
	elif n == 1 and m == 1:
		print(x)
	elif y <= x:
		print((m * n + 1) // 2 * y)
	else:
		print((m * n + 1) // 2 * x + m * n // 2 * (y - x))


import sys
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]
for _ in range(RI()):
	(n, m, x, y) = RMI()
	if n * m > 1:
		x = min(x, y)
	y = min(y, 2 * x)
	answer = (n * m + 1) // 2 * x + n * m // 2 * (y - x)
	print(answer)


def greedyChoco(n, m, x, y):
	z = n * m
	if z == 1:
		return x
	p = z % 2
	q = z // 2
	(x, y) = (min(x, y), min(2 * x, y))
	return y * q + x * p
for t in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	print(greedyChoco(n, m, x, y))


for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	if n == 1 and m == 1:
		ans = x
	elif n * m % 2 == 0:
		if y >= 2 * x:
			ans = n * m * x
		elif y >= x:
			ans = (n * m + 1) // 2 * x + n * m // 2 * (y - x)
		else:
			ans = n * m * y // 2
	elif y >= 2 * x:
		ans = n * m * x
	elif y >= x:
		ans = (n * m + 1) // 2 * x + n * m // 2 * (y - x)
	else:
		ans = y * ((n * m + 1) // 2)
	print(ans)


try:
	for _ in range(int(input())):
		(n, m, x, y) = [int(_) for _ in input().split()]
		p = (n * m + 1) // 2
		q = n * m // 2
		if n * m == 1:
			print(x)
		elif x * 2 <= y:
			print(n * m * x)
		elif y <= x:
			print(y * p)
		else:
			print(x * p + (y - x) * q)
except:
	pass


try:
	t = int(input())
	for i in range(0, t):
		(n, m, x, y) = map(int, input().split(' '))
		h = x
		j = y
		(x1, y1) = (min(h, j), min(2 * h, j))
		u = (n * m + 1) // 2 * x1
		v = n * m // 2 * (y1 - x1)
		if n == 1 and m == 1:
			print(h)
		else:
			print(u + v)
except:
	pass


try:
	T = int(input())
	while T:
		T = T - 1
		(a, b, x, y) = map(int, input().split(' '))
		n = max(a, b)
		m = min(a, b)
		ans = 0
		if 2 * x <= y:
			ans = n * m * x
		elif n == 1 and m == 1:
			ans = x
		elif m == 1:
			if x > y:
				x = y
			ans = y * n // 2
			if n % 2 != 0:
				ans = ans + x
		else:
			if x > y:
				x = y
			r1 = y * (n // 2)
			if n % 2 != 0:
				r1 = r1 + x
			r2 = y * (n // 2)
			if n % 2 != 0:
				r2 = r2 + y - x
			kk = r1
			for i in range(m):
				ans = ans + kk
				if kk == r1:
					kk = r2
				else:
					kk = r1
		print(ans)
except:
	pass


for __ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	if n == 1 and m == 1:
		ans = x
	elif x >= y:
		ans = n * m * y // 2 if n * m % 2 == 0 else (n * m + 1) // 2 * y
	elif n * m % 2 == 0:
		ans = n * m * x // 2
		ans += n * m * min(x, y - x) // 2
	else:
		c1 = (n * m + 1) // 2
		c2 = n * m - c1
		ans = c1 * x
		ans += c2 * min(x, y - x)
	print(int(ans))


def solve(n, m, x, y):
	if y >= x:
		q = x
		w = min(y - x, x)
	else:
		q = 0
		w = y
	j = max(q, w)
	k = min(q, w)
	b = n * m
	if b == 1:
		return x
	if b & 1 == 0:
		ans = b // 2 * k + b // 2 * j
	else:
		ans = (b // 2 + 1) * j + b // 2 * k
	return ans
t = int(input())
for _ in range(t):
	(n, m, x, y) = map(int, input().split())
	print(solve(n, m, x, y))


T = int(input())
for i in range(T):
	(n, m, x, y) = map(int, input().split())
	if n * m == 1:
		print(x)
	elif 2 * x <= y:
		print(n * m * x)
		continue
	elif n * m % 2:
		print((n * m - 1) * y // 2 + min(x, y))
		continue
	else:
		print(n * m * y // 2)
		continue


try:
	from math import ceil, floor
	T = int(input())
	for _ in range(T):
		(N, M, X, Y) = [int(i) for i in input().split()]
		if N == 1 and M == 1:
			s = X
			print(s)
		else:
			X = min(X, Y)
			Y = min(2 * X, Y)
			s = (N * M + 1) // 2 * X + N * M // 2 * (Y - X)
			print(s)
except EOFError:
	pass


from math import ceil, floor
T = int(input())
ans = []
for _ in range(T):
	(N, M, X, Y) = [int(i) for i in input().split()]
	if N == 1 and M == 1:
		s = X
	else:
		X = min(X, Y)
		Y = min(2 * X, Y)
		s = (N * M + 1) // 2 * X + N * M // 2 * (Y - X)
	ans.append(s)
for i in ans:
	print(i)


t = 0
try:
	t = int(input())
except:
	pass
for _ in range(t):
	(n, m, x, y) = list(map(int, input().split()))
	y = min(2 * x, y)
	if n * m > 1:
		x = min(x, y)
	print((n * m + 1) // 2 * x + n * m // 2 * (y - x))


t = int(input())
for _ in range(t):
	(n, m, x, y) = map(int, input().split())
	tot = n * m
	if n == 1 and m == 1:
		ans = x
	else:
		part1 = min(x, y)
		max_sum = min(2 * x, y)
		part2 = max_sum - part1
		ans = (tot + 1) // 2 * part1 + tot // 2 * part2
	print(ans)


for _ in range(int(input())):
	(rows, columns, x, y) = map(int, input().split())
	if rows == 1 and columns == 1:
		print(x)
	elif x < y:
		if 2 * x <= y:
			print(x * rows * columns)
		elif rows * columns % 2 == 0:
			print(y * (rows * columns // 2))
		else:
			print(y * (rows * columns // 2) + x)
	elif rows * columns % 2 == 0:
		print(y * (rows * columns // 2))
	else:
		print(y * (rows * columns // 2) + y)


for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	mat = [[0 for x in range(m)] for y in range(n)]
	if n * m > 1:
		x = min(x, y)
		y = min(2 * x, y)
	for i in range(n):
		for j in range(m):
			if i == 0 and j == 0:
				mat[i][j] = x
			elif i == 0:
				mat[i][j] = min(abs(mat[i][j - 1] - y), x)
			elif j == 0:
				mat[i][j] = min(abs(mat[i - 1][j] - y), x)
			else:
				mat[i][j] = min(abs(mat[i - 1][j] - y), abs(mat[i][j - 1] - y), x)
	ans = 0
	for i in range(n):
		for j in range(m):
			ans += mat[i][j]
	print(ans)


def fun():
	a = []
	for i in range(m):
		if i == 0:
			if x <= y:
				a.append(x)
			else:
				a.append(y)
		elif y - a[i - 1] >= x:
			a.append(x)
		else:
			a.append(y - a[i - 1])
	return a
from sys import stdin, stdout
for _ in range(int(stdin.readline().strip())):
	(n, m, x, y) = map(int, stdin.readline().strip().split())
	temp = []
	if n == 1 and m == 1:
		stdout.write(str(x) + '\n')
	else:
		if m % 2 != 0:
			temp = fun()
			s2 = (sum(temp) + min(temp) - max(temp)) * (n // 2)
			s1 = sum(temp) * (n // 2 + n % 2)
			f = s1 + s2
		else:
			f = sum(fun())
			f *= n
		stdout.write(str(f) + '\n')


t = int(input())
while t:
	t -= 1
	(n, m, x, y) = map(int, input().split())
	if y >= 2 * x:
		print(x * n * m)
	elif n == 1 and m == 1:
		print(x)
	elif y <= x:
		print((m * n + 1) // 2 * y)
	else:
		print((m * n + 1) // 2 * x + m * n // 2 * (y - x))


def sol():
	(n, m, x, y) = map(int, input().split())
	if y >= 2 * x:
		print(x * n * m)
	elif n == 1 and m == 1:
		print(x)
	elif y <= x:
		print((m * n + 1) // 2 * y)
	else:
		print((m * n + 1) // 2 * x + m * n // 2 * (y - x))
try:
	for _ in range(int(input())):
		sol()
except:
	pass


import math
t = int(input())
while t:
	t = t - 1
	(n, m, x, y) = [int(i) for i in input().split()]
	co = m * n
	if n == 1 and m == 1:
		print(x)
		continue
	elif x >= y:
		if co % 2 == 0:
			total = co // 2 * y
		else:
			total = (co - 1) // 2 * y + y
	elif 2 * x <= y:
		total = co * x
	elif co % 2 == 0:
		total = co // 2 * y
	elif x >= y - x:
		total = (co - 1) // 2 * y + x
	else:
		total = (co - 1) // 2 * y + (y - x)
	print(total)


t = int(input())
b = []
for i in range(t):
	(n, m, x, y) = map(int, input().split())
	s = n * m
	if s == 1:
		print(x)
	elif 2 * x <= y:
		print(s * x)
	elif 2 * x > y and x <= y:
		if s % 2 == 0:
			s = s // 2
			print(s * y)
		else:
			s = s // 2
			print(s * y + x)
	elif s % 2 == 0:
		s = s // 2
		print(s * y)
	else:
		s = s // 2
		print(s * y + y)


T = int(input())
for i in range(T):
	(N, M, X, Y) = map(int, input().split(' '))
	cells = N * M
	if cells == 1:
		print(X)
	elif Y >= 2 * X:
		total = cells * X
		print(total)
	elif Y >= X:
		if cells % 2 != 0:
			total = cells // 2 * Y + X
			print(total)
		else:
			total = cells // 2 * Y
			print(total)
	elif cells % 2 != 0:
		total = (cells // 2 + 1) * Y
		print(total)
	else:
		total = cells // 2 * Y
		print(total)


T = int(input())
for _ in range(T):
	(N, M, X, Y) = map(int, input().split())
	if M == N == 1:
		print(X)
	else:
		if N * M > 1:
			X = min(X, Y)
		Y = min(2 * X, Y)
		ans = (N * M + 1) // 2 * X + N * M // 2 * (Y - X)
		print(ans)


t = int(input())
for i in range(t):
	(r, c, x, y) = [int(i) for i in input().split()]
	te = int(r * c / 2)
	te2 = r * c - te
	(c1, c2) = (0, 0)
	if x >= y:
		(c1, c2) = (0, y)
	elif x > y - x:
		c1 = y - x
		c2 = x
	else:
		c1 = x
		c2 = x
	if te == max(te, te2):
		(te2, te) = (te, te2)
	te2 *= c2
	te *= c1
	if r * c != 1:
		print(te + te2)
	else:
		print(x)


t = int(input())
for i in range(t):
	(n, m, x, y) = [int(i) for i in input().split()]
	te = int(n * m / 2)
	te2 = n * m - te
	(c1, c2) = (0, 0)
	if x >= y:
		c2 = y
		c1 = 0
	elif x > y - x:
		c1 = y - x
		c2 = x
	else:
		c1 = x
		c2 = x
	if te > te2:
		te *= c2
		te2 *= c1
	else:
		te *= c1
		te2 *= c2
	if n * m != 1:
		print(te + te2)
	else:
		print(x)


from math import *
test = int(input())
for _ in range(test):
	(a, b, c, d) = map(int, input().split())
	k = a * b
	if a == 1 and b == 1:
		print(c)
	elif 2 * c <= d:
		print(c * k)
	else:
		print(min(c, d) * ceil(k / 2) + max(d - c, 0) * floor(k / 2))


try:
	t = int(input())
	for i in range(t):
		(n, m, x, y) = map(int, input().split())
		if n and m == 1:
			print(x)
		else:
			x = min(x, y)
			y = min(y - x, x)
			if m % 2 == 0:
				a = x * m // 2
				b = y * (m // 2)
				result = (a + b) * n
			else:
				a = x * (m // 2 + 1) + y * (m // 2)
				b = y * (m // 2 + 1) + x * (m // 2)
				if n % 2 == 0:
					result = (a + b) * (n // 2)
				else:
					result = a * (n // 2 + 1) + b * (n // 2)
			print(result)
except:
	pass


t = int(input())
for i in range(t):
	(n, m, x, y) = map(int, input().split())
	if n == 1 and m == 1:
		print(x)
		continue
	sum_ = 0
	matrix = [[0 for l in range(m)] for t in range(n)]
	for j in range(n):
		for k in range(m):
			candidate1 = 0
			if j == 0 and k == 0:
				candidate1 = min(x, y)
			elif j == 0 and k != 0:
				candidate1 = min(y - matrix[j][k - 1], x)
			elif j != 0 and k == 0:
				candidate1 = min(y - matrix[j - 1][k], x)
			elif j != 0 and k != 0:
				candidate1 = min(y - matrix[j - 1][k], y - matrix[j][k - 1], x)
			matrix[j][k] = candidate1
			sum_ = sum_ + candidate1
	print(sum_)


import math
for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	low = min(2 * x, y) - min(x, y)
	high = min(2 * x, y) - low
	tot = m * n
	if tot == 1:
		print(x)
	else:
		print(high * math.ceil(tot / 2) + low * (tot // 2))


try:
	t = int(input())
	for _ in range(t):
		(n, m, x, y) = map(int, input().split())
		a = 0
		if n * m == 1:
			a = x
		elif x * 2 <= y:
			a = n * m * x
		elif y >= x:
			if n * m % 2 == 0:
				a = n * m // 2 * y
			else:
				a = n * m // 2 * y + x
		else:
			a = (n * m + 1) // 2 * y
		print(a)
except:
	pass


for _ in range(int(input())):
	(n, m, x, y) = list(map(int, input().split()))
	a = 0
	if n * m == 1:
		a = x
	elif x * 2 <= y:
		a = n * m * x
	elif y >= x:
		if n * m % 2 == 0:
			a = n * m // 2 * y
		else:
			a = n * m // 2 * y + x
	else:
		a = (n * m + 1) // 2 * y
	print(a)


test = int(input())
for _ in range(test):
	(a, b, c, d) = map(int, input().split())
	m = a * b // 2
	if a * b == 1:
		ans = c
	elif c * 2 <= d:
		ans = c * a * b
	elif d >= c:
		if a * b % 2 != 0:
			ans = m * d + c
		else:
			ans = m * d
	else:
		ans = (a * b + 1) // 2 * d
	print(ans)


import math
for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	if m * n == 1:
		print(x)
		continue
	x = min(x, y)
	y = min(2 * x, y)
	ans = (n * m + 1) // 2 * x + m * n // 2 * (y - x)
	print(ans)


from sys import stdin

def solve(n, m, x, y):
	if n == m == 1:
		return x
	high_candy = min(x, y)
	if x >= y:
		low_candy = 0
	else:
		low_candy = min(x, y - x)
	high_boxes = (m // 2 + m % 2) * (n // 2 + n % 2) + m // 2 * (n // 2)
	low_boxes = m // 2 * (n // 2 + n % 2) + (m // 2 + m % 2) * (n // 2)
	total = low_candy * low_boxes + high_candy * high_boxes
	return total
for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	print(solve(n, m, x, y))


def chechoc(n, m, x, y):
	if n * m == 1:
		return x
	elif y >= x * 2:
		max = x
		min = x
		check = n * m
		if check % 2 == 1:
			max = max * (check + 1) // 2
			min = min * (check - 1) // 2
			return max + min
		else:
			return max * check // 2 + min * check // 2
	elif y >= x:
		max = x
		min = y - x
		check = n * m
		if check % 2 == 1:
			max = max * (check + 1) // 2
			min = min * (check - 1) // 2
			return max + min
		else:
			return max * check // 2 + min * check // 2
	else:
		max = y
		min = 0
		check = n * m
		if check % 2 == 1:
			max = max * (check + 1) // 2
			min = min * (check - 1) // 2
			return max + min
		else:
			return max * check // 2 + min * check // 2
t = int(input())
while t:
	(n, m, x, y) = list(map(int, input().split()))
	ans = chechoc(n, m, x, y)
	print(ans)
	t -= 1


for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	if n == 1 and m == 1:
		print(x)
	else:
		if y >= x:
			a = x
			if y - x > x:
				b = x
			else:
				b = y - x
		else:
			a = y
			b = 0
		total = (n * m + 1) // 2 * a + n * m // 2 * b
		print(total)


t = int(input())
for i in range(t):
	(n, m, x, y) = map(int, input().split())
	s = 0
	if n == 1 and m == 1:
		print(x)
	else:
		x = min(x, y)
		y = min(2 * x, y)
		v = (n * m + 1) // 2 * x + n * m // 2 * (y - x)
		print(v)


t = int(input())
for _ in range(t):
	t -= 1
	(n, m, x, y) = map(int, input().split())
	if x < y:
		(aa, bb) = (x, min(x, y - x))
	else:
		(aa, bb) = (y, 0)
	s = 0
	if n == 1 and m == 1:
		print(x)
	else:
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					s += aa
				else:
					s += bb
		print(s)


import math
for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	s = n * m
	v = math.ceil(s / 2)
	if m * n == 1:
		print(x)
	elif y >= 2 * x:
		print(m * n * x)
	elif y > x:
		k = v * x
		l = (s - v) * (y - x)
		print(k + l)
	elif y <= x:
		k = v * min(x, y)
		print(k)


for _ in range(int(input())):
	(r, c, x, y) = map(int, input().split())
	if r == 1 and c == 1:
		print(x)
	else:
		if y >= x:
			first = x
			second = y - x
			if second <= x:
				pass
			else:
				second = first
		else:
			first = y
			second = 0
		if c % 2 == 0:
			one = c // 2 * first + c // 2 * second
			print(one * r)
		else:
			one = c // 2 * second + (c // 2 + 1) * first
			two = c // 2 * first + (c // 2 + 1) * second
			if r % 2 == 0:
				print(r // 2 * two + r // 2 * one)
			else:
				print(r // 2 * two + (r // 2 + 1) * one)


t = int(input())
for i in range(t):
	(n, m, x, y) = map(int, input().split())
	if n == 1 and m == 1:
		print(x)
	else:
		b = min(y, x)
		a = min(x, y - b)
		total = n * m
		if total % 2 == 0:
			print((a + b) * (total // 2))
		else:
			print(b * (total // 2 + 1) + a * (total // 2))


for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	X = min(x, y)
	Y = min(2 * x, y)
	ans = 0
	if n == m == 1:
		print(x)
		continue
	else:
		ans = (n * m + 1) // 2 * X + n * m // 2 * (Y - X)
	print(ans)


import math
t = int(input())
while t > 0:
	a = list(map(int, input().split()))
	n = a[0]
	m = a[1]
	x = a[2]
	y = a[3]
	if n == 1 and m == 1:
		ans = x
	elif 2 * x <= y:
		ans = n * m * x
	elif n * m % 2 != 0:
		ans = y * (n * m - 1) / 2.0 + min(x, y)
	else:
		ans = y * n * m / 2.0
	print(int(ans))
	t -= 1