Pied Piper is a startup company trying to build a new Internet called Pipernet. Currently, they have $A$ users and they gain $X$ users everyday. There is also another company called Hooli, which has currently $B$ users and gains $Y$ users everyday.
Whichever company reaches $Z$ users first takes over Pipernet. In case both companies reach $Z$ users on the same day, Hooli takes over.
Hooli is a very evil company (like E-Corp in Mr. Robot or Innovative Online Industries in Ready Player One). Therefore, many people are trying to help Pied Piper gain some users.
Pied Piper has $N$ supporters with contribution values $C_1, C_2, \ldots, C_N$. For each valid $i$, when the $i$-th supporter contributes, Pied Piper gains $C_i$ users instantly. After contributing, the contribution value of the supporter is halved, i.e. $C_i$ changes to $\left\lfloor C_i / 2 \right\rfloor$. Each supporter may contribute any number of times, including zero. Supporters may contribute at any time until one of the companies takes over Pipernet, even during the current day.
Find the minimum number of times supporters must contribute (the minimum total number of contributions) so that Pied Piper gains control of Pipernet.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains six space-separated integers $N$, $A$, $B$, $X$, $Y$ and $Z$.
- The second line contains $N$ space-separated integers $C_1, C_2, \ldots, C_N$ — the initial contribution values.

-----Output-----
For each test case, if Hooli will always gain control of Pipernet, print a single line containing the string "RIP" (without quotes). Otherwise, print a single line containing one integer — the minimum number of times supporters must contribute.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N \le 10^5$
- $1 \le A, B, X, Y, Z \le 10^9$
- $A, B < Z$
- $0 \le C_i \le 10^9$ for each valid $i$

-----Example Input-----
3
3 10 15 5 10 100
12 15 18
3 10 15 5 10 100
5 5 10
4 40 80 30 30 100
100 100 100 100

-----Example Output-----
4
RIP
1

-----Explanation-----
Example case 1: After $8$ days, Pied Piper will have $50$ users and Hooli will have $95$ users. Then, if each supporter contributes once, Pied Piper will also have $95$ users. After that, they still need $5$ more users, so supporter $3$ can contribute again, with $18/2 = 9$ more users. So the answer will be $4$.
Example case 2: There is no way to beat Hooli.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
import heapq
from math import ceil
for _ in range(int(input())):
	(n, a, b, x, y, z) = list(map(int, input().split()))
	c = [-int(i) for i in input().split()]
	heapq.heapify(c)
	days = ceil((z - b) / y)
	pig = z - a
	if ceil((pig + 2 * sum(c)) / x) >= days:
		print('RIP')
	else:
		ans = 0
		while ceil(pig / x) >= days and any(c):
			use = -heapq.heappop(c)
			pig -= use
			heapq.heappush(c, -(use >> 1))
			ans += 1
		if ceil(pig / x) >= days:
			print('RIP')
		else:
			print(ans)


import heapq
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	days = (z - b + y - 1) // y - 1
	reqcont = z - a - days * x
	l = list(map(int, input().split()))
	for i in range(n):
		l[i] = -l[i]
	heapq.heapify(l)
	c = 0
	rem = 0
	while reqcont > 0:
		if not l:
			print('RIP')
			break
		rem = heapq.heappop(l)
		if -rem // 2 > 0:
			heapq.heappush(l, -(-rem // 2))
		reqcont += rem
		c += 1
	else:
		print(c)


import heapq
t = int(input())
for z in range(t):
	(n, bal1, bal2, inc1, inc2, target) = map(int, input().split())
	arr = [-int(x) for x in input().split()]
	req2 = target - bal2
	count = 0
	flag = 0
	multiplyer = int(req2 / inc2)
	bal1 += multiplyer * inc1
	if bal1 >= target:
		print(count)
		flag = 1
		continue
	heapq.heapify(arr)
	while len(arr):
		temp = heapq.heappop(arr)
		bal1 += -temp
		if temp == 0:
			break
		count += 1
		temp = int(temp / 2)
		heapq.heappush(arr, temp)
		if bal1 > target:
			print(count)
			flag = 1
			break
	if flag == 0:
		print('RIP')


import heapq as hq
t = int(input())
while t:
	t -= 1
	(n, a, b, x, y, z) = map(int, input().strip().split(' '))
	l = list(map(int, input().strip().split(' ')))
	for i in range(n):
		l[i] = -l[i]
	hq.heapify(l)
	days = (z - b) // y
	if b + days * y == z:
		days -= 1
	done = a + days * x
	count = 0
	while len(l) != 0 and done < z:
		tmp = hq.heappop(l)
		tmp = -tmp
		done += tmp
		count += 1
		tmp = tmp // 2
		if tmp > 0:
			hq.heappush(l, -tmp)
	if done < z:
		print('RIP')
	else:
		print(count)


import heapq
t = int(input().strip())
for _ in range(t):
	(n, a, b, x, y, z) = map(int, input().strip().split())
	c = list(map(int, input().strip().split()))
	for i in range(n):
		c[i] = -1 * c[i]
	heapq.heapify(c)
	days = (z - b) // y
	anew = a + x * days
	bnew = b + y * days
	if anew > z:
		print('0')
	else:
		if bnew == z:
			goal = z + 1
		else:
			goal = z
		cnt = 0
		while anew < goal and len(c) > 0:
			temp = -1 * heapq.heappop(c)
			anew += temp
			cnt += 1
			if temp != 1:
				heapq.heappush(c, -1 * (temp // 2))
		if anew < goal:
			print('RIP')
		else:
			print(cnt)


import heapq
from math import ceil
for _ in range(int(input())):
	(N, A, B, X, Y, Z) = map(int, input().split())
	C = list(map(int, input().split()))
	heap = [-contrib for contrib in C]
	heapq.heapify(heap)
	hooli_days = ceil((Z - B) / Y)
	piper_init_gap = Z - A
	if ceil((piper_init_gap - 2 * sum(C)) / X) >= hooli_days:
		print('RIP')
	else:
		num_contribs = 0
		while ceil(piper_init_gap / X) >= hooli_days and any(heap):
			contrib = -heapq.heappop(heap)
			piper_init_gap -= contrib
			heapq.heappush(heap, -(contrib >> 1))
			num_contribs += 1
		if ceil(piper_init_gap / X) < hooli_days:
			print(num_contribs)
		else:
			print('RIP')


import heapq as hq
from math import floor
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	arr = [-int(i) for i in input().split()]
	days = floor((z - b - 1) / y)
	ans = 0
	hq.heapify(arr)
	curr = a + days * x
	while curr < z:
		u = hq.heappop(arr)
		u = -u
		if u == 0:
			break
		else:
			curr += u
			ans += 1
			hq.heappush(arr, -(u // 2))
	if curr >= z:
		print(ans)
	else:
		print('RIP')


import math
import heapq
for z in range(int(input())):
	(n, a, b, x, y, z) = tuple(map(int, input().split()))
	c = list(map(int, input().split()))
	d_day = math.ceil((z - b) / y)
	own_score = a + x * (d_day - 1)
	short = z - own_score
	c = [-x for x in c]
	heapq.heapify(c)
	cnt = 0
	while short >= 0 and len(c) > 0:
		num = abs(heapq.heappop(c))
		short -= num
		cnt += 1
		num //= 2
		if num > 0:
			heapq.heappush(c, -num)
	if short >= 0:
		print('RIP')
	else:
		print(cnt)


import copy
from collections import *
import math

def solve(W, d, z):
	W.sort(reverse=True)
	C = deque(W)
	Q = deque()
	n = 0
	if d >= z:
		return n
	while True:
		if len(C) == 0 and len(Q) == 0:
			break
		if not Q or C[0] > Q[0]:
			contr = C.popleft()
			d = d + contr
			n += 1
			if d >= z:
				return n
			if contr // 2 >= 1:
				Q.append(contr // 2)
		else:
			contr = Q.popleft()
			d = d + contr
			n += 1
			if d >= z:
				return n
			if contr // 2 >= 1:
				Q.append(contr // 2)
		if not C:
			(C, Q) = (Q, C)
	if d >= z:
		return n
	return 'RIP'
T = int(input())
for t in range(T):
	riga = input().split()
	riga = [int(a) for a in riga]
	N = riga[0]
	A = riga[1]
	B = riga[2]
	X = riga[3]
	Y = riga[4]
	Z = riga[5]
	riga = input().split()
	W = [int(a) for a in riga]
	timeB = math.ceil((Z - B) / Y)
	g = timeB - 1
	pied = A + g * X
	if pied >= Z:
		print(0)
	else:
		print(solve(W, pied, Z))


import numpy as np
import heapq as h
t = int(input())
while t > 0:
	t = t - 1
	l = input().split(' ')
	n = int(l[0])
	a = int(l[1])
	b = int(l[2])
	x = int(l[3])
	y = int(l[4])
	z = int(l[5])
	count = 0
	cont = []
	c = input().split(' ')
	for i in range(n):
		h.heappush(cont, -int(c[i]))
	j = 1
	deadline = (z - b) // y
	rem = z - (a + deadline * x)
	while rem > 0:
		q = rem
		p = h.heappop(cont)
		h.heappush(cont, -(-p // 2))
		rem = rem + p
		count = count + 1
		if q == rem:
			j = 0
			break
	if j == 1:
		print(count)
	else:
		print('RIP')


import bisect as bs
from collections import deque
import heapq as hp
import math

def check1(a, b, x, y, z, val):
	if math.ceil((z - a - val) / x) < math.ceil((z - b) / y):
		return True
	return False
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	arr = list(map(int, input().split()))
	val = 0
	arr.sort(reverse=True)
	c = 0
	q1 = deque(arr)
	q2 = deque()
	while q1 or q2:
		if check1(a, b, x, y, z, val):
			print(c)
			break
		if not q2 or q1[0] > q2[0]:
			p = q1.popleft()
			val += p
			c += 1
			if p // 2:
				q2.append(p // 2)
		elif q2 and q2[0] >= q1[0]:
			p = q2.popleft()
			val += p
			c += 1
			if p // 2:
				q2.append(p // 2)
		if not q1 and q2:
			(q1, q2) = (q2, q1)
	else:
		print('RIP')


import heapq
for _ in range(int(input())):
	(n, a, b, x, y, z) = [int(x) for x in input().split()]
	h = [-int(x) for x in input().split()]
	timeA = 0
	timeB = (z - b) // y + (0 if (z - b) % y == 0 else 1)
	total = a
	totalB = b
	diff = (z - b) // y * x
	if total + diff > z:
		print(0)
	elif total + diff != z:
		total += diff
		heapq.heapify(h)
		while total < z and n > 0:
			max_user = -h[0]
			timeA += 1
			if max_user // 2 != 0:
				heapq.heappushpop(h, -(max_user // 2))
			else:
				heapq.heappop(h)
				n -= 1
			total += max_user
		print(timeA if total >= z else 'RIP')


import heapq
t = int(input())
for _ in range(t):
	(n, a, b, x, y, z) = map(int, input().split())
	c = [-int(x) for x in input().split()]
	heapq.heapify(c)
	k = int((z - b) / y)
	ans = 0
	if a + k * x > z:
		print(ans)
	elif a + k * x != z:
		a += k * x
		while a < z:
			temp = heapq.heappop(c)
			if temp == 0:
				break
			a += -temp
			ans += 1
			heapq.heappush(c, int(temp / 2))
		if a < z:
			print('RIP')
		else:
			print(ans)
	else:
		print('RIP')


import heapq
import math

def isLose(a, b, x, y, z):
	t1 = math.ceil((z - a) / x)
	t2 = math.ceil((z - b) / y)
	return t1 >= t2
t = int(input())
for i in range(t):
	(n, a, b, x, y, z) = map(int, input().split())
	arr = [-int(x) for x in input().split()]
	heapq.heapify(arr)
	ans = 0
	if b >= z:
		print('RIP')
	elif a >= z:
		print(0)
	else:
		t1 = math.ceil((z - a) / x)
		t2 = math.ceil((z - b) / y)
		if t1 < t2:
			print(0)
		elif math.ceil((z - a + 2 * sum(arr)) / x) >= t2:
			print('RIP')
		else:
			while arr[0] != 0 and isLose(a, b, x, y, z):
				ans += 1
				top = -1 * heapq.heappop(arr)
				a += top
				heapq.heappush(arr, -1 * (top // 2))
			if isLose(a, b, x, y, z):
				print('RIP')
			else:
				print(ans)


from collections import deque
import heapq as hq
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	c = list(map(int, input().split()))
	t2 = (z - b) // y
	t1 = a + x * t2
	c = [-x for x in c]
	hq.heapify(c)
	s = 0
	ans = 0
	while t1 + s < z:
		temp = hq.heappop(c)
		s += abs(temp)
		if temp == 0:
			break
		ans += 1
		temp = -temp
		temp = -(temp // 2)
		hq.heappush(c, temp)
	if s + t1 < z:
		print('RIP')
	else:
		print(ans)


import heapq
import math
for i in range(int(input())):
	(n, a, b, x, y, z) = list(map(int, input().split()))
	cntrbtns = [-int(x) for x in input().split()]
	if b >= z:
		print('RIP')
		continue
	t = math.ceil((z - b) / y)
	sum = a + x * (t - 1)
	c = 0
	heapq.heapify(cntrbtns)
	ele = 0
	while True:
		if sum >= z:
			print(c)
			break
		ele = -ele
		ele = heapq.heappushpop(cntrbtns, -(ele >> 1))
		if ele == 0:
			print('RIP')
			break
		sum -= ele
		c += 1


import heapq
from math import ceil, floor
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	s = [-int(i) for i in input().split()]
	days = floor((z - b) / y)
	current = a + days * x
	if b + days * y == z:
		z += 1
	count = 0
	heapq.heapify(s)
	while current < z:
		ret = heapq.heappop(s)
		ret = -ret
		if ret == 0:
			break
		else:
			current += ret
			heapq.heappush(s, -(ret // 2))
		count += 1
	print(count) if current >= z else print('RIP')


import heapq
from math import ceil
for i in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	cntrbtns = [-int(x) for x in input().split()]
	if b >= z:
		print('RIP')
		continue
	sum = a + x * (ceil((z - b) / y) - 1)
	c = 0
	heapq.heapify(cntrbtns)
	ele = 0
	while sum < z and any(cntrbtns):
		ele = -heapq.heappop(cntrbtns)
		sum += ele
		heapq.heappush(cntrbtns, -(ele >> 1))
		c += 1
	print(['RIP', c][sum >= z])


import heapq
t = int(input())
for _ in range(t):
	(n, a, b, x, y, z) = input().split()
	a = int(a)
	b = int(b)
	x = int(x)
	y = int(y)
	z = int(z)
	c = [-int(i) for i in input().split() if int(i) > 0]
	heapq.heapify(c)
	count = 0
	bd = (z - b) // y
	a += x * bd
	if a > z:
		print(count)
		continue
	while True:
		temp = -heapq.heappop(c)
		if a > z or temp == 0:
			break
		a += temp
		count += 1
		heapq.heappush(c, -(temp // 2))
	if a > z:
		print(count)
	else:
		print('RIP')


import heapq
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	ans = 0
	pri1 = list(map(int, input().split()))
	pri = [-x for x in pri1]
	heapq.heapify(pri)
	if b >= z:
		print('RIP')
		continue
	p = (z - 1 - b) // y
	a = a + x * p
	while a < z:
		mx = -heapq.heappop(pri)
		if mx == 0:
			break
		else:
			a += mx
			ans += 1
			heapq.heappush(pri, -(mx // 2))
	if a >= z:
		print(ans)
	else:
		print('RIP')


import heapq as heap
t = int(input())
while t:
	(n, a, b, x, y, z) = map(int, input().split())
	l = list(map(int, input().split()))
	days = (z - b) // y
	new = a + x * days
	l = [-x for x in l]
	heap.heapify(l)
	s = 0
	c = 0
	while new + s < z:
		temp = heap.heappop(l)
		s = s + abs(temp)
		if temp == 0:
			break
		c += 1
		temp = -temp
		temp = -(temp // 2)
		heap.heappush(l, temp)
	if new + s < z:
		print('RIP')
	else:
		print(c)
	t -= 1


from collections import deque
import heapq as hq
from math import ceil
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	arr = list(map(int, input().split()))
	val = (z - b) // y
	newVal = a + x * val
	arr.sort(reverse=True)
	d1 = deque(arr)
	d2 = deque([])
	support = 0
	count = 0
	while support + newVal < z:
		t = support
		if len(d1) == 0:
			break
		if not d2 or d1[0] >= d2[0]:
			temp = d1.popleft()
			if temp == 0:
				break
			count += 1
			support += temp
			temp = temp // 2
			d2.append(temp)
		else:
			temp = d2.popleft()
			count += 1
			support += temp
			temp = temp // 2
			d2.append(temp)
		if len(d1) == 0:
			(d1, d2) = (d2, d1)
	if support + newVal < z:
		print('RIP')
	else:
		print(count)


import heapq
t = int(input().strip())
for tc in range(t):
	(n, a, b, x, y, z) = map(int, input().strip().split())
	c = list(map(int, input().strip().split()))
	for i in range(n):
		c[i] = -1 * c[i]
	heapq.heapify(c)
	num_days_left = (z - b) // y
	a_gained_users = a + x * num_days_left
	b_gained_users = b + y * num_days_left
	if a_gained_users > z:
		print('0')
	else:
		if b_gained_users == z:
			users_required = z + 1
		else:
			users_required = z
		cnt = 0
		while a_gained_users < users_required and len(c) > 0:
			contrib_from_supporter = -1 * heapq.heappop(c)
			a_gained_users += contrib_from_supporter
			cnt += 1
			if contrib_from_supporter != 1:
				heapq.heappush(c, -1 * (contrib_from_supporter // 2))
		if a_gained_users < users_required:
			print('RIP')
		else:
			print(cnt)


t = int(input())
import heapq
import sys
from math import ceil
for i in range(t):
	(n, a, b, x, y, z) = map(int, input().split())
	l = list(map(int, input().split()))
	for i in range(n):
		l[i] = -1 * l[i]
	z1 = ceil((z - a) / x) + 1
	z2 = ceil((z - b) / y) + 1
	ba = []
	if z1 < z2:
		print(0)
	else:
		k = z2 - 1
		f = a + (k - 1) * x
		count1 = 0
		flag = 0
		heapq.heapify(l)
		while True:
			if f >= z:
				flag = 1
				break
			if l == []:
				break
			u = heapq.heappop(l)
			if u // 2 != 0:
				heapq.heappush(l, -1 * (abs(u) // 2))
			f += abs(u)
			count1 += 1
		if flag == 0:
			print('RIP')
		else:
			print(count1)


import heapq
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	l = [-int(i) for i in input().split()]
	diff = y - x
	base = b - a
	gotillz = 0
	piedz = 0
	from math import ceil
	z1 = z - 1
	hooliz = (z - b) / y
	if hooliz == int(hooliz):
		days = hooliz - 1
	else:
		days = int(hooliz)
	piedz = a + days * x
	if piedz >= z:
		print(0)
		continue
	else:
		req = z - piedz
		heapq.heapify(l)
		cnt = 0
		c = 0
		while l and c < req:
			curr = -heapq.heappop(l)
			c += curr
			cnt += 1
			if curr // 2 == 0:
				pass
			else:
				heapq.heappush(l, -(curr // 2))
		if c >= req:
			print(cnt)
		else:
			print('RIP')


from math import ceil, floor
import heapq
t = int(input())
while t:
	t -= 1
	(n, a, b, x, y, z) = map(int, input().split())
	li = [-int(x) for x in input().split()]
	i = ceil((z - b) / y - 1)
	a = a + i * x
	b = b + i * y
	c = 0
	heapq.heapify(li)
	while a < z and n != 0:
		f = -li[0]
		a += f
		c += 1
		y = floor(f / 2)
		if y != 0:
			heapq.heappushpop(li, -y)
		else:
			heapq.heappop(li)
			n -= 1
	if a >= z:
		print(c)
	else:
		print('RIP')


import heapq
R = lambda : map(int, input().split())
t = int(input())
for _ in range(t):
	(n, a, b, x, y, z) = R()
	c = [-x for x in R()]
	heapq.heapify(c)
	a -= (b - z) // y * x + x
	i = 0
	while a < z and c[0]:
		m = heapq.heappop(c)
		a -= m
		heapq.heappush(c, (m + 1) // 2)
		i += 1
	print((i, 'RIP')[a < z])


import heapq

def m():
	t = int(input())
	while t > 0:
		(n, a, b, x, y, z) = map(int, input().split())
		l = list(map(int, input().split()))
		for i in range(n):
			l[i] = -l[i]
		val1 = z - a
		val2 = z - b
		day1 = val1 / x
		if day1 == int(day1):
			day1 = int(day1)
		else:
			day1 = int(day1) + 1
		day2 = val2 / y
		if day2 == int(day2):
			day2 = int(day2)
		else:
			day2 = int(day2) + 1
		k = min(day1, day2)
		k -= 1
		final1 = a + x * k
		final2 = b + y * k
		count = 0
		if day1 < day2:
			print(0)
		else:
			heapq.heapify(l)
			while final1 <= z:
				try:
					a = heapq.heappop(l)
					final1 += -a
					if a != 0:
						count += 1
						heapq.heappush(l, int(a / 2))
				except IndexError:
					break
			if final1 > z:
				print(count)
			elif z >= final1:
				print('RIP')
		t -= 1
m()


import math
import heapq
t = int(input())
while t:
	(n, a, b, x, y, z) = [int(x) for x in input().split()]
	c = [-int(x) for x in input().split()]
	hooli = math.ceil((z - b) / y)
	heapq.heapify(c)
	count = 0
	temp_sum = a + (hooli - 1) * x
	while temp_sum < z and c[0] != 0:
		temp = heapq.heappop(c)
		temp_sum += -1 * temp
		heapq.heappush(c, math.ceil(temp / 2))
		count += 1
	if temp_sum < z:
		print('RIP')
	else:
		print(count)
	t -= 1


import heapq
for _ in range(int(input())):
	(N, A, B, X, Y, Z) = map(int, input().split())
	L = [-int(j) for j in input().split()]
	heapq.heapify(L)
	Di = A - B
	Dr = X - Y
	Fd = (Z - B) / Y
	if Fd == int(Fd):
		Fd = int(Fd - 1)
	else:
		Fd = int(Fd)
	Rem = Z - (A + X * Fd)
	S = 0
	n = 0
	while L != []:
		if S >= Rem:
			print(n)
			break
		Sup = heapq.heappop(L)
		n += 1
		S += -Sup
		if -Sup // 2 != 0:
			heapq.heappush(L, -(-Sup // 2))
	else:
		if S >= Rem:
			print(n)
		else:
			print('RIP')


import heapq
import math
t = int(input())
while t > 0:
	t -= 1
	(n, a, b, x, y, z) = map(int, input().split())
	c = [-1 * int(x) for x in input().split()]
	if math.ceil((z - a) / x) - math.ceil((z - b) / y) < 0:
		print(0)
		continue
	elif 1:
		req = z - (a + x * (math.ceil((z - b) / y) - 1))
		temp = 0
		heapq.heapify(c)
		while req > 0:
			temp += 1
			te = heapq.heappop(c)
			if te == 0:
				print('RIP')
				break
			req += te
			heapq.heappush(c, math.ceil(te / 2))
		if te != 0:
			print(temp)


import heapq
from math import ceil
t = int(input())
for k in range(t):
	(n, a, b, x, y, z) = map(int, input().split())
	c = list(map(int, input().split()))
	cont = [-int(x) for x in c]
	days = int((z - b) / y)
	p_user = days * x + a
	need = z - p_user
	flag = 0
	heapq.heapify(cont)
	count = 0
	if ceil((z - a - 2 * sum(c)) / x) >= days + 1:
		print('RIP')
	elif p_user > z:
		print(0)
	else:
		while p_user < z:
			key = heapq.heappop(cont)
			if key == 0:
				flag = 1
				break
			count += 1
			p_user += -key
			heapq.heappush(cont, int(key / 2))
		if flag == 0:
			print(count)
		else:
			print('RIP')


import heapq
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	l = list(map(int, input().split()))
	dho = (z - b) // y
	a += dho * x
	l = [-x for x in l]
	heapq.heapify(l)
	f = 0
	c = 0
	while a < z:
		k = abs(heapq.heappop(l))
		if k == 0:
			break
		a += k
		c += 1
		heapq.heappush(l, -(k // 2))
	if a < z:
		print('RIP')
	else:
		print(c)


from collections import deque
import math

def solve(nums, d, z):
	q1 = deque(sorted(nums, reverse=True))
	q2 = deque()
	c = 0
	if d >= z:
		return c
	while True:
		if len(q1) == 0 and len(q2) == 0:
			break
		if not q2 or q1[0] > q2[0]:
			ele = q1.popleft()
			c += 1
			d += ele
			if d >= z:
				return c
			ele = ele // 2
			if ele >= 1:
				q2.append(ele)
		else:
			ele = q2.popleft()
			c += 1
			d += ele
			if d >= z:
				return c
			ele = ele // 2
			if ele >= 2:
				q2.append(ele)
		if not q1:
			(q1, q2) = (q2, q1)
	if d >= z:
		return c
	return 'RIP'
t = int(input())
for _ in range(t):
	(n, a, b, x, y, z) = map(int, input().split())
	nums = list(map(int, input().split()))
	queries = set([])
	c = z - b
	c = math.ceil(c / y) - 1
	d = a + x * c
	if d >= z:
		print(0)
	else:
		print(solve(nums, d, z))


import heapq

def func(a):
	return -int(a)
T = int(input())
for i in range(T):
	(N, A, B, X, Y, Z) = list(map(int, input().split()))
	c = list(map(func, input().split()))
	heapq.heapify(c)
	day = (Z - B) // Y
	if (Z - B) % Y != 0:
		day += 1
	dif = Z - (A + (day - 1) * X)
	ans = 0
	while dif > 0:
		m = heapq.heappop(c)
		m = -m
		if m == 0:
			break
		heapq.heappush(c, -(m // 2))
		dif -= m
		ans += 1
	if dif > 0:
		print('RIP')
	else:
		print(ans)


import heapq
from math import ceil
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	c = list(map(int, input().split()))
	for i in range(n):
		c[i] *= -1
	heapq.heapify(c)
	if b >= z:
		print('RIP')
	elif a >= z:
		print(0)
	else:
		da = ceil((z - a) / x)
		db = ceil((z - b) / y)
		if da < db:
			print(0)
		else:
			cont = 0
			da = db - 1
			a += da * x
			while a < z and c[0]:
				cont += 1
				a += abs(heapq.heapreplace(c, -1 * (-1 * c[0] // 2)))
			if a < z:
				print('RIP')
			else:
				print(cont)


import heapq as h
for _ in range(int(input())):
	(n, a, x, b, y, z) = map(int, input().split())
	p = list(map(int, input().split()))
	p = [-i for i in p]
	h.heapify(p)
	if x > z:
		print('RIP')
		continue
	d = (z - x) // y
	a += b * d
	if a > z:
		print(0)
		continue
	c = 0
	while True:
		t = -h.heappop(p)
		if t == 0 or a > z:
			break
		c += 1
		a += t
		h.heappush(p, -(t // 2))
	if a > z:
		print(c)
	else:
		print('RIP')


import sys
from bisect import bisect_left, bisect_right, insort
from collections import deque, Counter
from math import gcd, sqrt, factorial, ceil, log10
from itertools import permutations
from heapq import heappush, heappop, heapify
inf = float('inf')
mod = 1000000007
mini = 1000000007

def ncr(n, r):
	d = 10 ** 9 + 7
	num = fact(n)
	den = fact(r) * fact(n - r) % d
	den = pow(den, d - 2, d)
	return num * den % d

def sieve(n):
	prime = [True for i in range(n + 1)]
	lst = []
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p = p + 1
	for i in range(2, n + 1):
		if prime[i]:
			lst.append(i)
	return lst

def binary(number):
	result = 0
	while number:
		result = result + 1
		number = number & number - 1
	return result

def calculate_factors(n):
	hh = [1] * (n + 1)
	p = 2
	while p * p < n:
		if hh[p] == 1:
			for i in range(p * 2, n, p):
				hh[i] = 0
		p += 1
	total = 1
	for p in range(2, n + 1):
		if hh[p] == 1:
			count = 0
			if n % p == 0:
				while n % p == 0:
					n = int(n / p)
					count += 1
				total *= count + 1
	return total

def prime_factors(n):
	i = 2
	factors = set()
	while i * i <= n:
		if n % i:
			i += 1
		else:
			factors.add(n // i)
			n = n // i
			factors.add(i)
	if n > 1:
		factors.add(n)
	return factors

def isPrime(n):
	if n == 2 or n == 3:
		return True
	if n % 2 == 0 or n < 2:
		return False
	for i in range(3, int(n ** 0.5) + 1, 2):
		if n % i == 0:
			return False
	return True

def solve(n):
	if n == 1:
		return 1
	p = 2
	while p * p <= n:
		if n % p == 0:
			return n // p
		p = p + 1
	return False

def expo(x, n):
	result = 1
	while n > 1:
		if n & 1:
			n = n - 1
			result = result * x
		else:
			n = n // 2
			x = x * x
	return result * x

def change(a):
	return chr(ord(a) + 1)

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

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

def input():
	return sys.stdin.readline().strip()
T = int(input())
while T > 0:
	(n, a, b, c, d, z) = get_ints()
	heap = []
	Arr = get_array()
	min_a = ceil((z - a) / c)
	min_b = ceil((z - b) / d)
	for i in Arr:
		heappush(heap, -1 * i)
	if min_a < min_b:
		print(0)
	else:
		trick = min_b - 1
		effort = a + trick * c
		flag = 0
		count = 0
		while heap != []:
			k = -1 * heappop(heap)
			count += 1
			effort += k
			if effort > z:
				flag = 1
				break
			k = k // 2
			if k != 0:
				heappush(heap, -1 * k)
		if flag == 0:
			print('RIP')
		else:
			print(count)
	T = T - 1


import math
import heapq
for test in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	c = list(map(int, input().split()))
	c = [-x for x in c]
	heapq.heapify(c)
	d = math.ceil((z - b) / y) - 1
	rem = z - (a + x * d)
	count = 0
	prev = -1000000
	for i in range(31 * n):
		if rem <= 0:
			break
		if rem == prev:
			break
		prev = rem
		e = -heapq.heappop(c)
		rem -= e
		e = 0 - e // 2
		heapq.heappush(c, e)
		count += 1
	if rem > 0:
		print('RIP')
	else:
		print(count)


import heapq as heap
for t in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	h = list(map(int, input().split()))
	for i in range(n):
		h[i] *= -1
	heap.heapify(h)
	extra = (z - b - 1) // y
	a += x * extra
	b += y * extra
	ans = 0
	while a < z and h:
		maximum = -1 * heap.heappop(h)
		a += maximum
		ans += 1
		maximum //= 2
		if maximum:
			heap.heappush(h, -1 * maximum)
	if a < z:
		print('RIP')
	else:
		print(ans)


import sys
import math
import heapq
RI = lambda : [int(x) for x in sys.stdin.readline().split()]
rw = lambda : sys.stdin.readline().strip()
ts = int(input())
while ts > 0:
	(n, a, b, x, y, z) = RI()
	con = RI()
	con = [-i for i in con]
	heapq.heapify(con)
	if z - b <= 0:
		print('RIP')
		ts -= 1
		continue
	elif z - a <= 0:
		print(0)
		ts -= 1
		continue
	rema = z - a
	remb = z - b
	daya = math.ceil(rema / x)
	dayb = math.ceil(remb / y)
	if dayb > daya:
		print(0)
		ts -= 1
		continue
	flag = True
	cnt = 0
	temp = (dayb - 1) * x
	rema -= temp
	while rema > 0:
		temp = heapq.heappop(con)
		temp = -temp
		if temp == 0:
			flag = not flag
			break
		rema -= temp
		temp = temp // 2
		temp = -temp
		heapq.heappush(con, temp)
		cnt += 1
	if not flag:
		print('RIP')
		ts -= 1
		continue
	else:
		print(cnt)
	ts -= 1


import heapq

def hpush(h, e):
	h.append(e)
	heapq._siftdown_max(h, 0, len(h) - 1)

def getCount(z, pp, cont):
	heapq._heapify_max(cont)
	count = 0
	while pp < z:
		e = heapq._heappop_max(cont)
		if e == 0:
			return -1
		pp = pp + e
		hpush(cont, e // 2)
		count = count + 1
	return count
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	cont = list(map(int, input().split()))
	d = (z - b) // y
	pp = a + d * x
	res = getCount(z, pp, cont)
	if res == -1:
		print('RIP')
	else:
		print(res)


from heapq import heapify, heappop, heappush
test = int(input())
for i in range(test):
	(cNo, a, b, x, y, z) = map(int, input().split())
	cl1 = list(map(int, input().split()))
	heapify(cl1)
	cl1 = [-i for i in cl1]
	heapify(cl1)
	day = int((z - b) // y)
	a += x * day
	count = 0
	while a <= z:
		ele = heappop(cl1)
		if ele == 0:
			break
		a = a + -ele
		count = count + 1
		heappush(cl1, int(ele / 2))
	if a > z:
		print(count)
	else:
		print('RIP')


import math, heapq
T = int(input())
while T:
	(N, A, B, X, Y, Z) = list(map(int, input().split()))
	C = list(map(int, input().split()))
	k1 = math.ceil((Z - A) / X)
	k2 = math.ceil((Z - B) / Y)
	if k1 < k2:
		print(0)
	else:
		k3 = k2 - 1
		users_still_required = Z - (A + k3 * X)
		C_mod = [-C[i] for i in range(N)]
		heapq.heapify(C_mod)
		count = 0
		is_not_possible = False
		while users_still_required > 0:
			max_contribution_value = -heapq.heappop(C_mod)
			if max_contribution_value == 0:
				is_not_possible = True
				break
			users_still_required -= max_contribution_value
			heapq.heappush(C_mod, -math.floor(max_contribution_value / 2))
			count += 1
		if is_not_possible == True:
			print('RIP')
		else:
			print(count)
	T -= 1


import heapq
for _ in range(int(input())):
	(N, A, B, X, Y, Z) = map(int, input().split())
	C = list(map(int, input().split()))
	asdf = []
	for ty in C:
		heapq.heappush(asdf, -1 * ty)
	e = Z - A
	r = Z - B
	ans = 0
	t = int(r / Y)
	if r % Y == 0:
		t -= 1
	e -= t * X
	qwer = []
	qwerty = 1
	hoga = 0
	if e <= 0:
		print('0')
		continue
	else:
		while qwerty != 0:
			qwerty = -1 * heapq.heappop(asdf)
			heapq.heappush(asdf, -1 * int(qwerty / 2))
			e -= qwerty
			ans += 1
			if e <= 0:
				hoga = 1
				break
		if hoga == 0:
			print('RIP')
		else:
			print(ans)


import heapq
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	c = []
	for ele in map(int, input().split()):
		c.append(0 - ele)
	heapq.heapify(c)
	factor = (z - b) // y
	pieds = a + factor * x
	count = 0
	while pieds < z and len(c) > 0:
		contrib = heapq.heappop(c)
		pieds -= contrib
		contrib = -(-contrib // 2)
		count += 1
		if contrib is not 0:
			heapq.heappush(c, contrib)
	if pieds < z:
		print('RIP')
	else:
		print(count)


import heapq
t = int(input())
while t > 0:
	(n, a, b, x, y, z) = map(int, input().split())
	l = [-int(x) for x in input().split()]
	heapq.heapify(l)
	u = (z - b) // y
	a = a + x * u
	s1 = 0
	if a > z:
		print('0')
	elif a != z:
		sum1 = 0
		while a < z:
			h = heapq.heappop(l)
			if h == 0:
				break
			a = a + -h
			s1 = s1 + 1
			heapq.heappush(l, int(h / 2))
		if a < z:
			print('RIP')
		else:
			print(s1)
	else:
		print('RIP')
	t = t - 1


import heapq
for t in range(int(input())):
	(N, a, b, x, y, z) = map(int, input().split())
	c = list(map(int, input().split()))
	c = [-x for x in c]
	heapq.heapify(c)
	if (z - b) % y == 0:
		n = (z - b) // y - 1
	else:
		n = (z - b) // y
	contrib = z - (a + n * x)
	ans = 0
	while contrib > 0:
		mx = heapq.heappop(c)
		if mx == 0:
			break
		contrib += mx
		ans += 1
		mx *= -1
		mx //= 2
		mx *= -1
		heapq.heappush(c, mx)
	if contrib <= 0:
		print(ans)
	else:
		print('RIP')


import heapq
T = int(input())
while T > 0:
	(N, A, B, X, Y, Z) = [int(x) for x in input().split()]
	C = [-int(x) for x in input().strip().split()]
	heapq.heapify(C)
	days = (Z - B) // Y
	pp = A + X * days
	if pp >= Z:
		print(0)
	else:
		count = 0
		max_c = -heapq.heappop(C)
		while max_c > 0 and pp < Z:
			count += 1
			pp += max_c
			heapq.heappush(C, -(max_c >> 1))
			max_c = -heapq.heappop(C)
		if pp >= Z:
			print(count)
		else:
			print('RIP')
	T -= 1


import heapq
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	arr = list(map(int, input().split()))
	time = (z - b) // y
	ua = a + x * time
	ub = b + y * time
	arr = [-x for x in arr]
	heapq.heapify(arr)
	cnt = 0
	hlp = 0
	while z > ua + hlp:
		chotu = heapq.heappop(arr)
		hlp += -chotu
		cnt += 1
		chotu = -chotu
		chotu = -(chotu // 2)
		if chotu == 0:
			break
		else:
			heapq.heappush(arr, chotu)
	if ua + hlp < z:
		print('RIP')
	else:
		print(cnt)


import heapq
for t in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	pat = list(map(lambda x: int(x) * -1, input().split()))
	heapq.heapify(pat)
	ndays = (z - b) // y
	rem = z - (a + x * ndays)
	count = 0
	while rem > 0 and pat:
		temp = -1 * heapq.heappop(pat)
		rem -= temp
		count += 1
		temp //= 2
		temp *= -1
		if temp:
			heapq.heappush(pat, temp)
	if rem > 0:
		print('RIP')
	else:
		print(count)


import math
import heapq
t = int(input())
for itrg in range(t):
	(n, a, b, x, y, z) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	p = z - b
	p = math.ceil(p / y)
	if p <= 0:
		print('RIP')
		continue
	p -= 1
	p = p * x
	p = z - p
	p = p - a
	if p <= 0:
		print(0)
		continue
	c = p
	arc = n
	for i in arr:
		if i == 0:
			arc -= 1
	for i in range(n):
		arr[i] = -arr[i]
	heapq.heapify(arr)
	ans = 0
	flag = 0
	while 1:
		if c <= 0:
			break
		ans += 1
		ele = heapq.heappop(arr)
		ele = -ele
		c -= ele
		ele = ele // 2
		if ele == 0:
			arc -= 1
		if arc == 0:
			flag = 1
			break
		heapq.heappush(arr, -ele)
	if flag == 1:
		print('RIP')
	else:
		print(ans)


from collections import deque
import heapq as hq
from math import ceil
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	arr = list(map(int, input().split()))
	val = (z - b) // y
	newVal = a + x * val
	arr = [-x for x in arr]
	hq.heapify(arr)
	support = 0
	count = 0
	while newVal + support < z:
		temp = hq.heappop(arr)
		support += abs(temp)
		if temp == 0:
			break
		count += 1
		temp = -temp
		temp = -(temp // 2)
		hq.heappush(arr, temp)
	if support + newVal < z:
		print('RIP')
	else:
		print(count)


from collections import deque
t = int(input())
while t:
	(n, a, b, x, y, z) = map(int, input().split())
	l = list(map(int, input().split()))
	ll = deque
	l = deque(sorted(l, reverse=True))
	ll = deque()
	cd = (z - b) // y
	le = cd * x + a
	c = 0
	if le <= 0:
		print(c)
	else:
		while le < z:
			if len(ll) == 0 and len(l) == 0:
				break
			if not ll or l[0] > ll[0]:
				le += l[0]
				c += 1
				v = l.popleft()
				if v // 2 >= 1:
					ll.append(v // 2)
			else:
				le += ll[0]
				c += 1
				v = ll.popleft()
				if v // 2 >= 1:
					ll.append(v // 2)
			if not l:
				(l, ll) = (ll, l)
			if le >= z:
				break
		if le >= z:
			print(c)
		else:
			print('RIP')
	t -= 1


import math, heapq
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	c = list(map(int, input().split()))
	C = [-i for i in c]
	heapq.heapify(C)
	ta = z - a
	tb = z - b
	ta = math.ceil(ta / x)
	tb = math.ceil(tb / y)
	ans = 0
	if ta < tb:
		print('0')
	else:
		vala = a + (tb - 1) * x
		valb = b + (tb - 1) * y
		remain = z - vala
		while remain >= 0:
			temp = heapq.heappop(C)
			if temp == 0:
				break
			temp = -temp
			remain -= temp
			heapq.heappush(C, -(temp // 2))
			ans += 1
		if remain >= 0:
			print('RIP')
		else:
			print(ans)


from heapq import heapify, heappop, heappush
from math import ceil, floor
for _ in range(int(input())):
	(n, a, b, x, y, z) = map(int, input().split())
	l = list(map(int, input().split()))
	heap = [-i for i in l]
	days_p = ceil((z - a) / x)
	days_h = ceil((z - b) / y)
	heapify(heap)
	mul = (z - b) // y
	a += x * mul
	b += y * mul
	count = 0
	while a <= z:
		ext = heappop(heap)
		if ext == 0:
			break
		a += -ext
		heappush(heap, int(ext / 2))
		count += 1
	if a <= z:
		print('RIP')
	else:
		print(count)


import math
import heapq as h
t = int(input())
while t:
	t -= 1
	(n, a, b, x, y, z) = map(int, input().strip().split())
	l = list(map(int, input().strip().split()))
	pd = z - a
	hd = math.ceil((z - b) / y)
	l = [-x for x in l]
	h.heapify(l)
	ct = 0
	while math.ceil(pd / x) >= hd and any(l):
		mx = -h.heappop(l)
		pd -= mx
		ct += 1
		h.heappush(l, -(mx // 2))
	if math.ceil(pd / x) >= hd:
		print('RIP')
	else:
		print(ct)


import math
import heapq
t = int(input())
while t > 0:
	t = t - 1
	(n, a, b, x, y, z) = map(int, input().split())
	arr = [-int(n) for n in input().split()]
	dh = math.ceil((z - b) / y)
	m = a + (dh - 1) * x
	need = z - m
	extra = 0
	z = heapq.heapify(arr)
	c = 0
	r = 0
	while extra < need:
		if arr[0] == 0:
			r = 1
			break
		temp = heapq.heappop(arr)
		extra = extra - temp
		heapq.heappush(arr, math.ceil(temp / 2))
		c = c + 1
	if r:
		print('RIP')
	else:
		print(c)