Tokio Marine & Nichido Fire Insurance Programming Contest 2020 - Knapsack Queries on a tree

We have a rooted binary tree with N vertices, where the vertices are numbered 1 to N. Vertex 1 is the root, and the parent of Vertex i (i \geq 2) is Vertex \left[ \frac{i}{2} \right].

Each vertex has one item in it. The item in Vertex i has a value of V_i and a weight of W_i. Now, process the following query Q times:

* Given are a vertex v of the tree and a positive integer L. Let us choose some (possibly none) of the items in v and the ancestors of v so that their total weight is at most L. Find the maximum possible total value of the chosen items.



Here, Vertex u is said to be an ancestor of Vertex v when u is an indirect parent of v, that is, there exists a sequence of vertices w_1,w_2,\ldots,w_k (k\geq 2) where w_1=v, w_k=u, and w_{i+1} is the parent of w_i for each i.

Constraints

* All values in input are integers.
* 1 \leq N < 2^{18}
* 1 \leq Q \leq 10^5
* 1 \leq V_i \leq 10^5
* 1 \leq W_i \leq 10^5
* For the values v and L given in each query, 1 \leq v \leq N and 1 \leq L \leq 10^5.

Input

Let v_i and L_i be the values v and L given in the i-th query. Then, Input is given from Standard Input in the following format:


N
V_1 W_1
:
V_N W_N
Q
v_1 L_1
:
v_Q L_Q


Output

For each integer i from 1 through Q, the i-th line should contain the response to the i-th query.

Examples

Input

3
1 2
2 3
3 4
3
1 1
2 5
3 5


Output

0
3
3


Input

15
123 119
129 120
132 112
126 109
118 103
115 109
102 100
130 120
105 105
132 115
104 102
107 107
127 116
121 104
121 115
8
8 234
9 244
10 226
11 227
12 240
13 237
14 206
15 227


Output

256
255
250
247
255
259
223
253

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
MX = 10 ** 5

def main():
	data = map(int, sys.stdin.buffer.read().split())
	N = next(data)
	H = min(N + 1, 1 << 10)
	dp = [None] * H
	dp[0] = [0] * (MX + 1)
	(IV, IW) = ([], [])
	i = 1
	for (v, w) in zip(data, data):
		if i < H:
			dpi = dp[i >> 1][:]
			dp[i] = dpi
			for j in range(MX, w - 1, -1):
				dpi[j] = max(dpi[j], dpi[j - w] + v)
		else:
			IV.append(v)
			IW.append(w)
		i += 1
		if i > N:
			break
	Q = next(data)
	for (v, L) in zip(data, data):
		if v < H:
			print(dp[v][L])
			continue
		item_values = []
		item_weights = []
		while v >= H:
			item_values.append(IV[v - H])
			item_weights.append(IW[v - H])
			v >>= 1
		l = len(item_values)
		V = [0] * (1 << l)
		W = [0] * (1 << l)
		ans = dp[v][L]
		for i in range(1, 1 << l):
			msb = i & -i
			msbb = msb.bit_length() - 1
			wi = W[i - msb] + item_weights[msbb]
			W[i] = wi
			if wi <= L:
				vi = V[i - msb] + item_values[msbb]
				ans = max(ans, vi + dp[v][L - wi])
				V[i] = vi
		print(ans)
main()


n = int(input())
vw = [(0, 0)]
for _ in range(n):
	vw.append(list(map(int, input().split())))
A = 10
N = min(1 << A, n + 1)
memo = [None for _ in range(N)]
L = 10 ** 5 + 1
memo[0] = [0] * L
for i in range(1, N):
	m = memo[i >> 1][:]
	(v, w) = vw[i]
	for j in range(L - 1, w - 1, -1):
		if m[j] < m[j - w] + v:
			m[j] = m[j - w] + v
	memo[i] = m
q = int(input())
ans_ = [0] * q
for _ in range(q):
	(u, l) = map(int, input().split())
	m = u.bit_length() - A
	if m < 0:
		m = 0
	dv = [0] * (1 << m)
	dw = [0] * (1 << m)
	for i in range(m):
		(v, w) = vw[u]
		for j in range(1 << i):
			dv[j + (1 << i)] = dv[j] + v
			dw[j + (1 << i)] = dw[j] + w
		u >>= 1
	ans = 0
	for (v, w) in zip(dv, dw):
		if w <= l:
			val = memo[u][l - w] + v
			if val > ans:
				ans = val
	ans_[_] = ans
print(*ans_, sep='\n')


import sys
readline = sys.stdin.readline

def mergeup(Av, Aw, vw):
	(v, w) = vw
	(rv, rw) = ([], [])
	N = len(Av)
	idx = 0
	jdx = 0
	for _ in range(2 * N):
		if idx == N or Aw[idx] > Aw[jdx] + w:
			if Aw[jdx] + w > limit:
				break
			rw.append(Aw[jdx] + w)
			rv.append(Av[jdx] + v)
			jdx += 1
		else:
			rw.append(Aw[idx])
			rv.append(Av[idx])
			idx += 1
	return (rv, rw)

def mergedown(Av, Aw, vw):
	(v, w) = vw
	(resv, resw) = ([], [])
	N = len(Av)
	idx = 0
	jdx = 0
	for _ in range(2 * N):
		if jdx == N or Aw[idx] <= Aw[jdx] - w:
			resv.append(Av[idx])
			resw.append(Aw[idx])
			idx += 1
		else:
			if Aw[jdx] - w < 0:
				jdx += 1
				continue
			resv.append(Av[jdx] + v)
			resw.append(Aw[jdx] - w)
			jdx += 1
	return (resv, resw)
limit = 10 ** 5
N = int(readline())
VW = [None] + [tuple(map(int, readline().split())) for _ in range(N)]
BS = min(N, 1 << 11)
Q = int(readline())
VL = [None] + [tuple(map(int, readline().split())) for _ in range(Q)]
Rv = [[0] for _ in range(BS + 1)]
Rw = [[0] for _ in range(BS + 1)]
for i in range(1, BS):
	for (vm, wm) in zip(*mergeup(Rv[i // 2], Rw[i // 2], VW[i])):
		if Rv[i][-1] < vm:
			Rv[i].append(vm)
			Rw[i].append(wm)
ans = [0] * (Q + 1)
for i in range(1, Q + 1):
	(v, l) = VL[i]
	(Kv, Kw) = ([0], [l])
	while v >= BS:
		(Kv, Kw) = mergedown(Kv, Kw, VW[v])
		v >>= 1
	cnt = len(Rv[v]) - 1
	ctr = 0
	for j in range(len(Kv) - 1, -1, -1):
		(kv, kw) = (Kv[j], Kw[j])
		while kw < Rw[v][cnt]:
			cnt -= 1
		ctr = max(ctr, kv + Rv[v][cnt])
	ans[i] = ctr
print('\n'.join(map(str, ans[1:])))


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

def merge(a, b):
	res = []
	(i, j) = (0, 0)
	while i < len(a) or j < len(b):
		if j >= len(b) or (i < len(a) and a[i][0] < b[j][0]):
			(w, v) = a[i]
			i += 1
		else:
			(w, v) = b[j]
			j += 1
		if not res or res[-1][1] < v:
			res.append((w, v))
		elif res[-1][0] == w and res[-1][1] <= v:
			res.pop()
			res.append((w, v))
	return res

def best(L, a, b):
	res = 0
	i = 0
	j = len(b) - 1
	while i < len(a):
		(w, v) = a[i]
		if j < 0:
			break
		if b[j][0] + w > L:
			j -= 1
			continue
		res = max(res, v + b[j][1])
		i += 1
	return res

def main():
	N = int(input())
	VW = [(-1, -1)] + [list(map(int, input().split())) for _ in range(N)]
	Q = int(input())
	query = tuple((tuple(map(int, input().split())) for _ in range(Q)))
	dp = [[] for _ in range(2048)]
	dp[0] = [(0, 0)]
	for i in range(1, min(N + 1, 2048)):
		(vi, wi) = VW[i]
		a1 = dp[i // 2]
		a2 = [(w + wi, v + vi) for (w, v) in a1]
		dp[i] = merge(a1, a2)
	for (n, L) in query:
		a = [(0, 0)]
		while n >= 2048:
			(vi, wi) = VW[n]
			b = [(w + wi, v + vi) for (w, v) in a]
			a = merge(a, b)
			n //= 2
		print(best(L, a, dp[n]))
main()


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(n,) = map(int, readline().split())
vw = [[0, 0]] + [list(map(int, readline().split())) for _ in range(n)]

def merge(av, aw, bv, bw):
	(la, lb) = (len(aw), len(bw))
	rv = [0] * (la + lb)
	rw = [0] * (la + lb)
	ia = ib = 0
	for i in range(la + lb):
		if ib == lb or (ia < la and aw[ia] < bw[ib]):
			rv[i] = av[ia]
			rw[i] = aw[ia]
			ia += 1
		else:
			rv[i] = bv[ib]
			rw[i] = bw[ib]
			ib += 1
	return (rv, rw)
A = 10
N = min(1 << A, n + 1)
memov = [[] for _ in range(N)]
memow = [[] for _ in range(N)]
memov[0] = [0]
memow[0] = [0]
for i in range(1, N):
	(v, w) = vw[i]
	m2v = [v + v1 for v1 in memov[i >> 1]]
	m2w = [w + w1 for w1 in memow[i >> 1]]
	(memov[i], memow[i]) = merge(memov[i >> 1], memow[i >> 1], m2v, m2w)
	for j in range(1, len(memov[i])):
		memov[i][j] = max(memov[i][j - 1], memov[i][j])

def solve(lstv, lstw, dv, dw, l):
	ans = 0
	idx = len(lstw) - 1
	for (v, w) in zip(dv, dw):
		while idx >= 0 and lstw[idx] + w > l:
			idx -= 1
		if idx >= 0 and v + lstv[idx] > ans:
			ans = v + lstv[idx]
	print(ans)
(q,) = map(int, readline().split())
for _ in range(q):
	(u, l) = map(int, readline().split())
	dv = [0]
	dw = [0]
	while u >= N:
		(v, w) = vw[u]
		m2v = [v + v1 for v1 in dv]
		m2w = [w + w1 for w1 in dw]
		(dv, dw) = merge(dv, dw, m2v, m2w)
		u >>= 1
	solve(memov[u], memow[u], dv, dw, l)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(n,) = map(int, readline().split())
vw = [(0, 0)] + [tuple(map(int, readline().split())) for _ in range(n)]
A = 10
N = min(1 << A, n + 1)
memo = [None for _ in range(N)]
L = 10 ** 5 + 1
memo[0] = [0] * L
for i in range(1, N):
	m = memo[i >> 1][:]
	(v, w) = vw[i]
	for j in range(L - 1, w - 1, -1):
		if m[j] < m[j - w] + v:
			m[j] = m[j - w] + v
	memo[i] = m
(q,) = map(int, readline().split())
ans_ = [0] * q
for _ in range(q):
	(u, l) = map(int, readline().split())
	m = u.bit_length() - A
	if m < 0:
		m = 0
	dv = [0] * (1 << m)
	dw = [0] * (1 << m)
	for i in range(m):
		(v, w) = vw[u]
		for j in range(1 << i):
			dv[j + (1 << i)] = dv[j] + v
			dw[j + (1 << i)] = dw[j] + w
		u >>= 1
	ans = 0
	for (v, w) in zip(dv, dw):
		if w <= l:
			val = memo[u][l - w] + v
			if val > ans:
				ans = val
	ans_[_] = ans
print(*ans_, sep='\n')


def main():
	import sys

	def I():
		return int(sys.stdin.readline())

	def LI():
		return list(map(int, sys.stdin.readline().split()))
	n = I()
	V = []
	W = []
	maxL = 10 ** 5
	m = min(n, 1 << 10)
	dp = [[0] * (maxL + 1)]
	for i in range(n):
		(v, w) = LI()
		if i <= m:
			d_ = dp[i + 1 >> 1][:]
			for j in range(w, maxL + 1)[::-1]:
				d_[j] = max(d_[j], d_[j - w] + v)
			dp.append(d_)
		V.append(v)
		W.append(w)
	q = I()
	for i in range(q):
		(v, L) = LI()
		if v <= m:
			print(dp[v][L])
			continue
		cnt = 0
		v_ = []
		w_ = []
		while v > m:
			v_.append(V[v - 1])
			w_.append(W[v - 1])
			v >>= 1
			cnt += 1
		ret = dp[v][L]
		v_tmp = [0] * (1 << cnt)
		w_tmp = [0] * (1 << cnt)
		for b in range(1, 1 << cnt):
			lsb = b & -b
			l = lsb.bit_length()
			w_t = w_tmp[b - lsb] + w_[l - 1]
			w_tmp[b] = w_t
			if w_t <= L:
				v_t = v_tmp[b - lsb] + v_[l - 1]
				v_tmp[b] = v_t
				ret = max(ret, v_t + dp[v][L - w_t])
		print(ret)
	return
main()


import sys

def solve():
	input = sys.stdin.buffer.readline
	LI = lambda : map(int, input().split())
	II = lambda : int(input())
	n = II()
	vw = [[]] * n
	M = 10 ** 5 + 1
	M0 = [0] * M
	XX = 1 << 10
	d = [[]] * XX
	d[0] = M0
	for i in range(1, min(XX, n + 1)):
		(v, w) = LI()
		vw[i - 1] = (v, w)
		di = d[i // 2][:]
		for j in range(M - 1, w - 1, -1):
			if di[j] < di[j - w] + v:
				di[j] = di[j - w] + v
		d[i] = di
	for i in range(XX, n + 1):
		(v, w) = LI()
		vw[i - 1] = (v, w)
	Vv = [i.bit_length() for i in range(1 << 18)]
	n = [pow(2, i) for i in range(18)]
	lentl = [i - 10 for i in range(19)]
	maskset = [[]] * n[10]
	for i in range(1, 11):
		for mask in range(n[i - 1], n[i]):
			a = mask & -mask
			b = Vv[a] - 1
			maska = mask - a
			maskset[mask - 1] = (mask, b, maska)
	for _ in range(II()):
		(V, L) = LI()
		if V < XX:
			print(d[V][L])
			continue
		n2 = lentl[Vv[V]]
		vw2 = [None] * n2
		for i in range(n2):
			vw2[i] = (vw[V - 1][0], vw[V - 1][1])
			V //= 2
		lw = [0] * n[n2]
		lv = [0] * n[n2]
		dv = d[V]
		ans = dv[L]
		for i in range(n[n2] - 1):
			(mask, b, maska) = maskset[i]
			(v, w) = vw2[b]
			ww = lw[maska] + w
			Lww = L - ww
			lw[mask] = ww
			if Lww < 0:
				continue
			vv = lv[maska] + v
			lv[mask] = vv
			tmp = dv[Lww] + vv
			if tmp > ans:
				ans = tmp
		print(ans)
	return
solve()


def main():
	import sys
	input = sys.stdin.readline
	n = int(input())
	L_MAX = 10 ** 5
	D_TH = 10
	V_MAX = (1 << D_TH) - 1
	dp = [[0] * (L_MAX + 1)]
	items_v = []
	items_w = []
	for i in range(n):
		(val, w) = map(int, input().split())
		if i < V_MAX:
			i1 = i + 1
			i0 = i + 1 >> 1
			dp_ = dp[i0][:]
			for j in range(w, L_MAX + 1)[::-1]:
				if dp_[j] < dp_[j - w] + val:
					dp_[j] = dp_[j - w] + val
			dp.append(dp_)
		else:
			items_v.append(val)
			items_w.append(w)
	q = int(input())
	for _ in range(q):
		(v, l) = map(int, input().split())
		v -= 1
		if v < V_MAX:
			ans = dp[v + 1][l]
		else:
			vv = []
			ww = []
			while v >= V_MAX:
				vv.append(items_v[v - V_MAX])
				ww.append(items_w[v - V_MAX])
				v = v - 1 >> 1
			ans = dp[v + 1][l]
			m2 = 1 << len(vv)
			v_sub = [0] * m2
			w_sub = [0] * m2
			for bit in range(1, m2):
				bit_min = bit & -bit
				x = bit_min.bit_length() - 1
				s_w = w_sub[bit - bit_min] + ww[x]
				w_sub[bit] = s_w
				if s_w <= l:
					s_val = v_sub[bit - bit_min] + vv[x]
					v_sub[bit] = s_val
					ans = max(ans, dp[v + 1][l - s_w] + s_val)
		print(ans)
main()


import sys, random, time, bisect
input = sys.stdin.buffer.readline
start = time.time()
N = int(input())
vw = [(-1, -1)]
for i in range(N):
	vw.append(tuple(map(int, input().split())))
dp = [[] for i in range(2 ** 9)]

def make_dp(v):
	t = [[0, 0] for i in range(15)]
	V = v
	id = 0
	while v >= 1:
		t[id] = vw[v]
		id += 1
		v //= 2
	n = id
	temp = [[0, 0] for i in range(2 ** n)]
	for i in range(n):
		for j in range(2 ** i, 2 ** (i + 1)):
			temp[j][0] = temp[j - 2 ** i][0] + t[i][0]
			temp[j][1] = temp[j - 2 ** i][1] + t[i][1]
	temp.sort(key=lambda x: x[1])
	while temp and temp[-1][1] > 10 ** 5:
		temp.pop()
	m = len(temp)
	for i in range(1, m):
		temp[i][0] = max(temp[i][0], temp[i - 1][0])
	dp[V] = [0] * (10 ** 5 + 1)
	for i in range(m - 1):
		L = temp[i][1]
		R = temp[i + 1][1]
		for j in range(L, R):
			dp[V][j] = temp[i][0]
	else:
		L = temp[-1][1]
		for j in range(L, 10 ** 5 + 1):
			dp[V][j] = temp[-1][0]
MAX = min(2 ** 9, N + 1)
for i in range(1, MAX):
	make_dp(i)
Q = int(input())
query = [[] for i in range(N + 1)]
for i in range(Q):
	(v, L) = map(int, input().split())
	query[v].append((L, i))
ans = [0] * Q
temp = [[0, 0] for i in range(2 ** 9)]
t = [[0, 0] for i in range(15)]

def solve(v):
	V = v
	id = 0
	while v >= 2 ** 9:
		t[id] = vw[v]
		id += 1
		v //= 2
	n = id
	for i in range(n):
		for j in range(2 ** i, 2 ** (i + 1)):
			temp[j][0] = temp[j - 2 ** i][0] + t[i][0]
			temp[j][1] = temp[j - 2 ** i][1] + t[i][1]
	for (L, ID) in query[V]:
		res = 0
		for i in range(2 ** n):
			if L >= temp[i][1]:
				res = max(res, temp[i][0] + dp[v][L - temp[i][1]])
		ans[ID] = res
for i in range(1, N + 1):
	if query[i]:
		solve(i)
for i in range(Q):
	print(ans[i])


from sys import stdin
import bisect
readline = stdin.readline
bisect_right = bisect.bisect_right
n = int(readline())
v = [0] * n
w = [0] * n
for i in range(n):
	(v[i], w[i]) = map(int, readline().split())
max_l = 10 ** 5
vshift = 21
mask = (1 << vshift) - 1
dp = [None] * min(n, 2 ** 12)
dp[0] = [(0 << vshift) + 0, (w[0] << vshift) + v[0]]
for u in range(1, len(dp)):
	parent = (u - 1) // 2
	ls = dp[parent][:]
	ls.extend((x + (w[u] << vshift) + v[u] for x in dp[parent] if (x >> vshift) + w[u] <= max_l))
	ls.sort()
	tail = 0
	for i in range(1, len(ls)):
		if ls[tail] >> vshift == ls[i] >> vshift:
			ls[tail] = ls[i]
		elif ls[tail] & mask < ls[i] & mask:
			tail += 1
			ls[tail] = ls[i]
	del ls[tail + 1:]
	dp[u] = ls

def solve(u, l):
	if u < len(dp):
		x = bisect_right(dp[u], (l << vshift) + mask) - 1
		return dp[u][x] & mask
	parent = (u - 1) // 2
	s = solve(parent, l)
	if l >= w[u]:
		s = max(s, v[u] + solve(parent, l - w[u]))
	return s
q = int(readline())
for i in range(q):
	(u, l) = map(int, readline().split())
	print(solve(u - 1, l))


import sys

def get_solve():
	cache = [None] * precalc_limit
	cache[0] = [0] * (weight_limit + 1)
	_vvv = vvv
	_www = www
	_weight_limit = weight_limit

	def _f(u):
		if cache[u] is not None:
			return cache[u]
		dp = _f(u >> 1).copy()
		v = _vvv[u]
		w = _www[u]
		for x in range(_weight_limit, w - 1, -1):
			nv = dp[x - w] + v
			if dp[x] < nv:
				dp[x] = nv
		cache[u] = dp
		return dp
	return _f
(n, *inp) = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]
weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)
solve = get_solve()
buf = []
mp = iter(inp[n * 2 + 1:])
for (u, l) in zip(mp, mp):
	if u < precalc_limit:
		dp = solve(u)
		buf.append(dp[l])
		continue
	dp_w = [0]
	dp_v = [0]
	while u >= precalc_limit:
		v = vvv[u]
		w = www[u]
		for i in range(len(dp_w)):
			nw = dp_w[i] + w
			if nw > l:
				continue
			nv = dp_v[i] + v
			dp_w.append(nw)
			dp_v.append(nv)
		u >>= 1
	ans = 0
	dp = solve(u)
	for (w, v) in zip(dp_w, dp_v):
		nv = v + dp[l - w]
		if ans < nv:
			ans = nv
	buf.append(ans)
print('\n'.join(map(str, buf)))


import sys
(n, *inp) = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]
weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)
precalc = [[0] * (weight_limit + 1)]
for u in range(1, precalc_limit):
	v = vvv[u]
	w = www[u]
	dp = precalc[u >> 1][:]
	for x in range(weight_limit, w - 1, -1):
		nv = dp[x - w] + v
		if dp[x] < nv:
			dp[x] = nv
	precalc.append(dp)
buf = []
mp = iter(inp[n * 2 + 1:])
for (u, l) in zip(mp, mp):
	if u < precalc_limit:
		buf.append(precalc[u][l])
		continue
	dp_w = [0]
	dp_v = [0]
	while u >= precalc_limit:
		v = vvv[u]
		w = www[u]
		for i in range(len(dp_w)):
			nw = dp_w[i] + w
			if nw > l:
				continue
			nv = dp_v[i] + v
			dp_w.append(nw)
			dp_v.append(nv)
		u >>= 1
	ans = 0
	for (w, v) in zip(dp_w, dp_v):
		nv = v + precalc[u][l - w]
		if ans < nv:
			ans = nv
	buf.append(ans)
print('\n'.join(map(str, buf)))


import sys
input = sys.stdin.readline
N = int(input())
LIMIT = min(N, 4195)
V = [0] * N
W = [0] * N
for i in range(N):
	(nV, nW) = map(int, input().split())
	V[i] = nV
	W[i] = nW
pre = [[] for i in range(LIMIT)]
for i in range(LIMIT):
	if i == 0:
		pre[i] = [(0, 0), (W[i], V[i])]
		continue
	curr = pre[i]
	prev = pre[(i - 1) // 2]
	(nV, nW) = (V[i], W[i])
	size = len(prev)
	left = 0
	right = 0
	while left < size or right < size:
		if left == size or prev[left][0] > prev[right][0] + nW or (prev[left][0] == prev[right][0] + nW and prev[left][1] < prev[right][1] + nV):
			if len(curr) == 0 or prev[right][1] + nV > curr[-1][1]:
				curr.append((prev[right][0] + nW, prev[right][1] + nV))
			right += 1
		else:
			if len(curr) == 0 or prev[left][1] > curr[-1][1]:
				curr.append(prev[left])
			left += 1
Q = int(input())
out = [0] * Q
for t in range(Q):
	(vert, L) = map(int, input().split())
	vert -= 1
	stack = []
	while vert >= LIMIT:
		stack.append((V[vert], W[vert]))
		vert = (vert - 1) // 2
	prev = pre[vert]
	best = 0
	for i in range(1 << len(stack)):
		sV = 0
		sW = 0
		red = i
		for (nV, nW) in stack:
			if red & 1:
				sV += nV
				sW += nW
			red >>= 1
		limit = L - sW
		if limit < 0:
			continue
		lo = -1
		hi = len(prev)
		while hi - lo > 1:
			test = (hi + lo) // 2
			if prev[test][0] <= limit:
				lo = test
			else:
				hi = test
		if lo >= 0:
			new = prev[lo][1] + sV
			best = max(best, new)
	out[t] = best
print('\n'.join(map(str, out)))