Geek is organizing a party at his house. For the party, he needs exactly N donuts for the guests. Geek decides to order the donuts from a nearby restaurant, which has L chefs and each chef has a rank R. 
A chef with rank R can make 1 donut in the first R minutes, 1 more donut in the next 2R minutes, 1 more donut in 3R minutes, and so on.
For example. a chef with rank 2, can make one donut in 2 minutes, one more donut in the next 4 minutes, and one more in the next 6 minutes. So, it take 2 + 4 + 6 = 12 minutes to make 3 donuts. A chef can move on to making the next donut only after completing the previous one. All the chefs can work simultaneously.
Since, it's time for the party, Geek wants to know the minimum time required in completing N donuts. Return an integer denoting the minimum time
Example 1:
Input:
N = 10
L = 4
rank[] = {1, 2, 3, 4}
Output: 12
Explanation: 
Chef with rank 1, can make 4 donuts in time 1 + 2 + 3 + 4 = 10 mins
Chef with rank 2, can make 3 donuts in time 2 + 4 + 6 = 12 mins
Chef with rank 3, can make 2 donuts in time 3 + 6 = 9 mins
Chef with rank 4, can make 1 donuts in time = 4 minutes
Total donuts = 4 + 3 + 2 + 1 = 10 and total time = 12 minutes.
Example 2:
Input:
N = 8
L = 8
rank[] = {1, 1, 1, 1, 1, 1, 1, 1}
Output: 1
Explanation: 
As all chefs are ranked 1, so each chef can make 1 donuts 1 min.
Total donuts = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8 and total time = 1 minute. 
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findMinTime() which takes an integer N as input and an array A[] of length L denoting the ranks and return an integer denoting the minimum time.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{3}
1 <= L <= 50
1 <= L[i] <= 8

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Sorting

Starter code: 

from typing import List

class Solution:

    def findMinTime(self, n : int, l : int, arr : List[int]) -> int:

        # code here

        



Solutions:
from typing import List
from heapq import heappop, heappush

class Solution:

	def findMinTime(self, n: int, l: int, chef_ranks: List[int]) -> int:
		q = []
		for chef_rank in chef_ranks:
			heappush(q, (chef_rank, 2 * chef_rank, chef_rank))
		time = 0
		for _ in range(n):
			(time, next_rank, base_rank) = heappop(q)
			heappush(q, (time + next_rank, next_rank + base_rank, base_rank))
		return time


from typing import List
from heapq import heappop, heappush

class Solution:

	def findMinTime(self, n: int, l: int, chef_ranks: List[int]) -> int:
		q = []
		for chef_rank in chef_ranks:
			heappush(q, (chef_rank, 2 * chef_rank, chef_rank))
		time = donuts = 0
		while donuts < n:
			(time, next_rank, base_rank) = heappop(q)
			donuts += 1
			heappush(q, (time + next_rank, next_rank + base_rank, base_rank))
		return time


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:

		def isPossible(p, cook, n, mid):
			cnt = 0
			for i in range(n):
				c = 0
				time = mid
				perpratas = cook[i]
				while time > 0:
					time -= perpratas
					if time >= 0:
						c += 1
						perpratas += cook[i]
				cnt += c
				if cnt >= p:
					return True
			return False
		(s, e) = (0, 10000007)
		(mid, ans) = (-1, -1)
		while s <= e:
			mid = (s + e) // 2
			if isPossible(n, arr, l, mid):
				ans = mid
				e = mid - 1
			else:
				s = mid + 1
		return ans


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		arr.sort()
		low = arr[0]
		high = int(arr[l - 1] * (n * (n + 1) / 2))
		time = 0
		while low <= high:
			mid = int(low + (high - low) / 2)
			if possible(mid, arr, n) == 1:
				time = mid
				high = mid - 1
			else:
				low = mid + 1
		return time

def possible(mid, arr, n):
	donuts = 0
	for i in arr:
		timeTaken = 0
		timeWillTake = i
		time = timeTaken + timeWillTake
		while time <= mid:
			donuts += 1
			timeWillTake += i
			time += timeWillTake
	if donuts >= n:
		return 1
	else:
		return 0


from typing import List
import heapq

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		heap = []
		for item in arr:
			heap.append((item, item, 1))
		heapq.heapify(heap)
		for _ in range(n - 1):
			(time, item, count) = heapq.heappop(heap)
			count += 1
			heapq.heappush(heap, (time + item * count, item, count))
		return heap[0][0]


from typing import List

class Solution:

	def check(self, n, l, arr, mid):
		dish = 0
		for i in range(l):
			time = arr[i]
			j = 2
			while time <= mid:
				time += arr[i] * j
				dish += 1
				j += 1
			if dish >= n:
				return True
		return False

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		s = 0
		e = 999999
		ans = -1
		mid = (s + e) // 2
		while s <= e:
			if self.check(n, l, arr, mid) == True:
				ans = mid
				e = mid - 1
			else:
				s = mid + 1
			mid = (s + e) // 2
		return int(ans)


import heapq

class Solution:

	def findMinTime(self, n, l, arr) -> int:
		q = []
		for i in range(l):
			heapq.heappush(q, (arr[i], arr[i], 1))
		ans = 0
		for i in range(n):
			(cost, rank, cnt) = heapq.heappop(q)
			ans = max(cost, ans)
			cnt += 1
			newCost = rank * cnt
			heapq.heappush(q, (cost + newCost, rank, cnt))
		return ans


from typing import List

class Solution:

	def number(self, rank, time):
		count = 0
		till = rank
		while time >= till:
			count += 1
			time -= till
			till += rank
		return count

	def ischeck(self, arr, time, n):
		count = 0
		for x in arr:
			count += self.number(x, time)
		return count >= n

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		arr.sort()
		total = sum(arr)
		s_min = 0
		t_min = 0
		while s_min < n:
			s_min += 1
			t_min += arr[0] * s_min
		(l, r) = (0, t_min)
		ans = t_min
		while l <= r:
			mid = (l + r) // 2
			isGood = self.ischeck(arr, mid, n)
			if isGood:
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return ans


from typing import List
import heapq

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		heap = [[R, 1, R] for R in arr]
		heapq.heapify(heap)
		t = 0
		for _ in range(n):
			(time, dN, R) = heapq.heappop(heap)
			t = time
			dN += 1
			heapq.heappush(heap, [dN * (dN + 1) * R // 2, dN, R])
		return time


from typing import List
from math import ceil, floor

class Solution:

	def findMinTime(self, n: int, ll: int, arr: List[int]) -> int:

		def valid(mid):
			count = 0
			for i in arr:
				t = 0
				temp = i
				while t + temp <= mid:
					t += temp
					temp += i
					count += 1
					if count >= n:
						return True
			return False
		(fastest, slowest) = (min(arr), max(arr))
		x = floor(n / ll)
		l = fastest * (x * (x + 1)) // 2
		y = ceil(n / ll)
		r = slowest * (y * (y + 1)) // 2
		ans = None
		while l <= r:
			mid = l + (r - l) // 2
			if valid(mid):
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return ans


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		ans = []
		for x in arr:
			ele = x
			ans.append(x)
			for i in range(2, n + 1):
				ans.append(ans[-1] + ele * i)
		ans.sort()
		return ans[n - 1]


from typing import List

class Solution:

	def can_make_donuts(self, mid, arr, n):
		ans = 0
		for i in arr:
			time = mid
			j = 0
			donuts = i
			while time > 0:
				time -= donuts
				if time >= 0:
					donuts += i
					j += 1
			ans += j
			if ans >= n:
				return True
		return False

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		high = 10000000.0
		low = 0
		ans = -1
		while low <= high:
			mid = (low + high) // 2
			if self.can_make_donuts(mid, arr, n):
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return int(ans)


from collections import defaultdict
from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		d = defaultdict(int)
		for i in range(l):
			t = 0
			k = 1
			while k <= n:
				d[t + arr[i] * k] += 1
				t += arr[i] * k
				k += 1
		s = 0
		t = 0
		for i in sorted(d.keys()):
			s += d[i]
			if s >= n:
				t = i
				break
		return t


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:

		def ispossible(t):
			donuts = 0
			for i in range(0, len(arr)):
				if donuts >= n:
					return True
				curr = 0
				next = arr[i]
				while curr + next <= t:
					donuts += 1
					curr += next
					next += arr[i]
			if donuts >= n:
				return True
			return False
		arr.sort()
		start = 1
		end = arr[l - 1] * (n * (n + 1) // 2)
		ans = 0
		while start <= end:
			mid = start + end >> 1
			if ispossible(mid):
				ans = mid
				end = mid - 1
			else:
				start = mid + 1
		return ans


from typing import List

class Solution:

	def isPossible(self, p, cook, n, mid):
		cnt = 0
		for i in range(0, n):
			c = 0
			time = mid
			perpratas = cook[i]
			while time > 0:
				time = time - perpratas
				if time >= 0:
					c += 1
					perpratas += cook[i]
			cnt += c
			if cnt >= p:
				return True
		return False

	def binarysearch(self, l, r, rank, N):
		if l <= r:
			mid = (l + r) // 2
			pos = self.isPossible(N, rank, len(rank), mid)
			if pos:
				return self.binarysearch(l, mid - 1, rank, N)
			else:
				return self.binarysearch(mid + 1, r, rank, N)
		return l

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		return self.binarysearch(0, 10000007, arr, n)


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:

		def ispossible(T):
			donuts = 0
			for rank in arr:
				if donuts >= n:
					return True
				current = 0
				makeTime = rank
				while current + makeTime <= T:
					donuts += 1
					current += makeTime
					makeTime += rank
			if donuts >= n:
				return True
			return False
		arr.sort()
		start = 0
		end = arr[l - 1] * (n * (n + 1) // 2)
		ans = 0
		while start <= end:
			mid = start + end >> 1
			if ispossible(mid):
				ans = mid
				end = mid - 1
			else:
				start = mid + 1
		return ans


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:

		def ispossible(mid, n, arr):
			donuts = 0
			for t in arr:
				timetaken = 0
				timewilltake = t
				while timetaken + timewilltake <= mid:
					donuts += 1
					timetaken += timewilltake
					timewilltake += t
			return donuts >= n
		arr.sort()
		low = arr[0]
		high = arr[-1] * (n * (n + 1)) // 2
		while low <= high:
			mid = (low + high) // 2
			if ispossible(mid, n, arr):
				time = mid
				high = mid - 1
			else:
				low = mid + 1
		return time


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		arr.sort()
		l = arr[0]
		h = arr[-1] * n * (n + 1) // 2
		time = 0

		def helper(mid, arr, n):
			donut = 0
			for i in arr:
				timetaken = 0
				willtake = i
				while timetaken + willtake <= mid:
					donut += 1
					timetaken += willtake
					willtake += i
			return donut >= n
		while l <= h:
			mid = (l + h) // 2
			if helper(mid, arr, n):
				time = mid
				h = mid - 1
			else:
				l = mid + 1
		return time


from typing import List

class Solution:

	def findMinTime(self, n: int, x: int, arr: List[int]) -> int:
		arr.sort()
		l = arr[0]
		h = arr[x - 1] * (n * (n + 1) // 2)
		time = 0
		while l <= h:
			mid = (l + h) // 2
			if self.isPossible(mid, n, arr):
				time = mid
				h = mid - 1
			else:
				l = mid + 1
		return time

	def isPossible(self, mid, n, arr):
		donuts = 0
		for t in arr:
			timeTaken = 0
			timeWillTake = t
			while timeTaken + timeWillTake <= mid:
				donuts += 1
				timeTaken += timeWillTake
				timeWillTake += t
		if donuts >= n:
			return True
		else:
			return False


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		c = 0
		t = 0
		y = [0] * l
		while c < n:
			t += 1
			for i in range(l):
				if arr[i] * (y[i] + 1) * (y[i] + 2) / 2 == t:
					y[i] += 1
			c = sum(y)
		return t


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		donuts = [0 for i in range(l)]
		time = [0 for i in range(l)]
		cost = [arr[i] for i in range(l)]
		don_count = 0
		i = 0
		while don_count != n:
			mini = float('inf')
			minindex = 0
			for j in range(l):
				if cost[j] + time[j] <= mini:
					minindex = j
					mini = cost[j] + time[j]
			time[minindex] += cost[minindex]
			donuts[minindex] += 1
			cost[minindex] = arr[minindex] * (donuts[minindex] + 1)
			don_count += 1
		return max(time)


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:

		def funk(a, t):
			ans = 0
			for r in a:
				p = 0
				while p * (p + 1) // 2 * r <= t:
					p += 1
				ans += p - 1
			return ans
		i = 0
		j = 1
		while funk(arr, j) < n:
			i = j
			j *= 2
		while i <= j:
			m = j - (j - i) // 2
			if funk(arr, m) < n:
				i = m + 1
			elif funk(arr, m - 1) < n and funk(arr, m + 1) >= n:
				return m
			else:
				j = m - 1


from typing import List

class Solution:

	def isvalid(self, n, l, arr, m):
		count = 0
		for i in range(l):
			time = arr[i]
			p = 1
			totaltime = p * time
			while totaltime <= m:
				count += 1
				if count == n:
					return True
				p += 1
				totaltime += p * time
		return False

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		s = 0
		ans = -1
		e = max(arr) * ((n + 1) * n) // 2
		while s <= e:
			m = s + (e - s) // 2
			if self.isvalid(n, l, arr, m):
				ans = m
				e = m - 1
			else:
				s = m + 1
		return ans


from typing import List

class Solution:

	def isValid(self, n, l, arr, time):
		totalDonut = 0
		for i in range(l):
			temp = 1
			t = 0
			while t + temp * arr[i] <= time:
				totalDonut += 1
				t += temp * arr[i]
				temp += 1
				if totalDonut == n:
					return True
		return totalDonut >= n

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		start = 1
		end = int(max(arr) * (n * (n + 1) / 2))
		res = -1
		while start <= end:
			mid = (start + end) // 2
			if self.isValid(n, l, arr, mid):
				res = mid
				end = mid - 1
			else:
				start = mid + 1
		return res


from typing import List
import math

class Solution:

	def check(self, mid, n, arr):
		count = 0
		for l in arr:
			temp = int(math.sqrt(mid / l * 2))
			if l * temp * (temp + 1) > mid * 2:
				temp -= 1
			count += temp
		return count >= n

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		low = int(-1)
		high = int(1000000000.0)
		while low + 1 < high:
			mid = int((low + high) / 2)
			if self.check(mid, n, arr):
				high = mid
			else:
				low = mid
		return high


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		start = 0
		end = max(arr) * (n * (n + 1) // 2)
		res = end
		while start <= end:
			mid = start + (end - start) // 2
			if self.isvalid(arr, n, l, mid):
				res = mid
				end = mid - 1
			else:
				start = mid + 1
		return res

	def isvalid(self, arr, n, l, mid):
		ans = 0
		for i in range(l):
			count = 1
			sum = 0
			while sum + count * arr[i] <= mid:
				ans += 1
				sum += count * arr[i]
				count += 1
		return ans >= n


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		t = []
		for i in range(0, l):
			sum = 0
			for j in range(1, n + 1):
				sum += arr[i] * j
				t.append(sum)
		t.sort()
		return t[n - 1]


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		low = 0
		high = 10 ** 6
		ans = -1
		while low <= high:
			mid = (low + high) // 2
			res = 0
			for i in range(l):
				cap = arr[i]
				b = 2
				while cap <= mid:
					cap += arr[i] * b
					res += 1
					b += 1
			if res >= n:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:

		def canMake(T):
			num = 0
			for i in range(l):
				rank = arr[i]
				t = 0
				j = 1
				while t + j * rank <= T:
					num += 1
					t += j * rank
					j += 1
			return num >= n
		(left, right) = (0, max(arr) * (n / 2) * (n + 1) + 1)
		ans = -1
		while left <= right:
			mid = (left + right) // 2
			if canMake(mid):
				ans = mid
				right = mid - 1
			else:
				left = mid + 1
		return int(ans)


from typing import List
from math import floor, sqrt

def bs(arr, st, ed, n, x):
	if st > ed:
		return x
	h = (st + ed) // 2
	(p, ind) = (0, n)
	for i in arr:
		g = h / i
		ind -= floor((sqrt(1 + 8 * g) - 1) / 2)
		if ind <= 0:
			p = 1
			break
	if p:
		return bs(arr, st, h - 1, n, min(h, x))
	return bs(arr, h + 1, ed, n, x)

def codeforces(arr, n):
	arr.sort()
	h = arr[0] * n * (n + 1) / 2
	return int(bs(arr, 0, h, n, h))

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		return codeforces(arr, n)


from typing import List
from functools import cmp_to_key as ck

def cp(a, b):
	if a[0] < b[0]:
		return -1
	if a[0] > b[0]:
		return 1
	return 0

def codeforces(arr, k):
	arr.sort()
	x = [[k * (k + 1) / 2 * arr[0], arr[0], k]]
	n = len(arr)
	for ind in range(1, n):
		p = arr[ind]
		ans = 1
		top = x.pop()
		while top[0] >= p * ans * (ans + 1) / 2:
			y = (top[2] - 1) * top[2] * top[1] / 2
			x.append([y, top[1], top[2] - 1])
			x = sorted(x, key=ck(cp))
			top = x.pop()
			y = (top[2] - 1) * top[2] * top[1] / 2
			ans += 1
		x.append(top)
		if ans > 1:
			x.append([p * ans * (ans - 1) / 2, p, ans - 1])
			x = sorted(x, key=ck(cp))
	return int(x.pop()[0])

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		return codeforces(arr, n)


from heapq import *
from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		h = []
		heapify(h)
		lim = n / 2 * (2 * min(arr) + (n - 1) * min(arr))
		for i in range(l):
			val = arr[i]
			time = arr[i]
			inc = arr[i]
			while time <= lim:
				heappush(h, time)
				inc += val
				time += inc
		ans = 0
		while n:
			ans = heappop(h)
			n -= 1
		return ans


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		time = 0
		donuts = 0
		times = arr.copy()
		counts = [1] * l
		while donuts < n:
			time += 1
			for i in range(l):
				if time == arr[i]:
					donuts += 1
					counts[i] += 1
					arr[i] = counts[i] * (counts[i] + 1) * times[i] // 2
		return time


import math
from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:

		def is_possible(m, n):
			val = 0
			for i in range(len(arr)):
				(time, j) = (0, 1)
				while time + j * arr[i] <= m:
					val += 1
					time += j * arr[i]
					j += 1
				if val >= n:
					return True
			return False
		high = math.ceil(n / l) * 10000
		low = 1
		while low <= high:
			mid = low + (high - low) // 2
			if is_possible(mid, n):
				high = mid - 1
			else:
				low = mid + 1
		return high + 1


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		L = [0 for i in range(len(arr))]
		donuts = 0
		chk = 0
		while donuts < n:
			chk += 1
			for i in range(len(L)):
				if chk == arr[i]:
					L[i] += 1
					donuts += 1
				elif chk % arr[i] == 0 and (L[i] + 1) * (L[i] + 2) / 2 * arr[i] == chk:
					L[i] += 1
					donuts += 1
		return chk


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, a: List[int]) -> int:

		def poss(val):
			ans = 0
			for i in a:
				(low, high) = (0, i * n * (n + 1) // 2 + 1)
				while low < high:
					mid = (low + high) // 2
					if i * (mid * (mid + 1) // 2) > val:
						high = mid
					else:
						low = mid + 1
				ans += low - 1
			return ans
		(low, high) = (0, min(a) * (n * (n + 1) // 2) + 1)
		while low < high:
			mid = (low + high) // 2
			if poss(mid) >= n:
				high = mid
			else:
				low = mid + 1
		return low


from typing import List

class Solution:

	def check(self, n, time, arr):
		count = 0
		for i in arr:
			tempTime = time
			startTime = i
			while tempTime >= i:
				tempTime -= i
				i += startTime
				count += 1
		if count >= n:
			return True
		return False

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		arr.sort()
		time = 0
		for i in range(n):
			time += (i + 1) * arr[0]
		i = 1
		j = time
		ans = time
		while i <= j:
			mid = i + (j - i) // 2
			if self.check(n, mid, arr):
				ans = mid
				j = mid - 1
			else:
				i = mid + 1
		return ans


from typing import List
from heapq import *

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		h = [(i, i, 1) for i in arr]
		heapify(h)
		ans = 0
		while n:
			(a, b, c) = heappop(h)
			n -= 1
			c += 1
			heappush(h, (a + b * c, b, c))
		return a


from typing import List

class Solution:

	def isPossible(self, m, n, arr):
		c = 0
		for i in range(len(arr)):
			t = 0
			time = arr[i]
			while t + time <= m:
				c += 1
				t += time
				time += arr[i]
		if c >= n:
			return True
		return False

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		arr.sort()
		if n == 1:
			return arr[0]
		f = arr[0]
		r = arr[l - 1] * (n * (n + 1) // 2)
		time = 0
		while r >= f:
			m = (f + r) // 2
			if self.isPossible(m, n, arr):
				time = m
				r = m - 1
			else:
				f = m + 1
		return time


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, x: List[int]) -> int:

		def check(m):
			a = 0
			for r in x:
				nn = (-1 + (1 + 8 * m / r) ** 0.5) // 2
				a += nn
			return a >= n
		j = 10 ** 9
		i = 1
		ans = 0
		while i <= j:
			m = (i + j) // 2
			if check(m):
				ans = m
				j = m - 1
			else:
				i = m + 1
		return ans


from typing import List

class Solution:

	def solve(self, A, mid, n, l):
		total = 0
		for i in range(l):
			c = 0
			t = mid
			p = A[i]
			while t > 0:
				t -= p
				if t >= 0:
					c += 1
					p += A[i]
			total += c
			if total >= n:
				return 1
		return 0

	def findMinTime(self, n: int, ll: int, arr: List[int]) -> int:
		l = 0
		r = int(1000000.0)
		ans = int(100000.0)
		while l <= r:
			mid = (l + r) // 2
			if self.solve(arr, mid, n, ll):
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return ans


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		arr.sort()
		low = arr[0]
		high = arr[-1] * (n * (n + 1) // 2)
		ans = 0

		def is_possible(arr, mid, n):
			donuts = 0
			for i in range(len(arr)):
				totalTime = 0
				timeTaken = arr[i]
				while totalTime + timeTaken <= mid:
					donuts += 1
					if donuts >= n:
						return True
					totalTime += timeTaken
					timeTaken += arr[i]
			return False
		while low <= high:
			mid = (low + high) // 2
			if is_possible(arr, mid, n):
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		lo = 0
		hi = 1000000000.0

		def f(k):
			lo = 0
			hi = k
			while lo <= hi:
				mid = (lo + hi) // 2
				if mid * (mid + 1) // 2 > k:
					hi = mid - 1
				else:
					lo = mid + 1
			return lo - 1

		def ok(m):
			curr = 0
			for x in arr:
				curr += f(m // x)
			return curr >= n
		while lo <= hi:
			mid = (lo + hi) // 2
			if ok(mid):
				hi = mid - 1
			else:
				lo = mid + 1
		return int(hi + 1)


from typing import List

class Solution:

	def donuts(self, o, lt):
		count = 0
		for i in lt:
			(time, nut, c) = (0, 0, 1)
			while time < o:
				if time + c * i <= o:
					nut += 1
					time += c * i
					c += 1
				else:
					break
			count += nut
		return count

	def search(self, l, h, lt, temp, n):
		while l <= h:
			mid = (l + h) // 2
			k = self.donuts(mid, lt)
			if k >= n:
				temp = mid
				(l, h) = (l, mid - 1)
			elif k < n:
				(l, h) = (mid + 1, h)
		return temp

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		(lo, u, koi) = (0, min(arr) * (n * (n + 1) // 2), 0)
		koi = self.search(lo, u, arr, u, n)
		return koi


from typing import List
from math import sqrt

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		belt = [0] * len(arr)
		for t in range(1, 1000000):
			for chef in range(0, len(arr)):
				belt[chef] = int(0.5 * (sqrt(8 * t / arr[chef] + 1) - 1))
			if sum(belt) >= n:
				return t


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, r: List[int]) -> int:
		lst = r.copy()
		n_lst = [0] * l
		i = 1
		m = 0
		while m < n:
			for j in range(l):
				if lst[j] == i:
					m += 1
					n_lst[j] += 1
					lst[j] += (n_lst[j] + 1) * r[j]
			i += 1
		return i - 1


from typing import List

class Solution:

	def isPossible(self, arr, len_arr, n, mid):
		count = 0
		for i in range(len_arr):
			totalTime = 0
			currTime = arr[i]
			while totalTime + currTime <= mid:
				count += 1
				if count >= n:
					return True
				totalTime += currTime
				currTime += arr[i]
		return False

	def findMinTime(self, n, len_arr, arr):
		arr.sort()
		left = arr[0]
		right = arr[len_arr - 1] * (n * (n + 1) // 2)
		ans = 0
		while left <= right:
			mid = (left + right) // 2
			if self.isPossible(arr, len_arr, n, mid):
				ans = mid
				right = mid - 1
			else:
				left = mid + 1
		return ans


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		ap_sum = lambda n: n * (n + 1) // 2

		def check(time):
			total = 0
			for r in arr:
				cur = time // r
				opt1 = (-1 + (1 + 8 * cur) ** 0.5) // 2
				opt2 = (-1 - (1 + 8 * cur) ** 0.5) // 2
				total += max(opt1, opt2)
			return total >= n
		low = 0
		ml = max(arr)
		high = ap_sum(ml) * ml
		high = 10 ** 6
		while low < high:
			mid = (low + high) // 2
			if check(mid):
				high = mid
			else:
				low = mid + 1
		return low


from typing import List
import heapq

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:

		class Chef:

			def __init__(self, id, rank):
				self.id = id
				self.time = rank
				self.multiplier = 2
				self.rank = rank

			def __lt__(self, other):
				return self.time < other.time
		time = [0 for i in range(l)]
		chefs = [Chef(i, arr[i]) for i in range(l)]
		heapq.heapify(chefs)
		for d in range(n):
			chef = heapq.heappop(chefs)
			time[chef.id] = chef.time
			chef.time += chef.multiplier * chef.rank
			chef.multiplier += 1
			heapq.heappush(chefs, chef)
		return max(time)


from typing import List

class Solution:

	def per_count(self, R, t, n):
		left = 0
		right = int(1000000000.0)
		while left < right:
			mid = left + (right - left) // 2
			if mid * (mid + 1) // 2 * R > t:
				right = mid
			else:
				left = mid + 1
		return left - 1

	def count(self, arr, t, n):
		total_count = 0
		for i in range(len(arr)):
			total_count += self.per_count(arr[i], t, n)
		return total_count

	def possible(self, arr, n, x):
		return self.count(arr, x, n) >= n

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		left = 0
		right = int(1000000000.0)
		while left < right:
			mid = left + (right - left) // 2
			if not self.possible(arr, n, mid):
				left = mid + 1
			else:
				right = mid
		return left


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		i = 0
		x = [1] * l
		t = [0] * l
		res = 0
		while i <= n:
			temp = [arr[j] + t[j] for j in range(l)]
			m = min(temp)
			ind = temp.index(m)
			arr[ind] = arr[ind] // x[ind] * (x[ind] + 1)
			x[ind] += 1
			t[ind] = m
			i += 1
			if i == n:
				res = max(t)
		return res


from typing import List

class Chef:

	def __init__(self, rank: int):
		self.rank = rank
		self.donuts_produced = 0
		self.time = 0
		self.next_time = rank

	def add(self):
		self.time = self.next_time
		self.donuts_produced += 1
		self.next_time += self.rank * (self.donuts_produced + 1)

	def __repr__(self):
		data = (str(a) for a in (self.rank, self.donuts_produced, self.time))
		return '(' + ', '.join(data) + ')'

class DonutFactory:

	def __init__(self, chefs: List[Chef]):
		self.chefs = chefs
		self.time = 0
		self.donuts = 0

	def produce_one_more(self):
		selected_chef = min(self.chefs, key=lambda chef: chef.next_time)
		selected_chef.add()
		self.time = selected_chef.time
		self.donuts += 1

	def __str__(self):
		data = [str(chef) for chef in self.chefs]
		return ', '.join(data)

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		chefs = [Chef(rank) for rank in arr]
		donut_factory = DonutFactory(chefs)
		while donut_factory.donuts < n:
			donut_factory.produce_one_more()
		return donut_factory.time


from typing import List

class Solution:

	def findMinTime(self, l: int, n: int, arr: List[int]) -> int:
		arr.sort()

		def isPossible(arr, l, n, curS):
			i = 0
			Ans = True
			while l and i < n:
				curE = arr[i]
				if curE > curS:
					Ans = False
					break
				s = curS / curE
				l = l - (-1 + (8 * s + 1) ** (1 / 2)) // 2
				i += 1
			return True if l <= 0 else False

		def binary(arr, lo, hi):
			while lo <= hi:
				middle = (lo + hi) // 2
				if isPossible(arr, l, n, middle):
					hi = middle - 1
				else:
					lo = middle + 1
			return lo
		hi = max(arr) * (l * (l + 1) // 2)
		return binary(arr, 0, hi)


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:

		def isdone(t):
			donuts = 0
			for chef in arr:
				if donuts >= n:
					return True
				current = 0
				make_time = chef
				while current + make_time <= t:
					donuts += 1
					current += make_time
					make_time += chef
			return donuts >= n
		arr.sort()
		l = 0
		r = arr[l - 1] * (n * (n + 1) // 2)
		mintime = 0
		while l <= r:
			midtime = l + (r - l) // 2
			if isdone(midtime):
				mintime = midtime
				r = midtime - 1
			else:
				l = midtime + 1
		return mintime


from typing import List
import math

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		(max_time, min_time) = (math.ceil(max(arr) * math.ceil(n / l) * math.ceil(n / l + 1) / 2), math.ceil(min(arr) * math.ceil(n / l) * math.ceil(n / l + 1) / 2))
		return self.binary_search(n, arr, max_time, min_time)

	def binary_search(self, n, arr, max_time, min_time):
		mid = math.ceil((max_time + min_time) / 2)
		if max_time >= min_time:
			if self.total_donut(arr, mid) > n:
				return self.binary_search(n, arr, mid - 1, min_time)
			elif self.total_donut(arr, mid) < n:
				return self.binary_search(n, arr, max_time, mid + 1)
			else:
				mid = math.ceil(mid)
				while mid > 0:
					if self.total_donut(arr, mid) >= n:
						mid -= 1
					else:
						return mid + 1
				return mid + 1
		else:
			return max(max_time, min_time)

	def total_donut(self, arr, mid):
		summ = 0
		for R in arr:
			n = (-1 + math.sqrt(1 + 8 * mid / R)) // 2
			summ += n
		return summ


from typing import List

class Solution:

	def possible(self, mid, arr, n):
		r = 0
		for i in range(len(arr)):
			c = 0
			t = 0
			x = 1
			while t <= mid:
				t += arr[i] * x
				x += 1
				if t <= mid:
					c += 1
			r += c
		if r >= n:
			return True
		else:
			return False
		pass

	def findMinTime(self, n, l, arr):
		a = 1
		maxi = 0
		arr.sort()
		for i in range(n):
			maxi += (i + 1) * arr[0]
		left = 0
		right = maxi
		mid = 0
		result = maxi
		while left <= right:
			mid = (right + left) // 2
			if self.possible(mid, arr, n):
				right = mid - 1
				result = mid
			else:
				left = mid + 1
		return result


from typing import List

class Solution:

	def isPossible(self, x, N, arr):
		n = 0
		for i in range(len(arr)):
			a = arr[i]
			a1 = a * a + 8 * x * a
			a3 = a1 ** 0.5 - a
			a4 = a3 / (2 * a)
			n += int(a4)
			if n >= N:
				return True
		return False

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		maxi = 0
		i = 1
		while i <= n:
			maxi += i * arr[0]
			i += 1
		i = 0
		j = maxi
		ans = -1
		while i <= j:
			mid = (i + j) // 2
			if self.isPossible(mid, n, arr):
				ans = mid
				j = mid - 1
			else:
				i = mid + 1
		return ans


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:
		left = 0
		right = 0
		m = max(arr)
		mul = 1
		for _ in range(n):
			right += m * mul
			mul += 1
		while left <= right:
			mid = int((left + right) / 2)
			cur = 0
			for rank in arr:
				mul = 1
				tmp = rank * mul
				time = tmp
				co = 0
				while time <= mid:
					co += 1
					mul += 1
					tmp = rank * mul
					time += tmp
				cur += co
			if cur < n:
				left = mid + 1
			else:
				right = mid - 1
		ans = 0
		for rank in arr:
			mul = 1
			tmp = rank * mul
			time = tmp
			while time <= left:
				mul += 1
				tmp = rank * mul
				ans = max(ans, time)
				time += tmp
		return ans


from typing import List

class Solution:

	def findMinTime(self, n: int, l: int, arr: List[int]) -> int:

		def findNoOfDonuts(t):
			donuts = 0
			for i in arr:
				totalTime = 0
				chefTime = i
				while totalTime + chefTime <= t:
					donuts += 1
					if donuts >= n:
						return True
					totalTime += chefTime
					chefTime += i
			return False
		arr.sort()
		low = arr[0]
		high = arr[0] * (n * (n + 1) // 2)
		minTime = 0
		while low <= high:
			mid = (low + high) // 2
			if findNoOfDonuts(mid):
				minTime = mid
				high = mid - 1
			else:
				low = mid + 1
		return minTime