Geek went to buy some chocolates from a nearby shop with k coins in his pocket. He found that the shop contains n chocolates which are arranged in sorted order (increasing) of their prices.
Now geek wants to taste costlier chocolates so he decided that he will buy the costliest chocolate (of course among the ones that he can afford) till there exists at least one type of chocolate he can afford. You may assume that there is an infinite supply of chocolates in the shop Geek visited.
As you know, Geek is a shy person and hence he will enquire about the prices of the chocolates at most 50 times from the shopkeeper. Now, your task is to find the number of chocolates he had enjoyed. 
Note: If you call the Shop.get function more than 50 times it will return -1. Price of chocolates are pairwise distinct.
Example 1: 
Input:
3 5 
2 4 6
Output:
1
Explanation: The prices of chocolates are [2, 4, 6] and Geek had 5 coins with him. So he can only buy chocolate that costs 4 coins (since he always picks the costliest one).
Example 2: 
Input:
4 9 
1 2 3 4
Output:
3
Explanation: The prices of chocolates are [1, 2, 3, 4] and Geek had 9 coins with him. So he can buy two chocolates that cost 4 coins. Thereafter, he had only 1 coin with him, hence he will have 1 more chocolate (that costs 1 coin).
Your Task:
Return the number of chocolates geeks had eaten. Use the get(int i) function to inquire about the price of the i'th chocolate. 
Note that, you can only call that function 50 times after which it will return -1. Test cases are generated such that the answer can always be found.
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(logN)
Constraints:
0 < n < 10^{5}
0 < priceOfChocolate < = 10^{7 }
0 < k <= 10^{12 }

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: #User function Template for python3



"""

Instructions - 



    1. 'shop' is object of class Shop.

    2. User 'shop.get(int i)' to enquire about the price

            of the i^th chocolate.

    3. Every chocolate in shop is arranged in increasing order

            i.e. shop.get(i) <= shop.get(i + 1) for all 0 <= i < n - 1

"""



class Solution:

    shop=Shop()

    def __init__(self,shop):

        self.shop=shop

    

    def find(self,n,k):

        #code here

Solutions:
class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		e = n - 1
		ch = 0
		while e >= 0:
			s = 0
			idx = 0
			ans = int(1000000000.0)
			while s <= e:
				m = (s + e) // 2
				p = shop.get(m)
				if k >= p:
					ans = p
					idx = m
					s = m + 1
				else:
					e = m - 1
			ch += k // ans
			k = k % ans
			e = idx - 1
		return ch


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		low = 0
		high = n - 1
		count = 0
		hm = dict()
		while k > 0:
			low = 0
			while low <= high:
				mid = (low + high) // 2
				temp = 0
				if mid not in hm:
					temp = self.shop.get(mid)
				else:
					temp = hm[mid]
				hm[mid] = temp
				if temp <= k:
					low = mid + 1
				else:
					high = mid - 1
			if high == -1:
				break
			count += k // hm[high]
			k -= k // hm[high] * hm[high]
		return count


class Solution:
	shop = Shop()
	mp = {}

	def __init__(self, shop):
		self.shop = shop
		self.mp = {}

	def mgc(self, x, n):
		(st, en) = (0, n)
		just_max = -1
		while st <= en:
			mid = (st + en) // 2
			if mid in self.mp:
				temp = self.mp[mid]
			else:
				temp = self.shop.get(mid)
				self.mp[mid] = temp
			if temp > x:
				en = mid - 1
			else:
				just_max = temp
				st = mid + 1
		return just_max

	def find(self, n, k):
		ans = 0
		exc = 0
		while k > 0:
			exc += 1
			ind = self.mgc(k, n - exc)
			if ind == -1:
				return ans
			ans += k // ind
			k %= ind
		return ans


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def search(self, n, k):
		start = 0
		end = n
		cost = shop.get(end)
		if cost < k:
			return [cost, end]
		while True:
			mid = (start + end) // 2
			cost = shop.get(mid)
			if cost == -1:
				return False
			if cost < k:
				start = mid
				if end - start == 1:
					return [cost, start]
			elif cost > k:
				end = mid
				if end - start == 1:
					return [shop.get(start), start]
			else:
				return [cost, mid]

	def find(self, n, k):
		tasted = 0
		n -= 1
		while k:
			Search = self.search(n, k)
			if Search:
				costliest = Search[0]
				n = Search[1]
				buy = k // costliest
				tasted += buy
				k -= buy * costliest
			else:
				return tasted
		return tasted


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		low = 0
		high = n - 1
		dict1 = {0: shop.get(0)}
		count = 0
		while k - dict1[0] >= 0:
			low = 0
			high = n - 1
			while low <= high:
				mid = (low + high) // 2
				if mid in dict1:
					pass
				else:
					dict1[mid] = shop.get(mid)
				if dict1[mid] < k:
					low = mid + 1
				elif dict1[mid] == k:
					return count + 1
				else:
					high = mid - 1
			if high in dict1:
				pass
			else:
				dict1[high] = shop.get(high)
			count += k // dict1[high]
			k = k % dict1[high]
		return count


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop
	from functools import lru_cache

	@lru_cache(None)
	def getprice(self, a):
		return shop.get(a)

	def find(self, n, k):
		ret = 0
		while k > 0:
			l = 0


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop
	from functools import lru_cache

	@lru_cache(None)
	def getprice(self, a):
		return shop.get(a)

	def find(self, n, k):
		ret = 0
		while k > 0:
			l = 0
			r = n - 1
			while l < r:
				m = l + (r - l) // 2
				if self.getprice(m) < k:
					l = m + 1
				else:
					r = m
			if l == 0 and self.getprice(l) > k:
				break
			if self.getprice(l) > k:
				l -= 1
			ret += k // self.getprice(l)
			k %= self.getprice(l)
		return ret


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		affords = 0
		low = 0
		high = n - 1
		while k > 0:
			max_price = 0
			while high >= low:
				mid = (low + high) // 2
				price = self.shop.get(mid)
				if price > k:
					high = mid - 1
				else:
					max_price = price
					low = mid + 1
			if max_price == 0:
				break
			numChocs = k // max_price
			affords += numChocs
			k -= numChocs * max_price
			low = 0
		return affords


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		ans = 0
		h = n - 1
		while k > 0:
			l = 0
			d = {}
			flag = False
			while l < h:
				m = (l + h) // 2
				if m in d:
					x = d[m]
				else:
					x = shop.get(m)
					d[m] = x
				if x < k:
					l = m + 1
				elif x == k:
					flag = True
					break
				else:
					h = m
			if flag:
				h = m
			else:
				if h in d:
					value = d[h]
				else:
					value = shop.get(h)
				if value > k:
					h -= 1
			if h == -1:
				return ans
			if h in d:
				value = d[h]
			else:
				value = shop.get(h)
			ans += k // value
			k %= value
		return ans


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		ans = 0
		l = 0
		r = n - 1
		while k > 0 and r >= 0:
			l = 0
			index = -1
			index_val = 0
			while l <= r:
				mid = (l + r) // 2
				mid_price = self.shop.get(mid)
				if mid_price <= k:
					index = mid
					index_val = mid_price
					l = mid + 1
				else:
					r = mid - 1
			if index_val == 0:
				break
			ans += k // index_val
			k %= index_val
			r = index - 1
		return ans


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def solve(self, n, k):
		low = 0
		high = n
		cost = shop.get(high)
		if cost < k:
			return [cost, high]
		while True:
			mid = (low + high) // 2
			cost = shop.get(mid)
			if cost == -1:
				return 0
			if cost < k:
				low = mid
				if high - low == 1:
					return [cost, low]
			elif cost > k:
				high = mid
				if high - low == 1:
					return [shop.get(low), low]
			else:
				return [cost, mid]

	def find(self, n, k):
		count = 0
		n -= 1
		while k > 0:
			a = self.solve(n, k)
			if a:
				costliest = a[0]
				n = a[1]
				buy = k // costliest
				count += buy
				k = k - buy * costliest
			else:
				return count
		return count
		return count


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		l = 0
		r = n - 1
		res = 0
		while r >= 0 and k > 0:
			l = 0
			idx = -1
			val = 0
			while l <= r:
				mid = (l + r) // 2
				pricem = self.shop.get(mid)
				if pricem <= k:
					l = mid + 1
					idx = mid
					val = pricem
				else:
					r = mid - 1
			if val:
				res += k // val
				k %= val
				r = idx - 1
		return res


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		zeroCost = self.shop.get(0)
		endIndex = n - 1
		self.count = 0
		while k > 0:
			if zeroCost > k:
				break
			endCost = self.shop.get(endIndex)
			if endCost == -1:
				break
			if endCost <= k:
				(count, k) = divmod(k, endCost)
				self.count += count
				endIndex -= 1
			else:
				(k, endIndex) = self.maxCount(k, endIndex, 0, zeroCost)
		return self.count

	def maxCount(self, k, ed, st, icost):
		if ed - st in [0, 1]:
			if icost == -1:
				return (0, st - 1)
			(count, k) = divmod(k, icost)
			self.count += count
			return (k, st - 1)
		else:
			md = (st + ed) // 2
			cost = self.shop.get(md)
			if cost == -1:
				return (0, md - 1)
			if cost == k:
				self.count += 1
				k = 0
				return (k, md - 1)
			elif cost > k:
				return self.maxCount(k, md, st, icost)
			else:
				return self.maxCount(k, ed, md, cost)


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		end = n - 1
		choc = 0
		while end >= 0:
			ans_val = k + 1
			ans_ind = 0
			start = 0
			while start <= end:
				mid = (start + end) // 2
				val = self.shop.get(mid)
				if val <= k:
					ans_val = val
					ans_ind = mid
					start = mid + 1
				else:
					end = mid - 1
			choc += k // ans_val
			k = k % ans_val
			end = ans_ind - 1
		return choc


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		if k == 0:
			return 0
		ans = 0
		(low, high) = (0, n - 1)
		mid_val = -1
		while low <= high:
			mid = (low + high) // 2
			mid_val = self.shop.get(mid)
			if mid_val == k:
				k = 0
				ans += 1
				return ans
			elif mid_val < k:
				low = mid + 1
			else:
				high = mid - 1
		if mid_val == -1:
			return 0
		if mid_val > k and mid > 0:
			cur = self.shop.get(mid - 1)
			ans += k // cur
			k -= k // cur * cur
		elif mid_val > k and mid == 0:
			return 0
		elif mid_val < k:
			ans += k // mid_val
			k -= k // mid_val * mid_val
		return ans + self.find(mid, k)


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def helper(self, n, k):
		l = 0
		r = n
		last = 0
		ans = -1
		while l <= r:
			mid = (l + r) // 2
			price = self.shop.get(mid)
			if price <= k:
				l = mid + 1
				ans = mid
				last = price
			else:
				r = mid - 1
		if last > k and r == 0:
			return (-1, -1)
		return (ans, last)

	def find(self, n, k):
		ans = 0
		ind = n
		while ind != -1:
			(ind, price) = self.helper(ind - 1, k)
			if ind == -1:
				break
			num = k // price
			k -= price * num
			ans += num
		return ans


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		i = 0
		j = n - 1
		ans = 0
		while k >= arr[0]:
			while i < j:
				mid = i + (j - i) // 2
				if k > arr[mid]:
					i = mid + 1
				else:
					j = mid
			if arr[j] <= k:
				mid = j
			else:
				mid = i
			ans += k // arr[mid]
			k = k % arr[mid]
			i = 0
			j = mid - 1
		return ans


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		i = 0
		j = n - 1
		mid = 0
		max_count = 0
		temp = n
		while k > 0:
			i = 0
			j = temp - 1
			val = 0
			while i <= j:
				mid = (i + j) // 2
				mid_val = shop.get(mid)
				if mid_val == -1:
					break
				if k >= mid_val:
					val = mid_val
					temp = mid
					i = mid + 1
				else:
					j = mid - 1
			if val == 0:
				break
			max_count += k // val
			k = k % val
		return max_count


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):

		def search(maxi, coins):
			(low, high) = (0, maxi)
			while low < high:
				mi = low + (high - low) // 2
				if self.shop.get(mi) > coins:
					high = mi
				else:
					low = mi + 1
			return low - 1
		ans = 0
		while True:
			n = search(n, k)
			if n == -1:
				return ans
			maxval = self.shop.get(n)
			ans += k // maxval
			k %= maxval
		return ans


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		maxC = 0
		l = 0
		h = n - 1
		while k > 0:
			maxP = 0
			while l <= h:
				midd = (l + h) // 2
				price = shop.get(midd)
				if price > k:
					h = midd - 1
				else:
					maxP = price
					l = midd + 1
			if maxP == 0:
				break
			chocol = k // maxP
			maxC = maxC + chocol
			k = k % maxP
			l = 0
		return maxC


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		cost = [-1] * n
		if n < 50:
			for i in range(n):
				cost[i] = self.shop.get(i)
		else:
			cost[0] = self.shop.get(0)
		ans = 0
		l = 0
		r = n - 1
		while r >= 0 and k > 0:
			l = 0
			idx = -1
			idx_val = 0
			while l <= r:
				mid = (l + r) // 2
				if cost[mid] == -1:
					cost[mid] = shop.get(mid)
				mprice = cost[mid]
				if mprice <= k:
					idx = mid
					idx_val = mprice
					l = mid + 1
				else:
					r = mid - 1
			if idx_val == 0:
				break
			ans += k // idx_val
			k = k % idx_val
			r = idx - 1
		return ans

	def find_v2(self, n, k):
		cost = [-1] * n
		if n < 50:
			for i in range(n):
				cost[i] = self.shop.get(i)
		else:
			cost[0] = self.shop.get(0)
		chocolates = 0
		mid = n // 2
		end = n - 1
		while mid <= end and k >= cost[0]:
			if cost[mid] == -1:
				cost[mid] = self.shop.get(mid)
			if cost[end] == -1:
				cost[end] = self.shop.get(end)
			if cost[end] <= k:
				tchoc = k // cost[end]
				k -= tchoc * cost[end]
				chocolates += tchoc
				end -= 1
				mid -= 1
				continue
			if cost[mid] < k and end - mid == 1:
				tchoc = k // cost[mid]
				k -= tchoc * cost[mid]
				chocolates += tchoc
				end = mid - 1
				continue
			end -= 1
			mid = (end + mid) // 2
		return chocolates

	def find_v1(self, n, k):
		cost = [-1] * n
		if n < 50:
			for i in range(N):
				cost[i] = shop.get(i)
		l = 0
		r = n - 1
		chocolates = 0
		last = [-1, -1]
		while l < r and k:
			mid = (l + r) // 2
			if cost[mid] == -1:
				cost[mid] = shop.get(mid)
			if cost[mid] == k:
				k = 0
				chocolates += 1
			elif cost[mid] < k:
				if last[1] > cost[mid]:
					if last[0] - mid <= 2:
						c = cost[mid]
						for i in range(2):
							if cost[mid + i + 1] == -1:
								cost[mid + i + 1] = shop.get(mid + i + 1)
							if cost[mid + i + 1] > c and cost[mid + i + 1] <= k:
								c = cost[mid + i + 1]
						k -= c
						r = mid
						l = 0
					else:
						r = last[1]
						l = mid
				else:
					r = mid
					last = [mid, cost[mid]]
			else:
				l = mid
				last = [mid, cost[mid]]


def hasher(num):
	hasher1 = []
	for i in range(num):
		hasher1.append(0)
	return hasher1

class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		coins = k
		low = 0
		high = n - 1
		ans = 0
		breaker = shop.get(0)
		hasher1 = hasher(n + 1)
		while coins >= breaker:
			low = 0
			while low <= high:
				mid = (low + high) // 2
				if hasher1[mid] == 0:
					item1 = shop.get(mid)
					hasher1[mid] = item1
				else:
					item1 = hasher1[mid]
				if low == mid and low == high and (item1 < coins):
					break
				if item1 < coins:
					low = mid + 1
				elif item1 > coins:
					high = mid - 1
				else:
					high = mid
					break
			if hasher1[high] == 0:
				item1 = shop.get(high)
				hasher1[mid] = item1
			else:
				item2 = hasher1[high]
			ans += coins // item2
			coins %= item2
		return ans


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		(l, mid, ans, calls) = (0, n, 0, 0)
		while k > 0:
			val = -1
			(l, r, possval) = (0, mid - 1, -1)
			while l <= r:
				mid = l + (r - l) // 2
				val = shop.get(mid)
				if val == k:
					possval = val
					break
				if val > k:
					r = mid - 1
				else:
					possval = val
					l = mid + 1
			if possval > 0:
				ans += k // possval
				k = k % possval
			if possval == -1:
				break
		return ans


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		res = 0
		i = 0
		pos = -1
		j = n - 1
		m = self.shop.get(0)
		while k >= m:
			i = 0
			while i <= j:
				mid = (i + j) // 2
				mid_val = self.shop.get(mid)
				if mid_val <= k:
					pos = mid
					pos_val = mid_val
					i = mid + 1
				else:
					j = mid - 1
			res += k // pos_val
			k = k % pos_val
			j = pos - 1
		return res


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		count = 0
		l = 0
		r = n - 1
		while k > 0:
			index = (-1, -1)
			while l <= r:
				mid = (l + r) // 2
				price = shop.get(mid)
				if price == -1:
					return count
				if price <= k:
					index = (mid, price)
					l = mid + 1
				elif price > k:
					r = mid - 1
			if index[0] == -1:
				return count
			count += k // index[1]
			k -= index[1] * (k // index[1])
			l = 0
			r = index[0] - 1
		return count


MAX_QURIES = 50

class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		max_chocolates = 0
		left = 0
		right = n - 1
		cnt = 0
		while k > 0 and cnt <= MAX_QURIES:
			max_price = 0
			while left <= right and cnt <= MAX_QURIES:
				cnt += 1
				mid = (left + right) // 2
				mid_val = self.shop.get(mid)
				if mid_val > k:
					right = mid - 1
				else:
					max_price = max(max_price, mid_val)
					left = mid + 1
			if max_price == 0:
				break
			div = k // max_price
			max_chocolates += div
			k %= max_price
			left = 0
		return max_chocolates


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		count = 0
		h = n - 1
		dict = {}
		while k > 0:
			l = 0
			while l <= h:
				mid = (h + l) // 2
				if mid in dict.keys():
					val = dict[mid]
				else:
					val = self.shop.get(mid)
					dict[mid] = val
				if val <= k:
					l = mid + 1
				else:
					h = mid - 1
			if h == -1:
				break
			count += k // dict[h]
			k = k % dict[h]
		return count


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def search(self, n, k, dict, h):
		l = 0
		a = -1
		while l <= h:
			mid = l + (h - l) // 2
			if mid in dict:
				m = dict[mid]
			else:
				dict[mid] = shop.get(mid)
				m = dict[mid]
			if m <= k:
				a = m
				l = mid + 1
			elif m > k:
				h = mid - 1
		m = a
		if m == -1:
			return (0, 0, h)
		rem = k % m
		return (rem, k // m, h)

	def find(self, n, k):
		h = n - 1
		count = 0
		dict = {}
		while k > 0:
			(k, a, h) = self.search(n, k, dict, h)
			count += a
		return count


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		ans = 0
		r = n - 1
		while k > 0:
			l = 0
			idx = -1
			val = -1
			while l <= r:
				mid = (l + r) // 2
				currval = shop.get(mid)
				if currval <= k:
					idx = mid
					val = currval
					l = mid + 1
				else:
					r = mid - 1
			if val != -1:
				ans += k // val
				k = k % val
			else:
				k = 0
			r = idx - 1
		return ans


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		i = n - 1
		currChocPrice = self.shop.get(i)
		coinsLeft = k
		tot = 0
		while i >= 0 and coinsLeft > 0:
			if coinsLeft >= currChocPrice:
				coinsLeft -= currChocPrice
				tot += 1
			else:
				lo = 0
				hi = i
				condition = True
				while condition:
					mid = (hi + lo) // 2
					midPrice = self.shop.get(mid)
					if midPrice == coinsLeft:
						i = mid
						currChocPrice = midPrice
						condition = False
					elif hi - lo <= 1:
						hiPrice = self.shop.get(hi)
						loPrice = self.shop.get(lo)
						if hiPrice <= coinsLeft:
							currChocPrice = hiPrice
							i = hi
						elif loPrice <= coinsLeft:
							currChocPrice = loPrice
							i = lo
						else:
							coinsLeft = 0
						condition = False
					elif midPrice > coinsLeft:
						hi = mid - 1
					else:
						lo = mid
		return tot


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):

		def get_price(idx, shop, price_by_idx):
			price = price_by_idx.get(idx)
			if not price:
				price = shop.get(idx)
				price_by_idx[idx] = price
			return price
		chocolates = 0
		start = 0
		end = n - 1
		price_by_idx = {}
		cheapest = get_price(0, shop, price_by_idx)
		while k >= cheapest:
			while start <= end:
				mid = (start + end) // 2
				price = get_price(mid, shop, price_by_idx)
				if k < price:
					end = mid - 1
				else:
					start = mid + 1
			price = get_price(end, shop, price_by_idx)
			chocolates += k // price
			k %= price
			start = 0
		return chocolates


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		en = n - 1
		choc = 0
		while en >= 0:
			val = k + 1
			ind = 0
			st = 0
			while st <= en:
				mid = (st + en) // 2
				v = shop.get(mid)
				if v <= k:
					val = v
					ind = mid
					st = mid + 1
				else:
					en = mid - 1
			choc += k // val
			k = k % val
			en = ind - 1
		return choc


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		mem = {}

		def get_max(val, st=None):
			res = -1
			l = 0
			h = n - 1
			while l <= h:
				if st and l == 0 and (h == n - 1):
					mid = st
				else:
					mid = (h + l) // 2
				if mid in mem:
					cur = mem[mid]
				else:
					cur = shop.get(mid)
					mem[mid] = cur
				if cur <= val:
					res = cur
					l = mid + 1
				else:
					h = mid - 1
			return (res, mid)
		count = 0
		st = None
		while k >= 0:
			(cur, st) = get_max(k, st)
			if cur == -1:
				break
			k -= cur
			count += 1
		return count


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		(low, high) = (0, n - 1)
		ans = 0
		while k > 0:
			low = 0
			flag = False
			freq = {}
			while low < high:
				mid = (low + high) // 2
				x = -1
				if mid in freq:
					x = freq[mid]
				else:
					x = shop.get(mid)
					freq[mid] = x
				if x < k:
					low = mid + 1
				elif x == k:
					flag = True
					break
				else:
					high = mid
			if flag:
				high = mid
			else:
				if high in freq:
					temp = freq[high]
				else:
					temp = shop.get(high)
				if temp > k:
					high -= 1
			if high == -1:
				break
			if high in freq:
				temp = freq[high]
			else:
				temp = shop.get(high)
			ans += k // temp
			k = k % temp
		return ans


class Shop:
	chocolates = []
	countOfCalls = 0

	def __init__(self):
		self.chocolates = []
		self.countOfCalls = 0

	def addChocolate(self, price):
		self.chocolates.append(price)

	def get(self, i):
		self.countOfCalls += 1
		if self.countOfCalls > 50 or i >= len(self.chocolates) or i < 0:
			return -1
		return self.chocolates[i]

class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		ans = 0
		h = n - 1
		while k > 0:
			l = 0
			d = {}
			flag = False
			while l < h:
				m = (l + h) // 2
				if m in d:
					x = d[m]
				else:
					x = shop.get(m)
					d[m] = x
				if x < k:
					l = m + 1
				elif x == k:
					flag = True
					break
				else:
					h = m
			if flag:
				h = m
			else:
				if h in d:
					value = d[h]
				else:
					value = shop.get(h)
				if value > k:
					h -= 1
			if h == -1:
				return ans
			if h in d:
				value = d[h]
			else:
				value = shop.get(h)
			ans += k // value
			k %= value
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		shop = Shop()
		(n, k) = list(map(int, input().strip().split()))
		arr = list(map(int, input().strip().split()))
		for choco in arr:
			shop.addChocolate(choco)
		ob = Solution(shop)
		ans = ob.find(n, k)
		print(ans)
		tc -= 1


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):

		def search(maxi, coins):
			(yy, p) = (0, maxi)
			while yy < p:
				mi = yy + (p - yy) // 2
				if self.shop.get(mi) > coins:
					p = mi
				else:
					yy = mi + 1
			return yy - 1
		ans = 0
		while True:
			n = search(n, k)
			if n == -1:
				return ans
			maxv = self.shop.get(n)
			ans += k // maxv
			k %= maxv
		return ans


import math

class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		count = 0
		l = 0
		r = n - 1

		def returnIndex(price, l, r):
			(index, lastprice, bprice) = (float('inf'), float('inf'), float('inf'))
			while l <= r:
				mid = (l + r) // 2
				lastprice = self.shop.get(mid)
				if lastprice <= price:
					bprice = lastprice
					index = mid
					l = mid + 1
				else:
					r = mid - 1
			return (index, bprice)
		while k > 0:
			(ind, price) = returnIndex(k, l, r)
			if not math.isinf(ind):
				count += k // price
				k %= price
				(l, r) = (0, ind - 1)
			else:
				k = 0
		return count


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		chococount = 0
		seen = [-1 for i in range(n)]
		seen[-1] = shop.get(n - 1)
		if seen[-1] <= k:
			chococount += k // seen[-1]
			k = k % seen[-1]
		(L, H, M) = (0, n - 1, (n - 1) // 2)
		while k > 0 and H > 0:
			if seen[M] == -1:
				seen[M] = shop.get(M)
			local = seen[M]
			if local == k:
				return chococount + 1
			elif L == M:
				if k >= local:
					chococount += k // local
					k = k % local
					H = M
				elif seen[M - 1] != -1:
					chococount += k // seen[M - 1]
					k = k % seen[M - 1]
					H = M - 1
				if k == 0:
					return chococount
				L = 0
				M = L + (H - L) // 2
			elif k > local:
				L = M + 1
				M = L + (H - L) // 2
			else:
				H = M
				M = L + (H - L) // 2
		return chococount


class Shop:
	chocolates = []
	countOfCalls = 0

	def __init__(self):
		self.chocolates = []
		self.countOfCalls = 0

	def addChocolate(self, price):
		self.chocolates.append(price)

	def get(self, i):
		self.countOfCalls += 1
		if self.countOfCalls > 50 or i >= len(self.chocolates) or i < 0:
			return -1
		return self.chocolates[i]

class Solution:

	def __init__(self, s):
		self.shop = s

	def find(self, n, k):
		ans = 0
		l = 0
		r = n - 1
		while r >= 0 and k > 0:
			l = 0
			index = -1
			index_val = 0
			while l <= r:
				mid = (l + r) // 2
				mid_price = self.shop.get(mid)
				if mid_price <= k:
					index = mid
					index_val = mid_price
					l = mid + 1
				else:
					r = mid - 1
			if index_val == 0:
				break
			ans += k // index_val
			k = k % index_val
			r = index - 1
		return ans


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		cnt = 0
		s = 0
		e = n
		while k:
			ans = -1
			s = 0
			while s < e:
				mid = (s + e) // 2
				choc = shop.get(mid)
				if choc == -1:
					ans = -1
				if choc > k:
					e = mid
				else:
					ans = choc
					s = mid + 1
			if ans == -1:
				break
			cnt += k // ans
			k = k % ans
		return cnt


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		c = 0
		(l, r) = (0, n - 1)
		while k > 0:
			ans = -1
			l = 0
			while l <= r:
				mid = (l + r) // 2
				mid_val = self.shop.get(mid)
				if mid_val == -1:
					ans = -1
				if mid_val > k:
					r = mid - 1
				else:
					ans = mid_val
					l = mid + 1
			if ans == -1:
				break
			c += k // ans
			k = k % ans
		return c


class Solution:
	shop = Shop()

	def __init__(self, shop):
		self.shop = shop

	def find(self, n, k):
		(ans, mid) = (0, n)
		while k > 0:
			(lo, hi) = (0, mid - 1)
			cost = -1
			while lo <= hi:
				mid = (lo + hi) // 2
				c = shop.get(mid)
				if c > cost and c <= k:
					cost = c
					lo = mid + 1
				else:
					hi = mid - 1
			if cost == -1 or cost > k:
				break
			ans += k // cost
			k %= cost
		return ans