There are $n$ chests. The $i$-th chest contains $a_i$ coins. You need to open all $n$ chests in order from chest $1$ to chest $n$.

There are two types of keys you can use to open a chest:

a good key, which costs $k$ coins to use;

a bad key, which does not cost any coins, but will halve all the coins in each unopened chest, including the chest it is about to open. The halving operation will round down to the nearest integer for each chest halved. In other words using a bad key to open chest $i$ will do $a_i = \lfloor{\frac{a_i}{2}\rfloor}$, $a_{i+1} = \lfloor\frac{a_{i+1}}{2}\rfloor, \dots, a_n = \lfloor \frac{a_n}{2}\rfloor$;

any key (both good and bad) breaks after a usage, that is, it is a one-time use.

You need to use in total $n$ keys, one for each chest. Initially, you have no coins and no keys. If you want to use a good key, then you need to buy it.

During the process, you are allowed to go into debt; for example, if you have $1$ coin, you are allowed to buy a good key worth $k=3$ coins, and your balance will become $-2$ coins.

Find the maximum number of coins you can have after opening all $n$ chests in order from chest $1$ to chest $n$.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \leq n \leq 10^5$; $0 \leq k \leq 10^9$) — the number of chests and the cost of a good key respectively.

The second line of each test case contains $n$ integers $a_i$ ($0 \leq a_i \leq 10^9$)  — the amount of coins in each chest.

The sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case output a single integer  — the maximum number of coins you can obtain after opening the chests in order from chest $1$ to chest $n$.

Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).


-----Examples-----

Input
5
4 5
10 10 3 1
1 2
1
3 12
10 10 29
12 51
5 74 89 45 18 69 67 67 11 96 23 59
2 57
85 60
Output
11
0
13
60
58


-----Note-----

In the first test case, one possible strategy is as follows:

Buy a good key for $5$ coins, and open chest $1$, receiving $10$ coins. Your current balance is $0 + 10 - 5 = 5$ coins.

Buy a good key for $5$ coins, and open chest $2$, receiving $10$ coins. Your current balance is $5 + 10 - 5 = 10$ coins.

Use a bad key and open chest $3$. As a result of using a bad key, the number of coins in chest $3$ becomes $\left\lfloor \frac{3}{2} \right\rfloor = 1$, and the number of coins in chest $4$ becomes $\left\lfloor \frac{1}{2} \right\rfloor = 0$. Your current balance is $10 + 1 = 11$.

Use a bad key and open chest $4$. As a result of using a bad key, the number of coins in chest $4$ becomes $\left\lfloor \frac{0}{2} \right\rfloor = 0$. Your current balance is $11 + 0 = 11$.

At the end of the process, you have $11$ coins, which can be proven to be maximal.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Greedy algorithms

Complete search

Dynamic programming

Mathematics


Solutions:
def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	vs = []
	prefs = [0] * (n + 1)
	for i in range(n):
		prefs[i + 1] = prefs[i] + a[i]
	ans = sum(a) - k * n
	for i in range(n - 1, -1, -1):
		vs = [x >> 1 for x in vs if x > 1]
		vs.append(a[i] >> 1)
		nv = prefs[i] + sum(vs) - k * i
		if nv > ans:
			ans = nv
	print(ans)
	return

def main():
	for _ in range(int(input())):
		solve()
	return
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [*map(int, input().split())]
	S = sum(a)
	profit = S - m * n
	cur = []
	for i in range(n - 1, -1, -1):
		cur += (a[i],)
		cur = [x // 2 for x in cur if x // 2]
		S -= a[i]
		profit = max(profit, S + sum(cur) - i * m)
	print(profit)


x = int(input())

def cal(n, c, arr):
	t = [0] * n
	for i in range(n):
		t[i] = t[i - 1] + arr[i] - c
	p = []
	for i in range(n):
		re = 0
		k = 1
		for j in range(i, n):
			org = arr[j] >> k
			re += org
			k += 1
			if k >= 30:
				break
		p.append(re)
	res = max(p[0], t[-1])
	for i in range(n - 1):
		res = max(res, t[i] + p[i + 1])
	return res
for jj in range(x):
	(n, c) = [int(i) for i in input().split(' ')]
	arr = [int(i) for i in input().split(' ')]
	print(cal(n, c, arr))


from itertools import accumulate as ac
r = lambda : map(int, input().split())
(t,) = r()
f = lambda i: p[i] - k * i + sum((a[i + j] >> j + 1 for j in range(min(n - i, 30))))
while t:
	t -= 1
	(n, k) = r()
	a = [*r()]
	p = [0] + list(ac(a))
	print(max((f(i) for i in range(n + 1))))


def solve():
	(n, k) = map(int, input().split())
	chests = list(map(int, input().split()))
	(ans, total) = (0, 0)
	for i in range(-1, n):
		now = total
		for j in range(i + 1, min(n, i + 32)):
			copy = chests[j]
			copy >>= j - i
			now += copy
		ans = max(ans, now)
		if i + 1 != n:
			total += chests[i + 1] - k
	print(ans)
t = int(input())
for _ in range(t):
	solve()


import itertools
MAX = 29
POW = [2 ** (i + 1) for i in range(MAX)]

def calc(g):
	return -k * g + s[g] + sum((a[g + i] // POW[i] for i in range(min(n - g, MAX))))
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = list(itertools.accumulate(a, initial=0))
	print(max((calc(g) for g in range(0, n + 1))))


from bisect import insort
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = sum(arr) - n * k
	right = []
	ans = s
	for i in range(n - 1, -1, -1):
		s += k - arr[i]
		insort(right, -arr[i])
		for j in range(len(right)):
			right[j] = -(-right[j] // 2)
		while right and right[-1] == 0:
			right.pop()
		ans = max(ans, s - sum(right))
	print(ans)


from itertools import accumulate

def miis():
	return map(int, input().split())
for _ in range(int(input())):
	(n, k) = miis()
	a = list(miis())
	a.reverse()
	acc = [0] + list(accumulate(a))
	b = []
	ans = 0
	for i in range(n + 1):
		ans = max(ans, acc[-1] - acc[i] - (n - i) * k + sum(b))
		if i != n:
			b.append(a[i])
			for i in range(len(b)):
				b[i] //= 2
			b = list(filter(lambda x: x, b))
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	(*a,) = map(int, input().split())
	dp = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		bin_number = format(a[i], 'b')
		for (j, index) in zip(range(i - 1, max(-1, i - len(bin_number)), -1), range(-2, -len(bin_number) - 1, -1)):
			if bin_number[index] == '1':
				dp[j] -= 1
		dp[i] = dp[i] + dp[i + 1] + a[i] >> 1
	running_sum = 0
	for i in range(1, n + 1):
		running_sum += a[i - 1] - k
		dp[i] += running_sum
	print(max(dp))


def calc_postf(a, i):
	mul = 2
	res = 0
	for j in range(i, i + 32):
		res += a[j] // mul
		mul *= 2
	return res

def calc(a, k, idx, n, cursum, multiplier):
	global max_val
	if idx > n - 1:
		if cursum > max_val:
			max_val = cursum
		return
	if cursum < max_val:
		return
	calc(a, k, idx + 1, n, cursum + a[idx] // multiplier - k, multiplier)
	calc(a, k, idx + 1, n, cursum + a[idx] // (multiplier * 2), multiplier * 2)

def main():
	global max_val
	_i = int(input())
	for _ in range(_i):
		max_val = -1000000000
		(n, k) = [int(x) for x in input().strip('\r\n').split()]
		a = [int(x) for x in input().strip('\r\n').split()]
		a += [0] * 33
		sum_pref = 0
		res = calc_postf(a, 0)
		for i in range(n):
			sum_pref += a[i] - k
			sum_postf = calc_postf(a, i + 1)
			res = max(res, sum_pref + sum_postf)
		print(res)
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mx = max(0, sum(a) - n * k)
	s = 0
	for i in range(n):
		c = 0
		for j in range(i, min(n, 30 + i)):
			c += a[j] >> j - i + 1
		mx = max(mx, s + c)
		s += a[i] - k
	print(mx)


from itertools import accumulate
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	acc = [0] + list(accumulate(arr))
	ans = 0
	for i in range(n + 1):
		cur = acc[i] - k * i
		for j in range(i, min(n, i + 30)):
			cur += arr[j] >> j - i + 1
		ans = max(ans, cur)
	print(ans)


for q in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	pre = [arr[0]]
	suff = [arr[-1] // 2]
	for i in range(1, n):
		pre.append(pre[-1] + arr[i])
	ans = pre[-1] - k * n
	for i in range(n):
		temp = pre[i] - k * (i + 1)
		for j in range(i + 1, min(n, i + 33)):
			temp += arr[j] >> j - i
		ans = max(ans, temp)
	cur = 0
	for i in range(n):
		cur += arr[i] >> i + 1
	ans = max(ans, cur)
	print(ans)


T = int(input())
for _ in range(T):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	summ = 0
	ans = 0
	for i in range(min(n, 35)):
		ans += a[i] >> i + 1
	for i in range(n):
		summ += a[i] - k
		temp = 0
		for j in range(i + 1, min(n, i + 35)):
			temp += a[j] >> j - i
		ans = max(ans, summ + temp)
	print(ans)


import math
import os
import collections
import sys
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	(ans, val) = (0, 0)
	for i in range(-1, N):
		cnt = val
		for j in range(i + 1, min(N, i + 32)):
			B = A[j]
			B >>= j - i
			cnt += B
		ans = max(ans, cnt)
		if i != N - 1:
			val += A[i + 1] - M
	print(ans)


def soln():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	prefix = [0] * n
	prefix[0] = a[0] - k
	for i in range(1, n):
		prefix[i] = prefix[i - 1] + (a[i] - k)
	tw = [0] * n
	for i in range(n):
		s = 2
		val = 0
		for j in range(i, n):
			if s > int(1000000000.0):
				break
			else:
				val += a[j] // s
				s *= 2
		tw[i] = val
	ans = -1
	for i in range(n - 1):
		ans = max(ans, prefix[i] + tw[i + 1])
	print(max(ans, tw[0], prefix[-1]))
for _ in range(int(input())):
	soln()


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = [0] + list(map(int, input().split()))
	s = 0
	ans = 0
	for i in range(n + 1):
		s += a[i]
		p = 1
		ost = 0
		for j in range(1, min(30, n - i + 1)):
			p *= 2
			ost += a[i + j] // p
		ans = max(ans, s - i * k + ost)
	print(ans)


z = lambda : map(int, input().split())
(t,) = z()
for t_ in [0] * t:
	(n, k) = z()
	l = [0] + [*z()]
	m = -20000000000.0
	ar = [0]
	for i in range(1, n + 1):
		ar.append(ar[i - 1] + l[i] - k)
		c = 0
		e = 2
		for j in range(i, min(n + 1, i + 30)):
			c += l[j] // e
			e = 2 * e
		c += ar[i - 1]
		m = max(m, c)
	print(max(m, ar[-1]))


a = int(input())
for x in range(a):
	(b, c) = map(int, input().split())
	d = list(map(int, input().split()))
	f = 0
	j = []
	for y in range(b):
		k = 2
		s = f
		for z in range(y, min(y + 32, b)):
			s += d[z] // k
			k *= 2
		j.append(s)
		f += d[y] - c
	j.append(f)
	print(max(j))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	chests = list(map(int, input().split()))
	res = 0
	sum = 0
	for i in range(n + 1):
		cur = sum
		cuts = 1
		for j in range(i, min(i + 32, n)):
			cuts *= 2
			cur += chests[j] // cuts
		res = max(res, cur)
		if i < n:
			sum += chests[i] - k
	res = max(res, sum)
	print(res)


t = int(input())
while t:
	(p, q) = map(int, input().split())
	l = list(map(int, input().split()))
	check = 0
	ans = 0
	for i in range(-1, p):
		res = check
		for j in range(i + 1, min(p, i + 32)):
			u = l[j]
			u >>= j - i
			res += u
		ans = max(ans, res)
		if i + 1 != p:
			check += l[i + 1] - q
	print(ans)
	t -= 1


for _ in range(int(input())):
	(n, y) = map(int, input().split())
	a = list(map(int, input().split()))
	good = 0
	ans = 0
	for i in range(n):
		bad = 0
		fac = 1
		for j in range(i, min(i + 30, n)):
			bad += a[j] // (1 << fac)
			fac += 1
		ans = max(ans, good + bad)
		good += a[i] - y
	ans = max(good, ans)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ai = list(map(int, input().split()))
	ans = 0
	cur = 0
	for i in range(n):
		val = 0
		p = 2
		for ii in range(i, min(len(ai), i + 32)):
			val += ai[ii] // p
			p *= 2
		ans = max(ans, val + cur)
		cur += ai[i] - k
	ans = max(ans, cur)
	print(ans)


out = []

def f(m):
	ans = pre[m]
	c = 1
	for i in range(m, min(n, m + 30)):
		ans += a[i] // 2 ** c
		c += 1
	return ans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	pre = [0] * (n + 1)
	for i in range(n):
		pre[i + 1] = pre[i] + a[i] - k
	ans = 0
	for i in range(n + 1):
		ans = max(ans, f(i))
	out.append(ans)
for i in out:
	print(i)


import sys
import math
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	gk = [0]
	for i in range(n):
		gk.append(gk[-1] + arr[i] - k)
	ans = 0
	for i in range(n + 1):
		sum = gk[i]
		p = 2
		for j in range(i, min(n, i + 32)):
			sum += arr[j] // p
			p *= 2
		ans = max(ans, sum)
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	ans = 0
	prefix = 0
	for i in range(-1, n):
		now = prefix
		for j in range(i + 1, min(n, i + 1 + 32)):
			num = arr[j]
			num >>= j - i
			now += num
		ans = max(ans, now)
		if i + 1 < n:
			prefix += arr[i + 1] - k
	print(ans)


from itertools import accumulate
thr = int(1000000000.0)
t = int(input())
while t:
	t -= 1
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	prefix = list(accumulate(a))
	arr = [0] * n
	for i in range(n):
		cur = 0
		tmp = 2
		for j in range(i, n):
			cur += a[j] // tmp
			tmp *= 2
			if tmp > thr:
				break
		arr[i] = cur
	ans = -n * k + prefix[-1]
	for i in range(n - 1, 0, -1):
		ans = max(ans, -i * k + prefix[i - 1] + arr[i])
	ans = max(ans, arr[0])
	print(ans)


for nothing in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	pref = [0] * n
	pref[0] = a[0]
	for i in range(1, n):
		pref[i] = pref[i - 1] + a[i]
	ans = 0
	d = 0
	for i in range(n):
		d += 1
		ans += a[i] // (1 << d)
		if d > 30:
			break
	for good_end in range(n):
		s = pref[good_end] - k * (good_end + 1)
		d = 0
		for i in range(good_end + 1, n):
			d += 1
			s += a[i] // (1 << d)
			if d > 30:
				break
		ans = max(ans, s)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	bit = [0] * (n + 32)
	for i in range(n):
		x = bin(l[i])[2:]
		x = x[::-1]
		for j in range(len(x)):
			bit[n - i + j - 1] += int(x[j])
	sumlist = [l[-1]]
	for i in range(n - 2, -2, -1):
		x = sumlist[-1] - bit[n - 2 - i]
		x //= 2
		x += l[i]
		sumlist.append(x)
	ans = sum(l) - n * k
	best = ans
	for i in range(n - 1, -1, -1):
		x = sumlist[n - 1 - i] - sumlist[n - i] + l[i - 1]
		ans += k - x
		best = max(best, ans)
	print(best)


import sys
input = sys.stdin.readline

def int_num():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

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

def solve():
	(n, k) = int_list()
	arr = int_list()
	MAX_BAD = 32
	dp = [0] * MAX_BAD
	for i in range(n - 1, -1, -1):
		coin = arr[i]
		for j in range(MAX_BAD - 1):
			good = coin - k + dp[j]
			bad = coin // 2 + dp[j + 1]
			dp[j] = max(good, bad)
			coin = coin // 2
	ans = max(dp)
	print(ans)

def main():
	t = int_num()
	while t:
		solve()
		t -= 1
	return
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	s = 0
	for i in range(-1, n):
		left = 0
		if i >= 0:
			s += a[i] - k
		bad = 2
		for j in range(i + 1, min(n, i + 38)):
			left += a[j] // bad
			bad = 2 * bad
		ans = max(ans, s + left)
	print(ans)


import sys
T = int(sys.stdin.readline())
for t in range(T):
	(n, k) = map(int, sys.stdin.readline().split())
	chests = list(map(int, sys.stdin.readline().split()))
	gk = sum(chests) - n * k
	answer = gk
	bk_list = []
	for i in range(n - 1, -1, -1):
		bk_list.append(chests[i])
		gk = gk + k - chests[i]
		bk = 0
		j = max(0, len(bk_list) - 30)
		while j < len(bk_list):
			bk_list[j] //= 2
			bk += bk_list[j]
			j += 1
		answer = max(answer, bk + gk)
	print(answer)


I = lambda : map(int, input().split())
(t,) = I()
while t:
	t -= 1
	(_, k) = I()
	l = [0] * 31
	for a in I():
		l = [max([l[i] - k * (i < 30), l[i - 1]][:i + 1]) + (a >> i) for i in range(31)]
	print(max(l))


from itertools import accumulate
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	acc = [0] + list(accumulate(a))
	wins = []
	for x in range(n + 1):
		win = acc[x] - k * x
		for i in range(x, x + 30):
			if i >= n:
				break
			win += a[i] // 2 ** (i - x + 1)
		wins.append(win)
	print(max(wins))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	l = arr
	s = 0
	for i in range(n):
		p = l[i]
		arr[i] = p
		s += p - k
	ans = s
	for i in range(n - 1, -1, -1):
		s -= arr[i] - k
		tot = 0
		for j in range(i, min(i + 31, n - 1) + 1):
			tot += arr[j] // 2 ** (j - i + 1)
		ans = max(ans, s + tot)
	print(int(ans))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split(' ')]
	sum = 0
	for i in range(n):
		sum += a[i]
	ma = max(0, sum - n * k)
	sum = 0
	for i in range(n):
		res = 0
		tmp = 2
		j = i
		while j < n and j < 30 + i:
			res += a[j] // tmp
			tmp *= 2
			j += 1
		ma = max(ma, sum + res)
		sum += a[i] - k
	print(ma)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ma = max(0, sum(a) - n * k)
	sum1 = 0
	for i in range(n):
		res = 0
		j = i
		while j < n and j < 32 + i:
			res += a[j] >> j - i + 1
			j += 1
		ma = max(ma, sum1 + res)
		sum1 += a[i] - k
	print(ma)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mx = max(0, sum(a) - n * k)
	cur = 0
	for i in range(n):
		loc = 0
		for j in range(i, min(n, 70 + i)):
			loc += a[j] >> j - i + 1
		mx = max(mx, cur + loc)
		cur += a[i] - k
	print(mx)


import sys
input = sys.stdin.readline

def construir_matriz(a, n):
	m = [[0] * n for _ in range(32)]
	m[0] = a
	d = [0] * n
	for i in range(1, 32):
		for j in range(n):
			m[i][j] = m[i - 1][j] // 2
			if j - i + 1 >= 0 and j - i + 1 < n:
				d[j - i + 1] = d[j - i + 1] + m[i][j]
	return (m, d)
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	(m, d) = construir_matriz(a, n)
	s = [0] * n
	v = [0] * (n + 1)
	v[0] = d[0]
	s[0] = a[0]
	for i in range(1, n):
		s[i] = s[i - 1] + a[i]
		v[i] = d[i] - i * k + s[i - 1]
	v[n] = s[n - 1] - n * k
	print(max(v))


tests = int(input())
for _ in range(tests):
	(n, cost) = list(map(int, input().split()))
	array = list(map(int, input().split()))
	q = 30
	dp = [0] * q
	for k in range(q):
		dp[k] = max((array[-1] >> k) - cost, array[-1] >> k + 1)
	for i in range(1, n):
		newdp = [0] * q
		for k in range(q - 1):
			x = array[n - 1 - i] >> k
			newdp[k] = max(x - cost + dp[k], (x >> 1) + dp[k + 1])
		dp = newdp
	m = max(dp)
	print(m)