Victoria is splurging on expensive accessories at her favorite stores. Each store stocks $\mbox{A}$ types of accessories, where the $i^{\mbox{th}}$ accessory costs $\boldsymbol{i}$ dollars ($1\leq i\leq A$). Assume that an item's type identifier is the same as its cost, and the store has an unlimited supply of each accessory.

Victoria wants to purchase a total of $L$ accessories according to the following rule:

Any $N$-element subset of the purchased items must contain at least $\mbox{D}$ different types of accessories. 

For example, if $L=6$, $N=3$, and $D=2$, then she must choose $\boldsymbol{6}$ accessories such that any subset of $3$ of the $\boldsymbol{6}$ accessories will contain at least $2$ distinct types of items. 

Given $L$, $\mbox{A}$, $N$, and $\mbox{D}$ values for $\mathbf{T}$ shopping trips, find and print the maximum amount of money that Victoria can spend during each trip; if it's not possible for Victoria to make a purchase during a certain trip, print SAD instead. You must print your answer for each trip on a new line.

Input Format

The first line contains an integer, $\mathbf{T}$, denoting the number of shopping trips. 

Each of the $\mathbf{T}$ subsequent lines describes a single shopping trip as four space-separated integers corresponding to $L$, $\mbox{A}$, $N$, and $\mbox{D}$, respectively.

Constraints

$1\leq T\leq10^6$  
$1\leq D\leq N\leq L\leq10^5$  
$1\leq A\leq10^9$  
The sum of the $L$'s for all $\mathbf{T}$ shopping trips $\leq8\cdot10^{6}$.  

Output Format

For each shopping trip, print a single line containing either the maximum amount of money Victoria can spend; if there is no collection of items satisfying her shopping rule for the trip's $L$, $\mbox{A}$, $N$, and $\mbox{D}$ values, print SAD instead.

Sample Input
2
6 5 3 2
2 1 2 2

Sample Output
24
SAD

Explanation

Shopping Trip 1: 

We know that:

Victoria wants to buy $L=6$ accessories. 
The store stocks the following $A=5$ types of accessories: $\{1,2,3,4,5\}$. 
For any grouping of $N=3$ of her $L$ accessories, there must be at least $D=2$ distinct types of accessories.  

Victoria can satisfy her shopping rule and spend the maximum amount of money by purchasing the following set of accessories: $\{3,4,5,5,4,3\}$. The total cost is $3+4+5+5+4+3=24$, so we print $24$ on a new line.

Shopping Trip 2: 

We know that:

Victoria wants to buy $L=2$ accessories.
The store stocks $A=1$ type of accessory: $\{1\}$. 
For any grouping of $N=2$ of her $L$ accessories, there must be at least $D=2$ distinct types of accessories. 

Because the store only carries $1$ type of accessory, Victoria cannot make a purchase satisfying the constraint that there be at least $D=2$ distinct types of accessories. Because Victoria will not purchase anything, we print that she is SAD on a new line.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


for _ in range(int(input())):
	(L, A, N, D) = [int(i) for i in input().split(' ')]
	if D == 1:
		print(A * L)
		continue
	n_rest_max = (N - 1) // (D - 1)
	max_result = -1
	for n_rest in range(n_rest_max, 0, -1):
		n_highest = N + (n_rest - 1) - n_rest * (D - 1)
		rest = (L - n_highest) // n_rest
		n_lowest = (L - n_highest) % n_rest
		if rest > A - 1 or (rest == A - 1 and n_lowest > 0):
			break
		result = n_highest * A + n_rest * (2 * A - rest - 1) * rest // 2 + n_lowest * (A - rest - 1)
		if max_result >= result:
			break
		max_result = result
	if max_result == -1:
		print('SAD')
	else:
		print(max_result)


import sys
from math import floor, ceil

def f(a, L, A, N, D):
	x = N - 1 - a * (D - 1)
	L_bar = L - x
	q = L_bar // a
	r = L_bar % a
	return A * L - q * (L_bar + r - a) // 2
T = int(input().strip())
for a0 in range(T):
	(L, A, N, D) = input().strip().split(' ')
	(L, A, N, D) = [int(L), int(A), int(N), int(D)]
	if D == 1:
		print(L * A)
	elif A <= D - 1:
		print('SAD')
	else:
		amin = ceil((L - N + 1) / (A - D + 1))
		amax = floor((N - 1) / (D - 1))
		if amin > amax:
			print('SAD')
		else:
			print(max((f(a, L, A, N, D) for a in range(amin, amax + 1))))


def f(l, a, n, j, x, r):
	if r > 0:
		j += 1
		x += 1
	stop = l - r * x if r > 0 else 0
	sum = j * a
	a -= 1
	l -= j
	while l > 0:
		if l == stop:
			x -= 1
		if l - x < 0:
			x = l
		sum += a * x
		a -= 1
		if a < 0:
			return -1
		l -= x
	return sum
t = int(input())
for x in range(t):
	(l, a, n, d) = list(map(int, input().split()))
	if d == 1:
		print(l * a)
	elif d > a:
		print('SAD')
	elif d == n:
		res = 'SAD' if l > a else sum(range(a, a - l, -1))
		print(res)
	else:
		m = n - d + 1
		q = int((n - 1) / (d - 1))
		r = (n - 1) % (d - 1)
		maxs = f(l, a, n, q, q, r)
		for j in range(m, q, -1):
			x = int((n - j - 1) / (d - 2))
			rem = (n - j - 1) % (d - 2)
			if rem != 0:
				continue
			maxs = max(maxs, f(l, a, n, j, x, rem))
		if maxs < 0:
			print('SAD')
		else:
			print(maxs)


T = int(input())
for _ in range(T):
	(L, A, N, D) = [int(x) for x in input().strip().split()]
	if N < D or N > L or A < D:
		print('SAD')
		continue
	if D == 1:
		print(L * A)
		continue
	max = 0
	a2Max = int((N - 1) / (D - 1))
	for a2 in range(a2Max, 0, -1):
		a1 = N + (a2 - 1) - a2 * (D - 1)
		n = int((L - a1) / a2)
		a3 = (L - a1) % a2
		if n > A - 1 or (n == A - 1 and a3 > 0):
			break
		sum = int(A * a1 + (A - 1 + A - n) * n / 2 * a2 + a3 * (A - n - 1))
		if sum <= max:
			break
		max = sum
	if max == 0:
		print('SAD')
	else:
		print(int(max))


from itertools import *

def F(L, A, N, D):
	res = 0
	bmax = (N - 1) // (D - 1)
	for b in range(bmax, 0, -1):
		c = N + (b - 1) - b * (D - 1)
		(x, y) = divmod(L - c, b)
		if x > A - 1 or (x == A - 1 and y):
			break
		r = A * c + (A - 1 + A - x) * x * b // 2 + y * (A - x - 1)
		if r <= res:
			break
		res = r
	return res
T = int(input().strip())
for _ in range(T):
	(L, A, N, D) = map(int, input().strip().split())
	if D > A or N > L or D > N:
		print('SAD')
	elif D == 1:
		print(A * L)
	else:
		res = F(L, A, N, D)
		if res:
			print(res)
		else:
			print('SAD')


T = int(input().strip())
res = []
for a0 in range(T):
	(L, A, N, D) = input().strip().split(' ')
	(L, A, N, D) = [int(L), int(A), int(N), int(D)]
	if N < D or N > L or A < D:
		res.append('SAD')
		continue
	if D == 1:
		res.append(str(L * A))
		continue
	mmax = 0
	a2Max = (N - 1) // (D - 1)
	a2 = a2Max
	while a2 >= 1:
		a1 = N + (a2 - 1) - a2 * (D - 1)
		n = (L - a1) // a2
		a3 = (L - a1) % a2
		if n > A - 1 or (n == A - 1 and a3 > 0):
			break
		ssum = A * a1 + (A - 1 + A - n) * n // 2 * a2 + a3 * (A - n - 1)
		if ssum <= mmax:
			break
		mmax = ssum
		a2 -= 1
	if mmax == 0:
		res.append('SAD')
	else:
		res.append(str(mmax))
print('\n'.join(res))


import sys
sys.setrecursionlimit(10 ** 5 + 10)

def get_answer(L, A, N, D, old_answer, it):
	L_preserve = L
	old_answer = -1
	new_answer = 0
	it = 0
	if D == 1:
		return L * A
	while new_answer > old_answer:
		old_answer = new_answer
		L = L_preserve
		num_per = (N - 1) // (D - 1) - it
		it += 1
		if num_per <= 0:
			new_answer = 0
			break
		num_first = min(L - D + 1, N - 1 - num_per * (D - 2))
		profit = num_first * A
		L -= num_first
		for x in range(1, A):
			if L > num_per:
				profit += num_per * (A - x)
			else:
				profit += L * (A - x)
				old_answer = new_answer
				new_answer = profit
				break
			L -= num_per
	ret = max(old_answer, new_answer)
	if not ret:
		return 'SAD'
	return ret
T = int(input().strip())
for a0 in range(T):
	(L, A, N, D) = input().strip().split(' ')
	(L, A, N, D) = [int(L), int(A), int(N), int(D)]
	print(get_answer(L, A, N, D, 0, 0))


from itertools import *

def F(L, A, N, D):
	res = 0
	bmax = (N - 1) // (D - 1)
	for b in range(bmax, 0, -1):
		c = N + (b - 1) - b * (D - 1)
		(x, y) = divmod(L - c, b)
		if x > A - 1 or (x == A - 1 and y):
			break
		r = A * c + (A - 1 + A - x) * x * b // 2 + y * (A - x - 1)
		if r <= res:
			break
		res = r
	return res
T = int(input().strip())
for _ in range(T):
	(L, A, N, D) = map(int, input().strip().split())
	if D > A or N > L or D > N:
		print('SAD')
	elif D == 1:
		print(A * L)
	else:
		res = F(L, A, N, D)
		if res:
			print(res)
		else:
			print('SAD')


t = int(input())
for _ in range(t):
	(l, a, n, d) = input().split()
	L = int(l)
	A = int(a)
	N = int(n)
	D = int(d)
	if N > L or D > N:
		print('SAD')
		continue
	if D == 1:
		print(A * L)
		continue
	max_count = int((N - 1) / (D - 1))
	amount = 0
	for mid_count in range(max_count, 0, -1):
		large_count = N - (D - 1) * mid_count + mid_count - 1
		num_of_mid_acc = int((L - large_count) / mid_count)
		least_count = (L - large_count) % mid_count
		if num_of_mid_acc > A - 1 or (num_of_mid_acc == A - 1 and least_count > 0):
			break
		this_amount = A * large_count + int((A - 1 + A - num_of_mid_acc) * num_of_mid_acc / 2) * mid_count + least_count * (A - num_of_mid_acc - 1)
		if this_amount <= amount:
			break
		amount = this_amount
	if amount > 0:
		print(amount)
	else:
		print('SAD')


def sol(L, A, N, D):
	if A < D or N < D or L < N:
		print('SAD')
	elif D == 1:
		print(L * A)
	else:
		m = 0
		cm = (N - 1) // (D - 1)
		for c in range(cm, 0, -1):
			a1 = N + (c - 1) - c * (D - 1)
			n = (L - a1) // c
			h = (L - a1) % c
			if n > A - 1 or (n == A - 1 and h > 0):
				break
			s = A * a1 + (A - 1 + A - n) * n // 2 * c + h * (A - n - 1)
			if s <= m:
				break
			m = s
		print('SAD' if m == 0 else m)
for a0 in range(int(input())):
	sol(*[int(x) for x in input().split(' ')])


from itertools import *

def F(L, A, N, D):
	res = 0
	bmax = (N - 1) // (D - 1)
	for b in range(bmax, 0, -1):
		c = N + (b - 1) - b * (D - 1)
		(x, y) = divmod(L - c, b)
		if x > A - 1 or (x == A - 1 and y):
			break
		r = A * c + (A - 1 + A - x) * x * b // 2 + y * (A - x - 1)
		if r <= res:
			break
		res = r
	return res
T = int(input().strip())
for _ in range(T):
	(L, A, N, D) = map(int, input().strip().split())
	if D > A or N > L or D > N:
		print('SAD')
	elif D == 1:
		print(A * L)
	else:
		res = F(L, A, N, D)
		if res:
			print(res)
		else:
			print('SAD')


import sys
from math import floor, ceil

def f(a, L, A, N, D):
	x = N - 1 - a * (D - 1)
	L_bar = L - x
	q = L_bar // a
	r = L_bar % a
	return A * L - q * (L_bar + r - a) // 2
T = int(input().strip())
for a0 in range(T):
	(L, A, N, D) = input().strip().split(' ')
	(L, A, N, D) = [int(L), int(A), int(N), int(D)]
	if D == 1:
		print(L * A)
	elif A <= D - 1:
		print('SAD')
	else:
		amin = ceil((L - N + 1) / (A - D + 1))
		amax = floor((N - 1) / (D - 1))
		if amin > amax:
			print('SAD')
		else:
			print(max((f(a, L, A, N, D) for a in range(amin, amax + 1))))


for _ in range(int(input())):
	(L, A, N, D) = [int(i) for i in input().split(' ')]
	if D == 1:
		print(A * L)
		continue
	n_rest_max = (N - 1) // (D - 1)
	max_result = -1
	for n_rest in range(n_rest_max, 0, -1):
		n_highest = N + (n_rest - 1) - n_rest * (D - 1)
		rest = (L - n_highest) // n_rest
		n_lowest = (L - n_highest) % n_rest
		if rest > A - 1 or (rest == A - 1 and n_lowest > 0):
			break
		result = n_highest * A + n_rest * (2 * A - rest - 1) * rest // 2 + n_lowest * (A - rest - 1)
		if max_result >= result:
			break
		max_result = result
	if max_result == -1:
		print('SAD')
	else:
		print(max_result)


for i in range(0, int(input())):
	(n, t, m, d) = map(int, input().split())
	ans = 0
	if d == 1:
		ans = n * t
	else:
		temp = (m - 1) // (d - 1)
		for mid in range(temp, 0, -1):
			maxx = mid + (m - mid * (d - 1)) - 1
			end = (n - maxx) % mid
			terms = (n - maxx) // mid
			if terms > t - 1 or (terms == t - 1 and end > 0):
				break
			else:
				temp_am = maxx * t + terms * (t - 1 + t - terms) * (mid / 2) + end * (t - terms - 1)
				if temp_am > ans:
					ans = temp_am
				else:
					break
	if ans != 0:
		print(int(ans))
	else:
		print('SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


from itertools import *

def F(L, A, N, D):
	res = 0
	bmax = (N - 1) // (D - 1)
	for b in range(bmax, 0, -1):
		c = N + (b - 1) - b * (D - 1)
		(x, y) = divmod(L - c, b)
		if x > A - 1 or (x == A - 1 and y):
			break
		r = A * c + (A - 1 + A - x) * x * b // 2 + y * (A - x - 1)
		if r <= res:
			break
		res = r
	return res
T = int(input().strip())
for _ in range(T):
	(L, A, N, D) = map(int, input().strip().split())
	if D > A or N > L or D > N:
		print('SAD')
	elif D == 1:
		print(A * L)
	else:
		res = F(L, A, N, D)
		if res:
			print(res)
		else:
			print('SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import os
import sys
import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import math

def anii(odhu):
	if odhu <= 0:
		return 0
	modhati = nenu - odhu * (dig - 2) - 1
	gar = (kjm - modhati) // odhu
	if modhati < odhu or avunu - gar <= 0 or modhati + odhu * (avunu - 1) < kjm:
		return 0
	konchem = int((2 * (avunu - 1) - gar + 1) / 2 * gar)
	left = (avunu - gar - 1) * (-gar * odhu + kjm - modhati)
	return modhati * avunu + konchem * odhu + left
for _ in range(int(input())):
	(kjm, avunu, nenu, dig) = map(int, input().strip().split())
	if dig == 1:
		print(kjm * avunu)
		continue
	if dig == 2:
		n1 = nenu - 1
		if n1 * avunu >= kjm:
			ln1 = kjm // n1
			print(int((2 * avunu + 1 - ln1) / 2 * ln1 * n1) + (avunu - ln1) * (kjm - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if avunu == 1:
		print('SAD')
		continue
	if avunu == 2:
		if dig == 2 and (nenu - dig + 1) * 2 >= kjm:
			print(nenu - dig + kjm + 1)
			continue
		else:
			print('SAD')
			continue
	odhu = math.ceil((kjm - avunu - nenu + dig) / (avunu - 2))
	if odhu > nenu - dig:
		print('SAD')
		continue
	else:
		aunty = int(math.sqrt((2 - 3 * dig + dig * dig) * (1 + kjm - nenu) * (1 + kjm - nenu)) / (2 - 3 * dig + dig * dig)) + 1
		if (dig == 3 or (dig == 4 and avunu > 2)) or (dig > 4 and avunu > dig - 2):
			aunty = max(int((1 + kjm - nenu) / (2 + avunu - dig)), aunty)
			aunty = min(int((nenu - 1) / (dig - 1)), aunty)
			if dig == 3 or avunu > dig - 1:
				aunty = max(int((1 + kjm - nenu) / (1 + avunu - dig)), aunty)
			elif dig > 3 and avunu < dig - 1:
				aunty = min(int((1 + kjm - nenu) / (1 + avunu - dig)), aunty)
		max_haul = max(anii(aunty - 1), anii(aunty), anii(aunty + 1))
		print(max_haul if max_haul else 'SAD')


import math

def final(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	result = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + result * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(final(argmax - 1), final(argmax), final(argmax + 1))
		print(max_haul if max_haul else 'SAD')


import os
import sys
import math

def total(g):
	if g <= 0:
		return 0
	first = N - g * (D - 2) - 1
	f = (L - first) // g
	if first < g or A - f <= 0 or first + g * (A - 1) < L:
		return 0
	partial = int((2 * (A - 1) - f + 1) / 2 * f)
	left = (A - f - 1) * (-f * g + L - first)
	return first * A + partial * g + left
for _ in range(int(input())):
	(L, A, N, D) = map(int, input().strip().split())
	if D == 1:
		print(L * A)
		continue
	if D == 2:
		n1 = N - 1
		if n1 * A >= L:
			ln1 = L // n1
			print(int((2 * A + 1 - ln1) / 2 * ln1 * n1) + (A - ln1) * (L - ln1 * n1))
			continue
		else:
			print('SAD')
			continue
	if A == 1:
		print('SAD')
		continue
	if A == 2:
		if D == 2 and (N - D + 1) * 2 >= L:
			print(N - D + L + 1)
			continue
		else:
			print('SAD')
			continue
	g = math.ceil((L - A - N + D) / (A - 2))
	if g > N - D:
		print('SAD')
		continue
	else:
		argmax = int(math.sqrt((2 - 3 * D + D * D) * (1 + L - N) * (1 + L - N)) / (2 - 3 * D + D * D)) + 1
		if (D == 3 or (D == 4 and A > 2)) or (D > 4 and A > D - 2):
			argmax = max(int((1 + L - N) / (2 + A - D)), argmax)
			argmax = min(int((N - 1) / (D - 1)), argmax)
			if D == 3 or A > D - 1:
				argmax = max(int((1 + L - N) / (1 + A - D)), argmax)
			elif D > 3 and A < D - 1:
				argmax = min(int((1 + L - N) / (1 + A - D)), argmax)
		max_haul = max(total(argmax - 1), total(argmax), total(argmax + 1))
		print(max_haul if max_haul else 'SAD')