You are in a grid of dimensions N \times M.

You are allowed to perform two types of operations:
Go down, left, up, or right each for a cost of X. Formally, if you are at the cell (i,j) of the grid, you can go to either of the cells (i + 1, j), (i, j - 1), (i - 1, j) or (i, j + 1) at a cost of X.
Go diagonally down-left, down-right, up-left, up-right, for a cost of Y. Formally, if you are at the cell (i,j) of the grid, you can go to either of the cells (i + 1, j - 1), (i + 1, j + 1), (i - 1, j - 1) or (i - 1, j + 1) at a cost of Y.

You cannot exit the grid at any point. Find the minimum cost of going to the bottom-right corner (N, M) from the top-left corner (1, 1). 

\textbf{Note}: Since input-output is large, prefer using fast input-output methods.

------ Input Format ------ 

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains of a single line of input, four space separated integers integers: N, M, X, Y.

------ Output Format ------ 

For each testcase, output the answer in a new line.

------ Constraints ------ 

$1 ≤ T ≤ 5 \cdot 10^{5}$
$1 ≤ N, M, X, Y ≤ 10^{6}$

----- Sample Input 1 ------ 
3
5 6 2 5
4 7 5 6
7 8 6 5
----- Sample Output 1 ------ 
18
33
36
----- explanation 1 ------ 
Test Case $1$:
We can go $4$ steps down from $(1, 1)$ to $(5, 1)$ and then $5$ steps right to $(5, 6)$. The total cost is $2 \times 9 = 18$

Test Case $2$:
We can go $3$ steps diagonally down-right from $(1, 1)$ to $(4, 4)$ and then $3$ steps right to $(4, 7)$. The total cost is $3 \times 6 + 3 \times 5  = 18 + 15 = 33$

Test Case $3$:
We can go $6$ steps diagonally down-right from $(1, 1)$ to $(7, 7)$ and then $1$ step right to $(7, 8)$. The total cost is $5 \times 6 + 6 = 36$

Difficulty: HARD
Tags: Ad-hoc

Starter code:

Solutions:
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))

def func():
	(n, m, x, y) = map(int, input().split())
	d = abs(m - n)
	path1 = x * (n - 1 + m - 1)
	path2 = y * (min(n, m) - 1) + d * min(x, y)
	if d % 2 and x >= y:
		path2 += x - y
	return min(path1, path2)
t = inp()
for i in range(t):
	print(func())


t = int(input())
for _ in range(t):
	(n, m, x, y) = map(int, input().split())
	(ma, mi) = (max(n, m), min(n, m))
	if 2 * x < y:
		cost = 2 * (mi - 1) * x + (ma - mi) * x
	elif y < x:
		cost = (mi - 1) * y
		cost += (ma - mi) // 2 * 2 * y + (ma - mi) % 2 * x
	else:
		cost = (mi - 1) * y + (ma - mi) * x
	print(cost)


try:
	for t in range(int(input())):
		(N, M, X, Y) = map(int, input().split())
		if Y > 2 * X or M == 1 or N == 1:
			print((N + M - 2) * X)
		elif Y < X:
			if (max(M, N) - min(M, N)) % 2 == 0:
				print((min(M, N) - 1) * Y + (max(M, N) - min(M, N)) * Y)
			else:
				print((min(M, N) - 1) * Y + (max(M, N) - min(M, N) - 1) * Y + X)
		else:
			print((min(M, N) - 1) * Y + (max(M, N) - min(M, N)) * X)
except:
	pass


for _ in range(int(input())):
	(n, m, x, y) = [int(x) for x in input().split()]
	diff = abs(m - n)
	case1 = (n + m - 2) * x
	case2 = y * min(n - 1, m - 1) + diff * x
	case3 = y * min(n - 1, m - 1) + diff // 2 * 2 * y + diff % 2 * x
	print(min(case1, min(case2, case3)))


from sys import stdin
for _ in range(int(stdin.readline())):
	(n, m, x, y) = map(int, stdin.readline().split())
	(n, m) = (n - 1, m - 1) if n < m else (m - 1, n - 1)
	s = n + m
	if n > 0 and x > y:
		r = m * y if s % 2 == 0 else m * y + (x - y)
	else:
		r = s * x - n * max(0, 2 * x - y)
	print(r)


from sys import stdin
for _ in range(int(stdin.readline())):
	(n, m, x, y) = map(int, stdin.readline().split())
	(n, m) = (n - 1, m - 1) if n < m else (m - 1, n - 1)
	d = m - n
	case1 = x * (n + m)
	case2 = y * min(n, m) + d * min(x, y)
	if d % 2 == 1 and x >= y:
		case2 += x - y
	print(min(case1, case2))


for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	d = abs(m - n)
	case1 = x * (n - 1 + m - 1)
	case2 = y * (min(n, m) - 1) + d * min(x, y)
	if d % 2 == 1 and x >= y:
		case2 += x - y
	print(min(case1, case2))


def solveA():
	for _ in range(int(input())):
		print('YES' if input().count('1') > 3 else 'NO')

def solveB():
	for _ in range(int(input())):
		N = int(input())
		if N == 1:
			print('3')
		elif N == 2:
			print('21')
		else:
			print('11' + '0' * (N - 3) + '1')

def solveC():
	from itertools import permutations
	for _ in range(int(input())):
		T = [int(x) for x in input().split()]
		M = [int(x) for x in input().split()]
		ans = 0
		for i in range(21):
			for j in range(21):
				for k in range(21):
					if i * T[0] + j * T[1] + k * T[2] <= 240:
						temp = i * M[0] + j * M[1] + k * M[2]
						ans = max(ans, temp)
		print(ans)

def solveD():
	index = set()
	for _ in range(int(input())):
		(N, K) = [int(x) for x in input().split()]
		S = input() + '0' * K
		ans = 0
		index.clear()
		for i in range(K):
			if S[i] == '1' and S[i + K] == '0':
				ans += 1
				index.add(i + K)
		for i in range(K, N):
			if S[i] == '1' and S[i - K] == '0' and (S[i + K] == '0') and (i - K not in index):
				ans += 1
				index.add(i + K)
		return ans

def solveE():
	ans = []
	T = int(input())
	for _ in range(T):
		(N, M, X, Y) = [int(x) for x in input().split()]
		(N, M) = (N - 1, M - 1)
		if 0 in [N, M]:
			ans.append(X * max(N, M))
		elif 2 * X <= Y:
			ans.append((N + M) * X)
		elif abs(N - M) % 2:
			ans.append(Y * min(N, M) + min(X, Y) * (abs(N - M) - 1) + X)
		else:
			ans.append(Y * min(N, M) + min(X, Y) * abs(N - M))
	for i in range(T):
		print(ans[i])
solveE()


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


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


for i in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	d = 0
	d = (n + m - 2) * x
	l = min(n, m)
	k = max(n, m)
	d = min(d, (l - 1) * y + (k - l) * x)
	if (m - n) % 2:
		th = x
	else:
		th = 0
	th += (l - 1) * y
	th += (k - l - (k - l) % 2) * y
	d = min(d, th)
	print(d)


import sys

def codeChef():
	n = sys.stdin.readline()
	for _ in range(int(n)):
		(n, m, x, y) = map(int, sys.stdin.readline().strip().split())
		print(get_ans(n, m, x, y))

def get_ans(n, m, x, y):
	if y >= 2 * x:
		return (m + n - 2) * x
	elif x < y < 2 * x:
		return (min(m, n) - 1) * y + abs(m - n) * x
	elif x >= y and abs(m - n) % 2 == 0:
		return (min(m, n) - 1) * y + abs(m - n) * y
	return (min(m, n) - 1) * y + (abs(m - n) - 1) * y + x
try:
	codeChef()
except:
	pass


t = int(input())
for tt in range(t):
	(n, m, x, y) = map(int, input().split())
	diagonal = min(n, m) - 1
	result = min(2 * diagonal * x, diagonal * y)
	remain = max(n, m) - min(n, m)
	if x <= y:
		result += remain * x
	elif remain % 2 == 0:
		result += remain * y
	else:
		result += (remain - 1) * y + x
	print(result)


for i in range(int(input())):
	(N, M, X, Y) = map(int, input().split())
	if M == 1:
		print((N - 1) * X)
	elif N == 1:
		print((M - 1) * X)
	else:
		n = min(X, Y)
		k = (M + N - 2) * X
		j = min(N, M)
		b = (j - 1) * Y + (max(N, M) - j) * X
		l = (j - 1) * Y + (max(N, M) - j) * X
		m = (j - 1) * Y + (max(N, M) - 1) * X
		h = M + N - 2 * j
		if h & 1:
			h = (j - 1) * Y + (M + N - 2 * j - 1) * n + X
		else:
			h = (j - 1) * Y + (M - j + N - j) * n
		print(min(k, l, b, m, h))


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


import sys
for i in range(int(input())):
	(n, m, x, y) = map(int, sys.stdin.readline().split())
	if y > 2 * x:
		ans = (n - 1) * x + (m - 1) * x
	elif y < x:
		if abs(m - n) % 2 == 0:
			ans = (min(n, m) - 1 + abs(n - m)) * y
		else:
			ans = (min(n, m) - 1) * y + (abs(n - m) - 1) * y + x
	else:
		ans = (min(n, m) - 1) * y + abs(m - n) * x
	sys.stdout.write(str(ans) + '\n')


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


import sys
for _ in range(int(sys.stdin.readline())):
	(n, m, x, y) = map(int, sys.stdin.readline().split())
	a = max(n, m)
	b = min(m, n)
	if 2 * x <= y:
		print((n + m - 2) * x)
	elif y < x:
		if (a - b) % 2 == 0:
			print((a - 1) * y)
		else:
			print((a - 2) * y + x)
	else:
		print((b - 1) * y + (a - b) * x)


import sys
f = sys.stdin
next(f)
for s in f:
	(n, m, x, y) = map(int, s.split())
	(n, m) = sorted((n - 1, m - 1))
	s = n + m
	if n and x > y:
		r = m * y + (s % 2 and x - y)
	else:
		r = s * x - n * max(0, 2 * x - y)
	print(r)


for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	yg2x = (n + m - 2) * x
	x2gy = (min(n, m) - 1) * y + abs(n - m) * x
	xgyd2 = (min(n, m) - 1 + abs(n - m)) * y
	xgynd2 = (min(n, m) - 1 + abs(n - m) - 1) * y + x
	if y > 2 * x:
		print(yg2x)
	elif y < x:
		if abs(n - m) % 2 == 0:
			print(xgyd2)
		else:
			print(xgynd2)
	else:
		print(x2gy)


for t in range(int(input())):
	(N, M, X, Y) = map(int, input().split())
	(mn, mx, diff) = (min(N, M), max(N, M), abs(N - M))
	zigzag = (mn + diff - 1) * Y
	if diff & 1:
		zigzag += X - Y
	print(min(zigzag, (mn - 1) * Y + diff * X, (mn + mx - 2) * X))


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


t = int(input())
for k in range(t):
	(n, m, x, y) = map(int, input().split())
	d = 2 * x if 2 * x < y else y
	s = 2 * x if 2 * x < 2 * y else 2 * y
	p = n - 1 if n < m else m - 1
	q = n - p - 1 if n > m else m - p - 1
	q = q // 2
	total = p * d + s * q
	if n - m & 1 != 0:
		total += x
	print(total)


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


import sys
input = sys.stdin.readline

def I():
	return input().strip()

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import copy, string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, chain, combinations, groupby
from operator import itemgetter
from types import GeneratorType
from typing import Iterable, TypeVar, Union
for _ in range(II()):
	(n, m, x, y) = LI()
	(n, m) = (n - 1, m - 1)
	ans = min((n + m) * x, abs(n - m) * x + min(n, m) * y)
	if n >= 1 and m >= 1:
		var = min(n, m) * y + abs(n - m) // 2 * 2 * y + abs(n - m) % 2 * x
		ans = min(ans, var)
	print(ans)


import sys
input = sys.stdin.readline
print = sys.stdout.write

def myfunc(m, n, x, y):
	if m == 1:
		return (n - 1) * x
	if 2 * x <= y:
		return (m - 1 + n - 1) * x
	ans = (m - 1) * y
	if 2 * x <= 2 * y:
		return ans + (n - m) * x
	if (n - m) % 2 == 0:
		return ans + (n - m) * y
	return ans + (n - 1 - m) * y + x
for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	(min_nm, ans) = (min(n, m), 0)
	if m == n:
		ans = min((n - 1) * y, (n - 1) * 2 * x)
	elif m > n:
		(m, n) = (n, m)
		ans = myfunc(m, n, x, y)
	else:
		ans = myfunc(m, n, x, y)
	print(str(ans) + '\n')


tc = int(input())
while tc > 0:
	(n, m, x, y) = map(int, input().split())
	ans_one = (n + m - 2) * x
	ans_two = (min(n, m) - 1) * y + abs(n - m) * x
	remain = abs(n - m)
	if remain % 2 == 0:
		ans_three = (min(n, m) - 1) * y + remain * y
	else:
		ans_three = (min(n, m) - 1) * y + (remain - 1) * y + remain % 2 * x
	print(min(min(ans_one, ans_two), ans_three))
	tc -= 1


try:
	for i in range(int(input())):
		(n, m, x, y) = map(int, input().split())
		shortpath = (n + m - 2) * x
		diff = abs(n - m)
		shortpath = min(shortpath, (min(n, m) - 1) * y + diff * x)
		shortpath = min(shortpath, (min(n, m) - 1) * y + diff // 2 * 2 * y + diff % 2 * x)
		print(shortpath)
except:
	pass


def func(n1, m1, x, y):
	if n1 == 1 or m1 == 1:
		return (n1 + m1 - 2) * x
	elif y < x:
		if (n1 - m1) % 2 == 0:
			return (n1 - 1) * y
		else:
			return (n1 - 2) * y + x
	elif y < 2 * x:
		return (m1 - 1) * y + (n1 - m1) * x
	elif y >= 2 * x:
		return (n1 + m1 - 2) * x
n = int(input())
for i in range(n):
	(n, m, x, y) = list(map(int, input().split()))
	n1 = max(n, m)
	m1 = min(n, m)
	print(func(n1, m1, x, y))


def solve(n, m, x, y):
	if y >= 2 * x:
		return (n + m - 2) * x
	if y > x and y < 2 * x:
		return (min(n, m) - 1) * y + abs(n - m) * x
	if y <= x and abs(n - m) % 2 == 0:
		return (min(n, m) - 1) * y + abs(n - m) * y
	if y <= x and abs(n - m) % 2 == 1:
		return (min(n, m) - 1) * y + (abs(n - m) - 1) * y + x
for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	print(solve(n, m, x, y))


t = int(input())
for _ in range(t):
	(n, m, x, y) = map(int, input().split())
	dif = abs(m - n)
	if m < n:
		(m, n) = (n, m)
	c1 = x * (m - 1 + (n - 1))
	c2 = y * (n - 1) + dif * x
	c3 = y * (n - 1) + dif // 2 * 2 * y + dif % 2 * x
	print(min(c1, c2, c3))


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


t = int(input())
for _ in range(t):
	(n, m, x, y) = map(int, input().split())
	w1 = (n + m - 2) * x
	w2 = 0
	if n > m:
		w2 += (m - 1) * y
	else:
		w2 += (n - 1) * y
	w3 = w2 + abs(n - m) * x
	w4 = y * min(n - 1, m - 1) + abs(n - m) // 2 * 2 * y + abs(n - m) % 2 * x
	print(min(w1, w4, w3))


import sys
t = sys.stdin.readline()
t = int(t[0])
l = sys.stdin.readlines()
for k in l:
	(n, m, x, y) = map(int, k.split(' '))
	if m > n:
		(n, m) = (m, n)
	ans = 0
	if n == 1 or m == 1:
		ans = (n + m - 2) * x
	elif y < x:
		if n % 2 == m % 2:
			ans = (n - 1) * y
		else:
			ans = (n - 2) * y + x
	elif y < 2 * x:
		ans = (m - 1) * y + (n - m) * x
	else:
		ans = (n + m - 2) * x
	sys.stdout.write(str(ans) + '\n')


for u in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	total = n + m - 2
	if n > m:
		(n, m) = (m, n)
	diff = m - n
	ans1 = x * total
	ans2 = y * (n - 1) + x * diff
	ans3 = y * (n - 1) + 2 * (diff // 2) * y + x * (diff % 2)
	print(min(ans3, min(ans1, ans2)))


for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	p = (min(n, m) - 1) * y
	q = max(m, n) - min(m, n)
	p += q // 2 * y * 2 + q % 2 * x
	l = [(n + m - 2) * x, (min(n, m) - 1) * y + (max(n, m) - min(n, m)) * x, p]
	print(min(l))


T = int(input())
myinp1 = []
for i in range(T):
	myinp1.append(input())
for i in range(T):
	inp = myinp1[i].split()
	N = int(inp[0])
	M = int(inp[1])
	X = int(inp[2])
	Y = int(inp[3])
	if N > M:
		(N, M) = (M, N)
	diff = M - N
	cost1 = (N - 1 + M - 1) * X
	cost2 = (N - 1) * Y + diff * X
	cost3 = (N - 1) * Y + int(diff / 2) * 2 * Y + diff % 2 * X
	ans = min(cost1, cost2, cost3)
	print(ans)


from sys import stdin
input = stdin.readline
t = int(input())
for i in range(t):
	(n, m, x, y) = map(int, input().split())
	if n > m:
		(n, m) = (m, n)
	d = n - 1
	moves = n + m - 2
	res = moves * x
	left = moves - 2 * d
	hops = left // 2
	extra = left % 2
	res = min(res, d * y + left * x)
	if n > 1:
		res = min(res, d * y + 2 * hops * y + extra * x)
	print(res)


import sys, bisect, math
from itertools import permutations
from itertools import combinations
from itertools import combinations_with_replacement
import heapq
from collections import deque
from collections import Counter
input = sys.stdin.readline

def log(*message):
	if not online:
		for i in message:
			print(i, end=' ')
		print()

def intersection(a: list, b: list):
	return list(set(a).intersection(b))

def union(a: list, b: list):
	return list(set(a + b))

def binarySearchFromLeft(a: list, x: any):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return 0

def binarySearchFromRight(a: list, x: any):
	i = bisect.bisect_right(a, x)
	if i != len(a) + 1 and a[i - 1] == x:
		return i - 1
	else:
		return 0

def lintinput(x=' '):
	return [int(i) for i in input().split(x)]

def lstrinput():
	return [i for i in input().split()]

def intinput():
	return int(input())

def XOR(*elements):
	return eval('^'.join([str(i) for i in elements]))

def AND(*elements):
	return eval('&'.join([str(i) for i in elements]))

def OR(*elements):
	return eval('|'.join([str(i) for i in elements]))

def NOT(x):
	return ~x

def BitwiseLeftShift(a, b):
	return a << b

def BitwiseRightShift(a, b):
	return a >> b
online = False

def testCase():
	return range(int(input()))

def solve(*args):
	ans = 'answer'
	return ans
for _ in testCase():
	(n, m, x, y) = lintinput()
	a1 = (n + m - 2) * x
	d = abs(n - m)
	if d & 1 == 0:
		a2 = min(n - 1, m - 1) * y + d * y
	else:
		a2 = min(n - 1, m - 1) * y + (d - 1) * y + x
	a3 = min(n - 1, m - 1) * y + d * x
	print(min(a1, a2, a3))


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	dir_cost = (n + m - 2) * x
	di_cost = (min(n, m) - 1) * y
	extra_steps = abs(n - m)
	if extra_steps % 2 == 0:
		di_cost += extra_steps * min(x, y)
	else:
		di_cost += min(extra_steps * x, x + (extra_steps - 1) * y)
	ans = min(dir_cost, di_cost)
	sys.stdout.write(str(ans) + '\n')


cases = int(input())
final = []
for _ in range(cases):
	(n, m, x, y) = map(int, input().split())
	if x * 2 < y or m == 1 or n == 1:
		ans = (n + m - 2) * x
	else:
		max_diag = min(n - 1, m - 1)
		dif = abs(n - m)
		ans1 = max_diag * y + dif * x
		ans2 = max_diag * y + (dif // 2 * y * 2 + dif % 2 * x)
		ans = min(ans1, ans2)
	final.append(ans)
for a in final:
	print(a)


from sys import stdin
input = stdin.readline
t = int(input())
for i in range(t):
	(n, m, x, y) = map(int, input().split())
	(n, m) = (max(n, m), min(n, m))
	ans = 0
	ans = ans + min((m - 1) * y, (2 * m - 2) * x)
	ans = ans + min((n - m) // 2 * 2 * y + (n - m) % 2 * x, (n - m) * x)
	print(ans)


import sys
input = sys.stdin.readline

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

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	(n, m, x, y) = ma()
	fi = (n + m - 2) * x
	if n <= m:
		se = max(0, m - n) * x + (n - 1) * y
		if (m - n) % 2:
			th = x
		else:
			th = 0
		th += (n - 1) * y
		th += (m - n - (m - n) % 2) * y
		se = min(se, th)
	else:
		se = max(0, n - m) * x + (m - 1) * y
		if (n - m) % 2:
			th = x
		else:
			th = 0
		th += (m - 1) * y
		th += (n - m - (n - m) % 2) * y
		se = min(se, th)
	print(min(fi, se))


import sys
for _ in range(int(input())):
	(n, m, x, y) = map(int, sys.stdin.readline().split())
	yg2x = (n + m - 2) * x
	x2gy = (min(n, m) - 1) * y + abs(n - m) * x
	xgyd2 = (min(n, m) - 1 + abs(n - m)) * y
	xgynd2 = (min(n, m) - 1 + abs(n - m) - 1) * y + x
	if y > 2 * x:
		sys.stdout.write(str(yg2x) + '\n')
	elif y < x:
		if abs(n - m) % 2 == 0:
			sys.stdout.write(str(xgyd2) + '\n')
		else:
			sys.stdout.write(str(xgynd2) + '\n')
	else:
		sys.stdout.write(str(x2gy) + '\n')


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())
n = sys.stdin.readline()

def solve(n, m, x, y):
	if y >= 2 * x:
		return (n + m - 2) * x
	if y > x and y < 2 * x:
		return (min(n, m) - 1) * y + abs(n - m) * x
	if y <= x and abs(n - m) % 2 == 0:
		return (min(n, m) - 1) * y + abs(n - m) * y
	if y <= x and abs(n - m) % 2 == 1:
		return (min(n, m) - 1) * y + (abs(n - m) - 1) * y + x
for i in range(int(n)):
	(n, m, x, y) = get_ints()
	print(solve(n, m, x, y))


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())
t = int(input())
while t > 0:
	t -= 1
	(n, m, x, y) = get_ints()
	dis = 0
	if m > n:
		(m, n) = (n, m)
	if 2 * x >= y:
		dis = (m - 1) * y
	else:
		dis += 2 * x * (m - 1)
	if y < x:
		if (n - m) % 2 == 0:
			dis += y * (n - m)
		else:
			dis += y * (n - m - 1) + x
	else:
		dis += (n - m) * x
	print(dis)


from sys import stdin
input = stdin.readline

def answer():
	val1 = (n + m - 2) * x
	diff = abs(n - m)
	if diff & 1 == 0:
		val2 = min(n - 1, m - 1) * y + diff * y
	else:
		val2 = min(n - 1, m - 1) * y + (diff - 1) * y + x
	val3 = min(n - 1, m - 1) * y + diff * x
	return min(val1, val2, val3)
for T in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	print(answer())