Chef has N bags and an integer X. The i^{th} bag contains A_{i} coins such that A_{i} ≤ X. 

In one operation, Chef can:
Pick any bag and increase its coins to X. Formally, if he choses the i^{th} bag, he can set A_{i} = X. 

Given that the cost of performing each operation is C (C ≤ X) coins and Chef can perform the above operation any (possibly zero) number of times, determine the maximum value of:  
\sum_{i=1}^N A_{i} - total cost paid by Chef, if Chef performs the operations optimally. 

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains three space-separated integers N, X, and C — the number of bags, maximum limit of coins on each bag and cost of each operation respectively.
- The next line contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} - denoting the number of coins in each bag.

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

For each test case, output the maximum value of \sum_{i=1}^N A_{i} - total cost paid by Chef.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 100$
$1 ≤ C ≤ X ≤ 100$
$1 ≤ A_{i} ≤ X$

----- Sample Input 1 ------ 
3
5 5 2
1 2 3 4 5
3 4 4
1 1 1
5 3 2
3 2 3 1 1

----- Sample Output 1 ------ 
18
3
10

----- explanation 1 ------ 
Test case $1$: It is optimal for Chef to perform $2$ operations:
- Operation $1$: Choose $i = 1$ and set $A_{1} = 5$ by using $2$ coins.
- Operation $2$: Choose $i = 2$ and set $A_{2} = 5$ by using $2$ coins.

The final array is $A = [5, 5, 3, 4, 5]$ and the total cost is $2+2 = 4$. Thus, the value of $\sum_{i=1}^N A_{i}$ $-$ total cost is $(5+5+3+4+5) - 4 = 22-4 = 18$. 

Test case $2$: It is optimal for Chef to perform $0$ operations. Thus, the final array remains $[1, 1, 1]$ and the cost is $0$. The value of $\sum_{i=1}^N A_{i}$ $-$ total cost is $(1+1+1) - 0 = 3$. 

Test case $3$: It is optimal for Chef to perform $0$ operations. Thus, the final array remains $[3, 2, 3, 1, 1]$ and the cost is $0$. The value of $\sum_{i=1}^N A_{i}$ $-$ total cost is $(3+2+3+1+1) - 0 = 10$.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
t = int(input())
while t:
	(n, x, c) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	s = 0
	for i in range(n):
		if a[i] < x and x - a[i] > c:
			a[i] = x
			s += 1
	print(sum(a) - s * c)
	t -= 1


t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	n = l[0]
	x = l[1]
	c = l[2]
	count = 0
	a = list(map(int, input().split()))
	for i in range(n):
		if x - a[i] > c:
			a[i] = x
			count += 1
	print(sum(a) - count * c)


for _ in range(int(input())):
	(n, x, c) = map(int, input().split())
	a = list(map(int, input().split()))
	counter = 0
	for i in range(n):
		if a[i] < x and x - a[i] > c:
			a[i] = x
			counter += 1
	print(sum(a) - counter * c)


for _ in range(int(input())):
	(n, x, c) = map(int, input().split())
	l = list(map(int, input().split()))
	cost = 0
	summ = 0
	for i in l:
		if x - i > c:
			cost += c
			i = x
		summ += i
	print(summ - cost)


def fun(bag_status, max_coins, cost):
	(new_arr, count) = (0, 0)
	for i in bag_status:
		if max_coins - i > cost:
			new_arr += max_coins
			count += cost
		else:
			new_arr += i
	return new_arr - count
for j in range(int(input())):
	(bags, max_coins, cost) = map(int, input().split())
	bag_status = [int(i) for i in input().split()]
	print(fun(bag_status, max_coins, cost))


for i in range(0, int(input())):
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	t = 0
	for j in range(0, len(l2)):
		if l1[1] - l2[j] > l1[2]:
			t = t + 1
			l2[j] = l1[1]
		else:
			continue
	print(sum(l2) - t * l1[2])


t = int(input())
for i in range(t):
	(b, c, d) = map(int, input().split())
	l = list(map(int, input().split()))
	y = 0
	for k in range(b):
		if c - l[k] > d:
			l[k] = c
			y = y + d
	print(sum(l) - y)


a = int(input())
for i in range(a):
	(b, c, d) = map(int, input().split())
	e = list(map(int, input().split()))
	y = 0
	for k in range(b):
		if c - e[k] > d:
			e[k] = c
			y = y + d
	print(sum(e) - y)


t = int(input())
for i in range(t):
	(n, x, c) = [int(y) for y in input().split()]
	a = [int(y) for y in input().split()]
	a.sort()
	z = 0
	for j in range(n):
		if x - a[j] > c:
			a[j] = x
			z += 1
		else:
			break
	print(sum(a) - z * c)


for _ in range(int(input())):
	(n, x, c) = map(int, input().split())
	a = list(map(int, input().split()))
	t = 0
	for i in range(n):
		if x - a[i] > c:
			a[i] = x
			t += c
	print(sum(a) - t)


tc = int(input())
for t in range(tc):
	(N, X, C) = map(int, input().split())
	A = list(map(int, input().split()))
	ops = 0
	for i in range(N):
		if A[i] < X - C:
			ops += 1
			A[i] = X
	print(sum(A) - ops * C)


T = int(input())
for i in range(T):
	(n, x, c) = map(int, input().split(' '))
	arr = list(map(int, input().strip().split()))[:n]
	cost = 0
	for i in range(n):
		if x - arr[i] - c > 0:
			arr[i] = x
			cost += c
	print(int(sum(arr) - cost))


T = int(input())
for i in range(T):
	(n, x, c) = map(int, input().split(' '))
	a = list(map(int, input().strip().split()))[:n]
	cnt = 0
	for j in range(n):
		if x - a[j] - c > 0:
			cnt += 1
			a[j] = x
	result = sum(a) - cnt * c
	print(result)


t = int(input())
for i in range(t):
	n_x_c = input().split(' ')
	(n, x, c) = (int(n_x_c[0]), int(n_x_c[1]), int(n_x_c[2]))
	arr = input().split(' ')
	for j in range(n):
		arr[j] = int(arr[j])
	arr.sort()
	(total, l) = (sum(arr), [sum(arr)])
	for y in range(n):
		if x - arr[y] != 0:
			total += x - arr[y] - c
			l.append(total)
	l.sort()
	print(l[-1])


def net_pos_delt(x, c, a):
	net = x - a - c
	if net < 0:
		net = 0
	return net
T = int(input())
for t in range(0, T):
	(N, X, C) = map(int, input().split())
	A = list(map(int, input().split()))
	net_pos_change = [net_pos_delt(X, C, A[i]) for i in range(0, N)]
	net_sum = sum([sum(item) for item in zip(A, net_pos_change)])
	print(net_sum)


for i in range(int(input())):
	(N, X, C) = map(int, input().split())
	li = list(map(int, input().split()))
	count = 0
	for i in range(N):
		if X == C:
			break
		elif X - li[i] > C:
			li[i] = X
			count += 1
	print(sum(li) - count * C)


q = int(input())
for i in range(q):
	(n, x, c) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	count = 0
	for j in range(n):
		if l[j] < x - c:
			l[j] = x
			count += 1
	print(sum(l) - count * c)


t = int(input())
for i in range(t):
	(n, x, c) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 0
	for k in range(n):
		if arr[k] < x and x - arr[k] > c:
			arr[k] = x
			count += 1
	print(sum(arr) - count * c)


for i in range(int(input())):
	(n, x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	for i in range(n):
		if a[i] < x and x - a[i] > y:
			a[i] = x
			c += y
	print(sum(a) - c)


t = int(input())
for _ in range(t):
	(n, x, c) = map(int, input().split())
	coins = list(map(int, input().split()))
	coins.sort()
	ans = 0
	for i in range(n):
		if x - coins[i] >= c:
			ans += x - c
		else:
			ans += coins[i]
	print(ans)


for i in range(int(input())):
	(N, X, C) = map(int, input().split())
	A = list(map(int, input().split()))
	s = 0
	for j in A:
		if X - j > C:
			s = s + X - C
		else:
			s = s + j
	print(s)


tc = int(input())
for _ in range(tc):
	(n, x, c) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(n):
		if x - a[i] > c:
			a[i] = x - c
	tot = 0
	for i in range(n):
		tot += a[i]
	print(tot)


t = int(input())
while t > 0:
	t -= 1
	(n, x, c) = map(int, input().split())
	lis = list(map(int, input().split()))
	cost = 0
	for i in range(n):
		if x - lis[i] > c:
			cost += c
			lis[i] = x
		else:
			pass
	print(sum(lis) - cost)


for i in range(int(input())):
	(n, x, c) = map(int, input().split())
	a = list(map(int, input().split()))
	c1 = 0
	for i in range(n):
		if x - a[i] > c:
			a[i] = x
			c1 += 1
	print(sum(a) - c * c1)


for i in range(int(input())):
	(n, x, c) = map(int, input().split())
	arr = list(map(int, input().split()))
	if sum(arr) == x * len(arr):
		print(sum(arr))
	else:
		nums = 0
		for i in range(len(arr)):
			if x - arr[i] - c > 0:
				nums += 1
				arr[i] = x
		print(sum(arr) - nums * c)


t = int(input())
for tc in range(t):
	(n, x, c) = map(int, input().split())
	a = list(map(int, input().split()))
	d = 0
	for j in range(n):
		if a[j] < x and x - a[j] > c:
			a[j] = x
			d += 1
	print(sum(a) - d * c)


for _ in range(int(input())):
	(bags, maxcoins, cost) = map(int, input().split())
	baglist = list(map(int, input().split()))
	count = 0
	for i in range(bags):
		if maxcoins - baglist[i] > cost:
			count += 1
			baglist[i] = maxcoins
	sumbags = sum(baglist)
	print(sumbags - count * cost)


cases = int(input())
for i in range(cases):
	(numBags, bagLimit, changeCost) = map(int, input().split())
	bags = list(map(int, input().split()))
	cost = 0
	for j in range(len(bags)):
		if bags[j] + changeCost < bagLimit:
			cost += changeCost
			bags[j] = bagLimit
	print(sum(bags) - cost)


for i in range(int(input())):
	arr = input().split()
	n = int(arr[0])
	x = int(arr[1])
	c = int(arr[2])
	bags = input().split()
	eff_gain = x - c
	count = 0
	for i in range(n):
		if int(bags[i]) < eff_gain:
			count += 1
			bags[i] = x
	sum = 0
	for i in range(n):
		sum += int(bags[i])
	print(sum - count * c)


for _ in range(int(input())):
	(n, x, c) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	t = 0
	for i in range(n):
		if x - l[i] > c:
			l[i] = x
			t += c
		else:
			break
	print(sum(l) - t)


for i in range(int(input())):
	(Num, X, C) = map(int, input().split())
	A = list(map(int, input().split()))
	a = 0
	for j in range(Num):
		if X - C - A[j] > 0:
			a += 1
			A[j] = X
	print(sum(A) - C * a)


for _ in range(int(input())):
	(n, x, c) = map(int, input().split())
	num = list(map(int, input().split()))
	total = sum(num)
	num.sort()
	cost = 0
	high = total
	for i in num:
		cost += c
		total += x - i
		if high > total - cost:
			break
		high = total - cost
	print(high)


for _ in range(int(input())):
	(n, x, c) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 0
	for i in range(len(a)):
		if x - a[i] > c:
			count += 1
			a[i] = x
	print(sum(a) - count * c)


for _ in range(int(input())):
	(N, X, C) = map(int, input().split())
	A = list(map(int, input().split()))
	a = sum(A)
	for Ai in A:
		if X - Ai > C:
			a += X - Ai - C
	print(a)


for i in range(int(input())):
	(n, x, c) = map(int, input().split())
	a = list(map(int, input().split()))
	l = []
	k = sum(a)
	co = 0
	for i in a:
		if i < x and c + i < x:
			l.append(x)
			co += 1
		else:
			l.append(i)
	print(sum(l) - co * c)


for t in range(int(input())):
	(n, x, c) = list(map(int, input().split()))
	ai = list(map(int, input().split()))
	s = 0
	for i in ai:
		if x - i > c:
			s += x - c
		else:
			s += i
	print(s)


for i in range(int(input())):
	(n, x, c) = map(int, input().split())
	abc = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if x - abc[i] > c:
			abc[i] = x
			ans += c
	print(sum(abc) - ans)


for i in range(int(input())):
	(n, l, m) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	y = 0
	for k in range(n):
		if l - arr[k] > m:
			arr[k] = l
			y = y + m
	print(sum(arr) - y)


for i in range(int(input())):
	(n, x, c) = map(int, input().split())
	po = list(map(int, input().split()))
	xx = 0
	for i in po:
		if x - i > c:
			xx += x - c
		else:
			xx += i
	print(xx)


for i in range(int(input())):
	(n, x, c) = map(int, input().split())
	l = list(map(int, input().strip().split()))
	l.sort()
	m = sum(l)
	for i in range(len(l)):
		l[i] = x
		k = sum(l) - (i + 1) * c
		if m < k:
			m = k
	print(m)


T = int(input())
while T:
	T -= 1
	(n, x, c) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	mon = sum(a)
	for i in range(n):
		if a[i] < x:
			if mon - a[i] + x - c > mon:
				mon = mon - a[i] + x - c
		else:
			break
	print(mon)


t = int(input())
for k in range(0, t):
	(n, x, c) = map(int, input().split())
	l = list(map(int, input().split()))
	q = x - c
	s = 0
	for j in range(0, n):
		if l[j] < q:
			s += q
		else:
			s += l[j]
	print(s)


for _ in range(int(input())):
	(n, x, c) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	s = sum(arr)
	sums = []
	for i in range(1, n + 1):
		arr[i - 1] = x
		sums.append(sum(arr) - i * c)
	if max(sums) > s:
		print(max(sums))
	else:
		print(s)


def money():
	reps = 0
	for i in range(n):
		if abs(a[i] - x) > c:
			a[i] = x
			reps += 1
	return sum(a) - reps * c
for _ in range(int(input())):
	(n, x, c) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a.sort()
	print(money())


for i in range(int(input())):
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	d = 0
	for j in range(a[0]):
		if a[1] - b[j] > a[2]:
			d += 1
			b[j] = a[1]
	print(sum(b) - d * a[2])


for _ in range(int(input())):
	(N, X, C) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	c = 0
	for i in range(0, len(l)):
		if X - l[i] > C:
			l[i] = X
			c += 1
	print(sum(l) - C * c)


l = list()
t = int(input())
for i in range(t):
	(N, X, C) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	c = 0
	for k in range(N):
		if X - l[k] > C:
			l[k] = X
			c = c + C
	print(sum(l) - c)


def cost(n, coins, x, c):
	num = 0
	for i in range(n):
		if x - coins[i] > c:
			num += x - c
		else:
			num += coins[i]
	print(num)
for t in range(int(input())):
	(n, x, c) = map(int, input().split(' '))
	coins = list(map(int, input().split(' ')))
	cost(n, coins, x, c)


t = int(input())
for i in range(t):
	(n, x, c) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(sum((max(j, x - c) for j in arr)))


T = int(input())
for i in range(T):
	(N, X, C) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = 0
	for i in a:
		b += i + max(0, X - i - C)
	print(b)


t = int(input())
for it in range(t):
	(n, x, c) = map(int, input().split())
	a = list(map(int, input().split()))
	sum = 0
	y = 0
	for item in a:
		y += item
	for item in a:
		sum += max(x - item - c, 0)
	print(y + sum)


t = int(input())
for i in range(t):
	(n, x, c) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	res = 0
	count = 0
	for j in range(len(arr)):
		curr_ele = int(arr[j])
		if x - curr_ele > c:
			res += x
			count += c
		else:
			res += curr_ele
	res = res - count
	print(res)