Meka-Naruto plays a computer game. His character has the following ability: given an enemy hero, deal $a$ instant damage to him, and then heal that enemy $b$ health points at the end of every second, for exactly $c$ seconds, starting one second after the ability is used. That means that if the ability is used at time $t$, the enemy's health decreases by $a$ at time $t$, and then increases by $b$ at time points $t + 1$, $t + 2$, ..., $t + c$ due to this ability.

The ability has a cooldown of $d$ seconds, i. e. if Meka-Naruto uses it at time moment $t$, next time he can use it is the time $t + d$. Please note that he can only use the ability at integer points in time, so all changes to the enemy's health also occur at integer times only.

The effects from different uses of the ability may stack with each other; that is, the enemy which is currently under $k$ spells gets $k\cdot b$ amount of heal this time. Also, if several health changes occur at the same moment, they are all counted at once.

Now Meka-Naruto wonders if he can kill the enemy by just using the ability each time he can (that is, every $d$ seconds). The enemy is killed if their health points become $0$ or less. Assume that the enemy's health is not affected in any way other than by Meka-Naruto's character ability. What is the maximal number of health points the enemy can have so that Meka-Naruto is able to kill them?


-----Input-----

The first line contains an integer $t$ ($1\leq t\leq 10^5$) standing for the number of testcases.

Each test case is described with one line containing four numbers $a$, $b$, $c$ and $d$ ($1\leq a, b, c, d\leq 10^6$) denoting the amount of instant damage, the amount of heal per second, the number of heals and the ability cooldown, respectively.


-----Output-----

For each testcase in a separate line print $-1$ if the skill can kill an enemy hero with an arbitrary number of health points, otherwise print the maximal number of health points of the enemy that can be killed.


-----Example-----
Input
7
1 1 1 1
2 2 2 2
1 2 3 4
4 3 2 1
228 21 11 3
239 21 11 3
1000000 1 1000000 1

Output
1
2
1
5
534
-1
500000500000



-----Note-----

In the first test case of the example each unit of damage is cancelled in a second, so Meka-Naruto cannot deal more than 1 damage.

In the fourth test case of the example the enemy gets:  $4$ damage ($1$-st spell cast) at time $0$;  $4$ damage ($2$-nd spell cast) and $3$ heal ($1$-st spell cast) at time $1$ (the total of $5$ damage to the initial health);  $4$ damage ($3$-nd spell cast) and $6$ heal ($1$-st and $2$-nd spell casts) at time $2$ (the total of $3$ damage to the initial health);  and so on. 

One can prove that there is no time where the enemy gets the total of $6$ damage or more, so the answer is $5$. Please note how the health is recalculated: for example, $8$-health enemy would not die at time $1$, as if we first subtracted $4$ damage from his health and then considered him dead, before adding $3$ heal.

In the sixth test case an arbitrarily healthy enemy can be killed in a sufficient amount of time.

In the seventh test case the answer does not fit into a 32-bit integer type.

Difficulty: HARD
Tags: Sorting

Mathematics

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
import sys
s = sys.stdin.read().split()
p = 0

def getSm(k, a, b, c, d):
	return (k + 1) * a - (k * (k + 1) >> 1) * b * d
t = int(s[p])
p += 1
res = []
for _ in range(t):
	a = int(s[p])
	p += 1
	b = int(s[p])
	p += 1
	c = int(s[p])
	p += 1
	d = int(s[p])
	p += 1
	if a - b * c > 0:
		res.append(-1)
	elif d >= c:
		res.append(a)
	else:
		dn = 0
		up = int(1000000.0) + 1
		while up - dn > 1:
			md = up + dn >> 1
			if getSm(md, a, b, c, d) < getSm(md + 1, a, b, c, d):
				dn = md
			else:
				up = md
		ans = max(a, getSm(dn, a, b, c, d), getSm(up, a, b, c, d))
		res.append(ans)
print('\n'.join(map(str, res)))


import sys, io, os
Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
o = []
for _ in range(int(Z())):
	(a, b, c, d) = map(int, Z().split())
	if a > b * c:
		o += [-1]
	elif d > c:
		o += [a]
	else:
		v = a // (b * d)
		o += [(v + 1) * a - b * d * (v * (v + 1)) // 2]
print('\n'.join(map(str, o)))


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.buffer.readline
	for _ in range(int(input())):
		(a, b, c, d) = map(int, input().split())
		if a > b * c:
			print(-1)
			continue
		if d > c:
			print(a)
			continue
		k = a // (b * d)
		print((a + (a - k * d * b)) * (k + 1) // 2)
main()


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import sys
X = []
t = int(input())
for tests in range(t):
	(a, b, c, d) = map(int, input().split())
	if a > b * c:
		X.append(-1)
		continue
	left = 1
	right = c // d + 1

	def calc(x):
		return -a * x + b * d * x * (x - 1) // 2
	while right > left:
		mid = (right + left) // 2
		if calc(mid) < calc(mid + 1):
			right = mid
		else:
			left = mid + 1
	X.append(-min(calc(left), calc(right)))
sys.stdout.write('\n'.join(map(str, X)))


import os, sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		(a, b, c, d) = map(int, input().split())
		if a > b * c:
			print(-1)
		elif a == b * c:
			if d >= c:
				print(a)
			elif d >= (c + 1) // 2:
				print(2 * a - d * b)
			else:
				x = c // d
				print((x + 1) * a - x * (x + 1) * d * b // 2)
		elif d >= c:
			print(a)
		elif a <= d * b:
			print(a)
		else:
			x = a // b // d
			print((x + 1) * a - x * (x + 1) * d * b // 2)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
for _ in range(II()):
	(a, b, c, d) = MI()
	if a > b * c:
		print(-1)
		continue
	t = a // (b * d)
	k1 = a - b * d
	r = -b * d
	kt = k1 + r * (t - 1)
	s = (k1 + kt) * t // 2
	ans = a + s
	print(ans)


from sys import stdin
t = int(input())
for i_t in range(t):
	(a, b, c, d) = map(int, stdin.readline().split())
	if b * c < a:
		result = -1
	else:
		i_hit = (a + b * d - 1) // (b * d) - 1
		i_hit = min(i_hit, (c - 1) // d)
		result = a * (i_hit + 1) - b * d * i_hit * (i_hit + 1) // 2
	print(result)


def solve(a, b, c, d):
	if a > c * b:
		return -1
	if c <= d:
		return a
	rt = a // b // d + 1
	p = rt * (rt - 1)
	db = d * b
	y = rt * a
	n = p // 2 * db
	return y - n

def main():
	t = int(input())
	for _ in range(t):
		(a, b, c, d) = map(int, input().split())
		print(solve(a, b, c, d))
main()


import sys
input = sys.stdin.readline

def solve_case():
	(a, b, c, d) = [int(x) for x in input().split()]
	if a > b * c:
		print(-1)
	else:
		k = a // (b * d)
		print(a * (k + 1) - k * (k + 1) // 2 * b * d)

def main():
	for _ in range(int(input())):
		solve_case()
main()


import sys
input = sys.stdin.readline
from collections import defaultdict
mod = 10 ** 9 + 7
INF = float('inf')

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

def Binary_Search(a, b, c, d):
	left = 0
	right = int(c // d) + 1
	itr = 0
	while left <= right:
		mid = (left + right) // 2
		if a >= mid * b * d:
			itr = max(itr, mid)
			left = mid + 1
		else:
			right = mid - 1
	heal = itr * (itr + 1) // 2 * b * d
	damage = (itr + 1) * a
	ans = damage - heal
	return ans

def main():
	T = int(input())
	for _ in range(T):
		(a, b, c, d) = getlist()
		if a > b * c:
			print(-1)
		else:
			ans = Binary_Search(a, b, c, d)
			print(ans)
main()


from sys import stdin, stdout

def f(a, b, c, d, i):
	return d * b * i * (i + 1) // 2 - a * (i + 1)
for i in range(int(input())):
	(a, b, c, d) = [int(i) for i in stdin.readline().split()]
	if -a + b * c < 0:
		stdout.write('-1\n')
	else:
		v = a // (b * d)
		mx = 0
		mx = max(mx, -f(a, b, c, d, max(0, v)))
		mx = max(mx, -f(a, b, c, d, max(0, v + 1)))
		stdout.write(str(mx) + '\n')


def solve(a, b, c, d):
	if a > b * c:
		return -1
	if c <= d:
		return a
	k = a // b // d + 1
	return k * a - k * (k - 1) // 2 * d * b

def main():
	t = int(input())
	for _ in range(t):
		(a, b, c, d) = map(int, input().split())
		print(solve(a, b, c, d))
main()


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
from itertools import permutations, combinations

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')
INF = 10 ** 9
mod = int(1000000000.0) + 7
for t in range(int(data())):
	(a, b, c, d) = mdata()
	if a > b * c:
		out(-1)
	else:
		k = a // (b * d)
		out(a * (k + 1) - k * (k + 1) * b * d // 2)


import sys
input = sys.stdin.readline

def f(mid):
	return a * (mid + 1) - mid * (mid + 1) // 2 * db
t = int(input())
res = []
for _ in range(t):
	(a, b, c, d) = map(int, input().split())
	inc = a - b * c
	if inc > 0:
		res.append(-1)
		continue
	if c < d:
		res.append(a)
		continue
	db = d * b
	(l, r) = (0, 10 ** 6 + 10)
	while r - l > 1:
		mid = (l + r) // 2
		c1 = l + (r - l) // 3
		c2 = r - (r - l) // 3
		if f(mid) - f(mid - 1) > 0:
			l = mid
		else:
			r = mid
	res.append(max(f(l), f(r)))
print('\n'.join(map(str, res)))


import sys
Z = sys.stdin.readline
o = []
for _ in range(int(Z())):
	(a, b, c, d) = map(int, Z().split())
	if a > b * c:
		o += [-1]
	elif d > c:
		o += [a]
	else:
		v = a // (b * d)
		o += [(v + 1) * a - b * d * (v * (v + 1)) // 2]
print('\n'.join(map(str, o)))


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
T = int(input())
for _ in range(T):
	(A, B, C, D) = map(int, input().split())
	if C * B < A:
		print(-1)
		continue
	n = A // B // D
	ans = A * (n + 1) - n * (n + 1) // 2 * B * D
	print(ans)


import sys
input = sys.stdin.buffer.readline
for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	if a - b * c > 0:
		print(-1)
	else:
		const = (-c - 1) // d
		k = c // d + 1
		tmp1 = (k + 1) * (a - b * c) - const * b * c - d * b * const * (const + 1) // 2
		tmp2 = 0
		m = (-d * b + 2 * a) // (2 * d * b)
		if m >= k:
			k = k - 1
			tmp2 = (k + 1) * a - d * b * k * (k + 1) // 2
		else:
			tmp2 = -10 ** 18
			for i in range(-5, 6):
				k = m + i
				if k < 0:
					continue
				tmp22 = (k + 1) * a - d * b * k * (k + 1) // 2
				tmp2 = max(tmp2, tmp22)
		res = max(tmp1, tmp2)
		print(res)


def f(k, a, b, d):
	return a * (k + 1) - k * (k + 1) * b * d // 2

def main():
	t = int(input())
	for _ in range(t):
		(a, b, c, d) = [int(s) for s in input().split()]
		if a > c * b:
			print(-1)
		else:
			k = a // (b * d)
			print(f(k, a, b, d))
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
for _ in range(N()):
	(a, b, c, d) = RL()
	if b * c < a:
		print(-1)
	else:
		key = a // (d * b)
		heal = (1 + key) * key >> 1
		print(a * (key + 1) - heal * b * d)


import sys
input = sys.stdin.readline
for f in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	if d >= c:
		if a > b * c:
			print(-1)
		else:
			print(a)
	elif a > b * c:
		print(-1)
	elif a < b * d:
		print(a)
	else:
		k = a // (b * d)
		print((k + 1) * a - k * (k + 1) * b * d // 2)