Geek is organising a bike race with N bikers. The initial speed of the ith biker is denoted by H_{i} Km/hr and the acceleration of ith biker as A_{i} Km/Hr2. A biker whose speed is 'L' or more, is considered be a fast biker. The total speed on the track for every hour is calculated by adding the speed of each fast biker in that hour. When the total speed on the track is 'M' kilometers per hour or more, the safety alarm turns on. 
Find the minimum number of hours after which the safety alarm will start.
Example 1:
Input: 
N = 3, M = 400, L = 120
H = {20, 50, 20}
A = {20, 70, 90}
Output: 3
Explaination: 
Speeds of all the Bikers at ith hour
Biker1= [20  40  60  80 100] 
Biker2= [50 120 190 260 330]
Biker3= [20 110 200 290 380] 
Initial Speed on track  = 0 
because none of the biker's speed is fast enough.
Speed on track after 1st Hour= 120
Speed on track after 2nd Hour= 190+200=390
Speed on track after 3rd Hour= 260+290=550
Alarm will start at 3rd Hour.
Example 2:
Input: 
N = 2, M = 60, L = 120
H = {50, 30}
A = {20, 40}
Output: 3
Explaination: 
Speeds of all the Bikers at ith hour
Biker1= [50 70  90 110 130] 
Biker2= [30 70 110 150 190]
Initial Speed on track = 0 because none of the 
biker's speed is fast enough.
Speed on track at 1st Hour= 0
Speed on track at 2nd Hour= 0
Speed on track at 3rd Hour= 150
Alarm will buzz at 3rd Hour.
Your Task:
You do not need to read input or print anything. Your task is to complete the function buzzTime() which takes N, M, L and array H and array A as input parameters and returns the time when alarm buzzes.
Expected Time Complexity: O(N*log(max(L,M)))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ L, M ≤ 10^{10}
1 ≤ H_{i}, A_{i} ≤ 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Sorting

Starter code: #User function template for Python



class Solution:	

	def buzzTime(self, N, M, L, H, A):

		# code here

Solutions:
class Solution:

	def buzzTime(self, N, M, L, H, A):
		(lo, hi) = (0, 10 ** 9)
		potential_alarm_hour = 0
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			speeds = (h + mid * a for (h, a) in zip(H, A))
			fast_speeds = filter(lambda x: x >= L, speeds)
			if sum(fast_speeds) > M:
				potential_alarm_hour = mid
				hi = mid - 1
			else:
				lo = mid + 1
		return potential_alarm_hour


class Solution:

	def buzzTime(self, N, M, L, H, A):

		def speed(H, A, T):
			return H + A * T

		def finalSpeed(T):
			tot = 0
			for i in range(N):
				s = speed(H[i], A[i], T)
				if s >= L:
					tot += s
			return tot >= M
		low = 0
		high = 10 ** 9
		while low < high:
			mid = (low + high) // 2
			if finalSpeed(mid):
				high = mid
			else:
				low = mid + 1
		return high


class Solution:

	def isPossible(self, N, M, L, H, A, mid):
		net_speed = 0
		for i in range(N):
			a = H[i]
			d = A[i]
			speed = a + mid * d
			if speed >= L:
				net_speed += speed
		if net_speed >= M:
			return True
		else:
			return False

	def buzzTime(self, N, M, L, H, A):
		start = 0
		end = M
		ans = -1
		mid = start + (end - start) // 2
		while start <= end:
			if self.isPossible(N, M, L, H, A, mid):
				ans = mid
				end = mid - 1
			else:
				start = mid + 1
			mid = start + (end - start) // 2
		return ans


class Solution:

	def check(self, N, M, L, H, A, mid):
		pass

	def buzzTime(self, N, M, L, H, A):
		s = 0
		e = 10000000000.0
		mid = (s + e) // 2
		ans = -1
		while s <= e:
			speed = 0
			for i in range(N):
				if H[i] + mid * A[i] >= L:
					speed += H[i] + mid * A[i]
			if speed >= M:
				ans = mid
				e = mid - 1
			else:
				s = mid + 1
			mid = (s + e) // 2
		return int(ans)


class Solution:

	def buzzTime(self, N, M, L, H, A):
		low = 0
		high = (max(M, L) - min(H)) // min(A)
		while low < high:
			mid = (low + high) // 2
			summa = 0
			for i in range(N):
				speed = H[i] + mid * A[i]
				if speed > L:
					summa += speed
			if summa == M:
				return mid
			if summa < M:
				low = mid + 1
			else:
				high = mid
		return low


from math import ceil

class Solution:

	def buzzTime(self, N, M, L, H, A):
		j = list()
		for x in range(N):
			(hp, ap) = (H.pop(), A.pop())
			t = ceil((L - hp) / ap)
			j.append([hp, ap, t])
		j.sort(key=lambda ele: ele[2])
		for x in range(1, N):
			j[x][0] += j[x - 1][0]
			j[x][1] += j[x - 1][1]
		for x in range(N - 1):
			(s, a, ct) = j[x]
			t = ceil((M - s) / a)
			if t < j[x + 1][2]:
				if ct > t:
					return ct
				return t
		return ceil((M - j[-1][0]) / j[-1][1])


class Solution:

	def buzzTime(self, N, M, L, H, A):
		(l, r, mid, sum) = (0, 0, 0, 0)
		x = max(M, L)
		for i in range(N):
			if (x - H[i]) % A[i] == 0:
				r = max(r, (x - H[i]) // A[i])
			else:
				r = max(r, (x - H[i]) // A[i] + 1)
		while l <= r:
			mid = (l + r) // 2
			sum = 0
			for i in range(N):
				if H[i] + A[i] * mid >= L:
					sum += H[i] + A[i] * mid
			if sum >= M:
				r = mid - 1
			else:
				l = mid + 1
		return l


class Solution:

	def alarm(self, H, A, M, L, hour):
		tot = 0
		for i in range(len(H)):
			ti = H[i] + A[i] * hour
			if ti > L:
				tot += ti
		return tot >= M

	def binarysearch(self, l, r, H, A, M, L):
		if l <= r:
			mid = (l + r) // 2
			if self.alarm(H, A, M, L, mid):
				return self.binarysearch(l, mid - 1, H, A, M, L)
			else:
				return self.binarysearch(mid + 1, r, H, A, M, L)
		return l

	def buzzTime(self, N, M, L, H, A):
		return self.binarysearch(1, max(M, L), H, A, M, L)


def currScore(N, H, A, L, ind):
	curr = 0
	for i in range(N):
		c = H[i] + A[i] * ind
		if c >= L:
			curr += c
	return curr

class Solution:

	def buzzTime(self, N, M, L, H, A):
		(st, en) = (0, max(M, L) // max(H) + 1)
		while st < en:
			mid = (st + en) // 2
			sc = currScore(N, H, A, L, mid)
			if sc == M:
				return mid
			elif sc > M:
				en = mid
			else:
				st = mid + 1
		return en


class Solution:

	def buzzTime(self, N, M, L, H, A):

		def check(val):
			s = 0
			for i in range(N):
				x = H[i] + val * A[i]
				if x >= L:
					s += x
			return s >= M
		(l, r) = (0, min(L, M))
		ans = 0
		while l <= r:
			mid = (l + r) // 2
			x = check(mid)
			if x:
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return ans


class Solution:

	def buzzTime(self, n, m, l, h, a):
		low = 0
		high = max(m, l)
		ans = 0
		while low <= high:
			mid = (low + high) // 2
			fast = 0
			for i in range(n):
				if h[i] + a[i] * mid >= l:
					fast += h[i] + a[i] * mid
			if fast >= m:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def isvalid(self, N, M, L, H, A, m):
		speedoftrack = 0
		for i in range(N):
			if H[i] + m * A[i] >= L:
				speedoftrack += H[i] + m * A[i]
				if speedoftrack >= M:
					return True
		return False

	def buzzTime(self, N, M, L, H, A):
		s = 0
		e = max(L, M)
		while s <= e:
			m = s + (e - s) // 2
			if self.isvalid(N, M, L, H, A, m):
				ans = m
				e = m - 1
			else:
				s = m + 1
		return ans


class Solution:

	def buzzTime(self, n, M, L, s, a):

		def check(e):
			c = 0
			for i in range(n):
				if s[i] + e * a[i] >= L:
					c += s[i] + e * a[i]
			return c >= M
		i = 0
		j = 10 ** 9
		ans = 0
		while i <= j:
			m = (i + j) // 2
			if check(m):
				ans = m
				j = m - 1
			else:
				i = m + 1
		return ans


def check(A, L, M, H, lo, hi, mid):
	s = 0
	for i in range(len(A)):
		if mid * A[i] + H[i] >= L:
			s += mid * A[i] + H[i]
	return s >= M

class Solution:

	def buzzTime(self, N, M, L, H, A):
		lo = 0
		hi = max(M, L)
		mid = lo + (hi - lo) // 2
		ans = -1
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			if check(A, L, M, H, lo, hi, mid):
				ans = mid
				hi = mid - 1
			else:
				lo = mid + 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M, L) = [int(x) for x in input().split()]
		H = [0 for x in range(N)]
		A = [0 for x in range(N)]
		for i in range(N):
			(H[i], A[i]) = [int(y) for y in input().split()]
		ob = Solution()
		print(ob.buzzTime(N, M, L, H, A))


class Solution:

	def buzzTime(self, N, M, L, H, A):
		(low, high) = (0, max(L, M))

		def isvalid(N, M, L, H, A, time):
			fast_bike_sum = 0
			for i in range(len(H)):
				speed = H[i] + A[i] * time
				if speed >= L:
					fast_bike_sum += speed
			if fast_bike_sum >= M:
				return True
			else:
				return False
		while low < high:
			mid = (low + high) // 2
			if isvalid(N, M, L, H, A, mid):
				high = mid
			else:
				low = mid + 1
		return high


class Solution:

	def buzzTime(self, N, M, L, H, A):
		low = 0
		high = max(L, M)
		while low <= high:
			mid = (low + high) // 2
			fast = 0
			for i in range(N):
				if H[i] + A[i] * mid >= L:
					fast += H[i] + A[i] * mid
			if fast >= M:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def buzzTime(self, N, M, L, H, A):

		def isPossible(m):
			fspeed = 0
			for i in range(N):
				speed = H[i] + m * A[i]
				if speed >= L:
					fspeed += speed
			if fspeed >= M:
				return True
			else:
				return False
		ans = -1
		s = 0
		e = max(L, M)
		while s <= e:
			m = (s + e) // 2
			if isPossible(m):
				e = m - 1
				ans = m
			else:
				s = m + 1
		return ans


class Solution:

	def buzzTime(self, N, M, L, H, A):
		strt = 0
		end = max(M, L)
		while strt <= end:
			mid = strt + (end - strt) // 2
			if self.TS(H, A, N, M, L, mid):
				end = mid - 1
			else:
				strt = mid + 1
		return end

	def TS(self, H, A, N, M, L, T):
		t = 0
		for i in range(0, N):
			x = H[i] + (T - 1) * A[i]
			if x >= L:
				t += x
			if t >= M:
				return True
		return False


import math

class Solution:

	def buzzTime(self, N, M, L, H, A):
		high = -1
		bigger_num = max(L, M)
		for i in range(0, N):
			high = max(bigger_num / A[i], high)
		low = 0
		while low <= high:
			mid = int((low + high) / 2)
			sum = 0
			for i in range(0, N):
				temp = H[i] + A[i] * mid
				if temp >= L:
					sum = sum + temp
			if sum == M:
				return mid
			elif sum < M:
				low = mid + 1
			elif sum > M:
				res = mid
				high = mid - 1
		return int(res)


class Solution:

	def buzzTime(self, N, M, L, H, A):
		l = 0
		r = 10 ** 9
		res = -1
		while l <= r:
			m = l + (r - l) // 2
			sum = 0
			for i in range(N):
				ans = H[i] + A[i] * m
				if ans >= L:
					sum += ans
			if sum >= M:
				res = m
				r = m - 1
			else:
				l = m + 1
		return res


class Solution:

	def buzzTime(self, N, M, L, H, A):
		high = min(L, M)
		low = 0
		while low < high:
			mid = (low + high) // 2
			if bool_(mid, N, M, L, H, A):
				high = mid
			else:
				low = mid + 1
		return high

def bool_(mid, N, M, L, H, A):
	sumCount = 0
	for i in range(N):
		temp = H[i] + A[i] * mid
		if temp > L:
			sumCount += temp
	if sumCount > M:
		return True
	else:
		return False


class Solution:

	def buzzTime(self, N, M, L, H, A):
		ans = 0
		bc = 0
		wc = max(M, N)
		while bc <= wc:
			mid = (bc + wc) // 2
			speed = 0
			for i in range(0, N):
				if H[i] + A[i] * mid >= L:
					speed += H[i] + A[i] * mid
			if speed >= M:
				ans = mid
				wc = mid - 1
			else:
				bc = mid + 1
		return ans


class Solution:

	def check(self, N, total, M, L, H, A):
		count = 0
		for i in range(N):
			temp = A[i] * (total - 1) + H[i]
			if temp >= L:
				count += temp
		if count >= M:
			return True
		return False

	def buzzTime(self, N, M, L, H, A):
		low = 0
		minvalue = min(A)
		high = M + max(H) // minvalue + 1
		ans = 0
		while low <= high:
			mid = low + (high - low) // 2
			if self.check(N, mid, M, L, H, A):
				high = mid - 1
				ans = mid
			else:
				low = mid + 1
		return ans - 1


class Solution:

	def check(self, mid, N, M, L, H, A):
		res = 0
		for i in range(len(H)):
			value = H[i] + mid * A[i]
			if value > L:
				res += value
		if res > M:
			return True
		return False

	def buzzTime(self, N, M, L, H, A):
		low = 0
		high = max(M, L)
		ans = 0
		while low <= high:
			mid = (low + high) // 2
			if self.check(mid, N, M, L, H, A):
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def buzzTime(self, N, M, L, H, A):

		def speed(h, a, t):
			return h + a * t

		def is_final_speed_good(t):
			tot = 0
			for i in range(N):
				s = speed(H[i], A[i], t)
				if s >= L:
					tot += s
			return tot >= M
		low = 0
		high = 10 ** 9
		mid = 0
		while low < high:
			mid = (low + high) // 2
			if is_final_speed_good(mid):
				high = mid
			else:
				low = mid + 1
		return high


class Solution:

	def buzzTime(self, N, M, L, H, A):
		low = 0
		high = M
		res = 0
		while low <= high:
			mid = (low + high) // 2
			Speed = 0
			for i in range(N):
				tmp = A[i] * mid + H[i]
				if tmp >= L:
					Speed += tmp
			if Speed >= M:
				high = mid - 1
				res = mid
			else:
				low = mid + 1
		return res


import sys

class Solution:

	def buzzTime(self, N, M, L, H, A):
		l = 0
		r = 1000000000.0
		res = -1
		while l <= r:
			m = l + int((r - l) / 2)
			sum = 0
			for i in range(N):
				ans = H[i] + A[i] * m
				if ans >= L:
					sum += ans
			if sum >= M:
				res = m
				r = m - 1
			else:
				l = m + 1
		return res


class Bikers:

	def __init__(self, bikers, alarm, fspeed):
		self.bikers = bikers
		self.speed_alarm = alarm
		self.fast_speed = fspeed

	def alarm(self, speed, accel):
		l = 0
		r = 0
		x = max(self.fast_speed, self.speed_alarm)
		for i in range(self.bikers):
			if (x - speed[i]) % accel[i] == 0:
				r = max(r, x - speed[i] // accel[i])
			else:
				r = max(r, x - speed[i] // accel[i] + 1)
		while l <= r:
			mid = (l + r) // 2
			sum = 0
			for i in range(self.bikers):
				if speed[i] + accel[i] * mid >= self.fast_speed:
					sum += speed[i] + accel[i] * mid
			if sum >= self.speed_alarm:
				r = mid - 1
			else:
				l = mid + 1
		return l

class Solution:

	def buzzTime(self, N, M, L, H, A):
		bk = Bikers(N, M, L)
		return bk.alarm(H, A)


import numpy as np

class Solution:

	def f_x(size, H, A, M, L):
		H = np.array(H)
		A = np.array(A)
		H = H + size * A
		max_sum = sum(H[H >= L])
		return max_sum

	def binarySearch(l, r, H, A, M, L):
		if r >= l:
			mid = l + (r - l) // 2
			if Solution.f_x(mid, H, A, M, L) >= M and Solution.f_x(mid - 1, H, A, M, L) < M:
				return mid
			elif Solution.f_x(mid, H, A, M, L) >= M and Solution.f_x(mid - 1, H, A, M, L) >= M:
				return Solution.binarySearch(l, mid - 1, H, A, M, L)
			else:
				return Solution.binarySearch(mid + 1, r, H, A, M, L)
		else:
			return -1

	def buzzTime(self, N, M, L, H, A):
		max_val = max(M, L)
		array_len = min(np.floor((max_val - np.array(H)) / np.array(A))) + 1
		return int(Solution.binarySearch(0, array_len, H, A, M, L))


import math

class Solution:

	def calc(self, H, A, t, L, M):
		curr = 0
		for i in range(len(H)):
			y = H[i] + t * A[i]
			if y >= L:
				curr += y
		return curr

	def buzzTime(self, N, M, L, H, A):
		start = 0
		mini = 2 ** 31
		maxi = -1 * mini
		for i in range(N):
			k = max(0, math.ceil((L - H[i]) / A[i]))
			mini = min(k, mini)
			maxi = max(k, maxi)
		left = mini
		right = maxi
		ans = 0
		while left <= right:
			mid = (left + right) // 2
			k = self.calc(H, A, mid, L, M)
			if k < M:
				left = mid + 1
			else:
				ans = mid
				right = mid - 1
		return ans


class Solution:

	def buzzTime(self, n, m, l, h, a):

		def speed(h, a, t):
			return h + a * t

		def is_final_speed_good(t):
			tot = 0
			for i in range(n):
				s = speed(h[i], a[i], t)
				if s >= l:
					tot += s
			return tot >= m
		low = 0
		high = 10 ** 9
		mid = 0
		while low < high:
			mid = (low + high) // 2
			if is_final_speed_good(mid):
				high = mid
			else:
				low = mid + 1
		return high


class Solution:

	def buzzTime(self, N, M, L, H, A):
		start = 0
		end = M
		while start < end:
			m = (start + end) // 2
			track_speed = 0
			for (h, a) in zip(H, A):
				speed = h + m * a
				if speed >= L:
					track_speed += speed
			if track_speed >= M:
				end = m
			else:
				start = m + 1
		return start


class Solution:

	def buzzTime(self, N, M, L, H, A):
		hour = all = low = 0
		high = 10 ** 10
		while low < high:
			hour = (high + low) // 2
			all = 0
			for i in range(0, N):
				speed = H[i] + hour * A[i]
				if speed >= L:
					all += speed
			if all >= M:
				high = hour
			else:
				low = hour + 1
		return low


class Solution:

	def buzzTime(self, N, M, L, H, A):
		l = 0
		r = 10000000000.0
		while l < r:
			m = int((l + r) / 2)
			total = 0
			for index in range(N):
				num = H[index] + m * A[index]
				if num >= L:
					total += num
			if total >= M:
				r = m
			else:
				l = m + 1
		return l


class Solution:

	def check(h, N, M, L, H, A):
		track_speed = 0
		for i in range(N):
			Biker_speed = H[i] + h * A[i]
			if Biker_speed >= L:
				track_speed += Biker_speed
		if track_speed >= M:
			return True
		return False

	def buzzTime(self, N, M, L, H, A):
		low = 0
		high = 10 ** 9
		ans = 0
		while low <= high:
			mid = (low + high) // 2
			if Solution.check(mid, N, M, L, H, A):
				high = mid - 1
				ans = mid
			else:
				low = mid + 1
		return int(ans)


class Solution:

	def buzzTime(self, N, M, L, H, A):
		min_acc = min(A)
		high = L // min_acc + 1
		low = 0
		flag = 0
		ans = -1
		while low <= high:
			mid = (low + high) // 2
			total_speed = 0
			for i in range(N):
				temp = H[i] + A[i] * mid
				if temp >= L:
					total_speed += temp
			if total_speed >= M:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


def ceil(b):
	if b > int(b):
		return int(b) + 1
	return int(b)

class Solution:

	def buzzTime(self, N, M, L, H, A):
		first_l = min([ceil((L - h) / a) for (h, a) in zip(H, A)])
		if M <= L or sum([a * first_l + h for (a, h) in zip(A, H) if a * first_l + h >= L]) >= M:
			return first_l
		first_m = min([ceil((M - h) / a) for (h, a) in zip(H, A)])
		while first_l < first_m - 1:
			mid = int((first_l + first_m) / 2)
			total_speed = sum([a * mid + h for (a, h) in zip(A, H) if a * mid + h >= L])
			if total_speed >= M:
				first_m = mid
			else:
				first_l = mid
		return first_m


class Solution:

	def bin_search(self, start, end, N, H, A, M, L):
		if start < end:
			mid = (end + start) // 2
			sm = 0
			for i in range(N):
				if H[i] + A[i] * mid > L:
					sm += H[i] + A[i] * mid
			if sm == M:
				return mid
			if sm < M:
				return self.bin_search(mid + 1, end, N, H, A, M, L)
			else:
				return self.bin_search(start, mid, N, H, A, M, L)
		return start

	def buzzTime(self, N, M, L, H, A):
		m = max(L, M)
		end = m // min(H)
		return self.bin_search(0, end, N, H, A, M, L)


import math

class Solution:

	def buzzTime(self, N, M, L, H, A):
		start = 0
		end = max(L, M)
		while start < end:
			mid = math.floor((start + end) / 2)
			total_speed = 0
			i = 0
			for i in range(N):
				speed = H[i] + mid * A[i]
				if speed >= L:
					total_speed = total_speed + speed
			if total_speed >= M:
				end = mid
			else:
				start = mid + 1
		return start


class Solution:

	def buzzTime(self, N, M, L, H, A):
		import math

		def is_possible(t):
			s = 0
			for (u, a) in zip(H, A):
				if u + a * t >= L:
					s += u + a * t
			return s >= M

		def get_max_time():
			ar = [(u, a) for (u, a) in zip(H, A)]
			ar.sort()
			return math.ceil((max(M, L) - ar[0][0]) / ar[0][1])
		r = get_max_time()
		l = 0
		ans = r
		while l <= r:
			m = (l + r) // 2
			if is_possible(m):
				ans = m
				r = m - 1
			else:
				l = m + 1
		return ans


class Solution:

	def buzzTime(self, N, M, L, H, A):
		r = 0
		l = max(L, M)

		def check(mid):
			speed = 0
			for i in range(N):
				s = H[i] + A[i] * mid
				if s >= L:
					speed += s
			return speed >= M
		ans = 0
		while r <= l:
			mid = (l + r) // 2
			if check(mid):
				ans = mid
				l = mid - 1
			else:
				r = mid + 1
		return ans


class Solution:

	def buzzTime(self, N, M, L, H, A):
		totalTrackSpeed = 0
		hr = -1
		firstMin = False
		for i in range(N):
			val = (L - H[i]) // A[i]
			if not firstMin:
				hr = val
				firstMin = True
			if hr > val:
				hr = val
		while totalTrackSpeed < M:
			totalTrackSpeed = 0
			bikerSpeed = 0
			for i in range(N):
				bikerSpeed = H[i] + A[i] * hr
				if bikerSpeed >= L:
					totalTrackSpeed += bikerSpeed
			if totalTrackSpeed < M:
				hr += 1
		return hr


class Solution:

	def buzzTime(self, N, M, L, H, A):
		l = 0
		r = 1 * pow(10, 10)
		while l <= r:
			mid = l + (r - l) // 2
			fsum = 0
			for i in range(N):
				if H[i] + A[i] * mid >= L:
					fsum += H[i] + A[i] * mid
			if fsum >= M:
				r = mid - 1
			else:
				l = mid + 1
		return l


import math

class Solution:

	def buzzTime(self, N, M, L, H, A):
		low = 0
		k = H.index(max(H))
		if M > L:
			high = math.ceil((M - H[k]) / A[k])
		else:
			high = math.ceil((L - H[k]) / A[k])
		while low <= high:
			mid = low + (high - low) // 2
			su = 0
			for i in range(N):
				if L <= H[i] + A[i] * mid:
					su = su + (H[i] + A[i] * mid)
			if su >= M:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def buzzTime(self, N, M, L, H, A):
		low = 0
		high = max(L, M)
		mid = 0
		ret = 0
		while low <= high:
			mid = int((low + high) / 2)
			t_speed = 0
			for i in range(N):
				h_speed = H[i] + A[i] * mid
				if h_speed >= L:
					t_speed += h_speed
			if t_speed >= M:
				ret = mid
				high = mid - 1
			else:
				low = mid + 1
		return ret


class Solution:

	def buzzTime(self, N, M, L, H, A):
		l = 0
		h = 100000000.0
		ans = 0
		while l <= h:
			mid = l + (h - l) // 2
			speed = 0
			for i in range(N):
				sp = H[i] + mid * A[i]
				if sp >= L:
					speed += sp
			if speed >= M:
				ans = mid
				h = mid - 1
			else:
				l = mid + 1
		return int(ans)


import math

class Solution:

	def buzzTime(self, N, M, L, H, A):

		def ok(h):
			s = 0
			for (a0, acc) in zip(H, A):
				speed = a0 + acc * h
				if speed > L:
					s += speed
			return s >= M
		(lo, hi) = (0, math.ceil(M // max(A)) + math.ceil(L / max(A)))
		while lo < hi:
			mi = lo + (hi - lo) // 2
			if ok(mi):
				hi = mi
			else:
				lo = mi + 1
		return lo


class Solution:

	def buzzTime(self, N, M, L, H, A):
		import math
		h = max(L, M)
		l = 1
		while l < h:
			mid = int((l + h) / 2)
			cur = 0
			for (u, a) in zip(H, A):
				if u + a * mid >= L:
					cur += u + a * mid
			if cur >= M:
				h = mid
			else:
				l = mid + 1
		return l


class Solution:

	def buzzTime(self, num_bikers, top_total_safe_speed, fast_total_speed, speeds, accels):
		self.top_safe = top_total_safe_speed
		self.top_fast = fast_total_speed
		self.initial_speeds = speeds
		self.accels = accels
		return self.binarySearch(0, max(top_total_safe_speed, fast_total_speed))

	def binarySearch(self, head, tail):
		mid = int((head + tail) / 2)
		speed = self.speedAtHour(mid)
		safe = speed < self.top_safe
		if not safe and mid == 0:
			return 0
		elif not safe and self.speedAtHour(mid - 1) < self.top_safe:
			return mid
		elif safe:
			return self.binarySearch(mid + 1, tail)
		else:
			return self.binarySearch(head, mid)

	def speedAtHour(self, hour):
		return sum([s + hour * a for (s, a) in zip(self.initial_speeds, self.accels) if s + hour * a > self.top_fast])


import numpy as np
import math

class Solution:

	def buzzTime(self, N, M, L, H, A):
		H = np.array(H)
		A = np.array(A)
		n = math.ceil(min((L - H) / A))
		H = H + n * A
		while True:
			sum_res = np.sum(H[H > L])
			if sum_res >= M:
				return n
			H = H + A
			n += 1


class Solution:

	def buzzTime(self, N, M, L, H, A):
		lTime = 0
		rTime = 9223372036854775807
		speed = 0
		for i in range(N):
			if H[i] >= L:
				speed = speed + H[i]
		if speed >= M:
			return 0
		while lTime <= rTime:
			mTime = int((lTime + rTime) / 2)
			mSpeed = 0
			prevSpeed = 0
			for i in range(N):
				if H[i] + mTime * A[i] >= L:
					mSpeed = mSpeed + (H[i] + mTime * A[i])
				if H[i] + (mTime - 1) * A[i] >= L:
					prevSpeed = prevSpeed + (H[i] + (mTime - 1) * A[i])
			if mSpeed >= M and prevSpeed < M:
				return mTime
			if mSpeed >= M:
				rTime = mTime
			else:
				lTime = mTime
		return lTime