Geek wants to scan N documents using two scanners. If S1 and S2 are the time taken by the scanner 1 and scanner 2 to scan a single document, find the minimum time required to scan all the N documents. You can use one or more scanners at a time.
Example 1:
Input: 
S1 = 2, S2 = 4, N = 2
Output: 4
Explaination: Here we have two possibilities. 
Either scan both documents in scanner 1 or
scan one document in each scanner. 
In both the cases time required is 4.
 
Example 2:
Input: 
S1 = 1, S2 = 3, N = 2
Output: 2
Explaination: Here the optimal approach is to 
scan both of them in the first scanner.
 
Your Task:
You do not need to read input or print anything. Your task is to complete the function minTime() which takes S1, S2 and N as input parameters and returns the minimum tme required to scan the documents.
 
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ S1, S2, N ≤ 10^{6}
1 ≤ S1*N, S2*N ≤ 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Mathematics

Starter code: #User function Template for python3



class Solution:

    def minTime(self, S1, S2, N):

        # code here

Solutions:
def mgc(n, s1, s2):
	(st, en) = (0, n)
	ans = 99999999999999999999
	while st <= en:
		mid = (st + en) // 2
		ans = min(ans, max(s1 * mid, s2 * (n - mid)))
		if s1 * mid > s2 * (n - mid):
			en = mid - 1
		else:
			st = mid + 1
	return ans

class Solution:

	def minTime(self, S1, S2, N):
		return mgc(N, S1, S2)


class Solution:

	def minTime(self, S1, S2, N):
		min_tim = min(S1, S2)
		max_time = max(S1, S2)
		if min_tim * N <= max_time:
			return N * min_tim
		x = N * max_time // (S1 + S2)
		a = N - x
		b = x + 1
		c = N - b
		ans1 = max(x * min_tim, a * max_time)
		ans2 = max(b * min_tim, c * max_time)
		return min(ans1, ans2)


class Solution:

	def minTime(self, S1, S2, N):
		low = 1
		high = min(S1, S2) * N
		while low < high:
			mid = (low + high) // 2
			copies = sum([mid // S1, mid // S2])
			if copies < N:
				low = mid + 1
			else:
				high = mid
		return low


class Solution:

	def minTime(self, S1, S2, N):
		if S1 > S2:
			(S1, S2) = (S2, S1)
		l = 0
		r = N
		mini = S2 * N
		maxa = S2 * N
		while l <= r:
			mid = (l + r) // 2
			mini = min(mini, max(mid * S1, (N - mid) * S2))
			if mid * S1 <= (N - mid) * S2:
				l = mid + 1
			else:
				r = mid - 1
		return mini


class Solution:

	def minTime(self, S1, S2, N):
		if S1 < S2:
			for i in range(N + 1):
				if S1 * i > S2 * (N - i):
					return min(max(S1 * i, S2 * (N - i)), max(S1 * (i + 1), S2 * (N - i - 1)), max(S1 * (i - 1), S2 * (N - i + 1)))
		elif S1 > S2:
			for i in range(N + 1):
				if S2 * i > S1 * (N - i):
					return min(max(S2 * i, S1 * (N - i)), max(S2 * (i + 1), S1 * (N - i - 1)), max(S2 * (i - 1), S1 * (N - i + 1)))
		elif N % 2 == 0:
			return N // 2 * S1
		else:
			return (N // 2 + 1) * S1


class Solution:

	def minTime(self, S1, S2, N):
		if S1 < S2:
			(S1, S2) = (S2, S1)
		i = (N + 1) // 2
		a = S1 * i
		b = S2 * (N - i)
		time = a
		while a > b:
			time = a
			i -= 1
			a = S1 * i
			b = S2 * (N - i)
		return min(time, b)


class Solution:

	def binarysearch(self, l, r, s1, s2, n):
		if l <= r:
			mid = (l + r) // 2
			t1 = max(s1 * mid, (n - mid) * s2)
			t2 = max(s1 * (mid + 1), (n - mid - 1) * s2)
			t3 = max(s1 * (mid - 1), (n - mid + 1) * s2)
			if t1 > t2 and t3 > t1:
				return self.binarysearch(mid + 1, r, s1, s2, n)
			elif t1 < t2 and t3 < t1:
				return self.binarysearch(l, mid - 1, s1, s2, n)
			elif t1 <= t2 and t1 <= t3:
				return mid
		t1 = max(s1 * l, (n - l) * s2)
		t2 = max(s1 * r, (n - r) * s2)
		if t1 < t2:
			return l
		return r

	def minTime(self, S1, S2, N):
		l = self.binarysearch(1, N - 1, S1, S2, N)
		t = max(S1 * l, S2 * (N - l))
		return min(t, S1 * N, S1 * N)


class Solution:

	def minTime(self, S1, S2, N):
		l = 0
		r = N
		ans = float('inf')
		while l <= r:
			m = l + (r - l) // 2
			temp = max(S1 * m, S2 * (N - m))
			ans = min(ans, temp)
			if m * S1 >= (N - m) * S2:
				r = m - 1
			else:
				l = m + 1
		return ans


class Solution:

	def minTime(self, S1, S2, N):
		(mit, mat) = (0, 0)
		(mit, mat) = (S1, S2) if S1 <= S2 else (S2, S1)
		if mit * N <= mat:
			return N * mit
		x = N * mat // (S1 + S2)
		a = N - x
		b = x + 1
		c = N - b
		a1 = x * mit if x * mit > a * mat else a * mat
		a2 = b * mit if b * mit > c * mat else c * mat
		return a1 if a1 < a2 else a2


class Solution:

	def minTime(self, S1, S2, N):
		if S1 < S2:
			(S1, S2) = (S2, S1)
		i = (N + 1) // 2
		slow = S1 * i
		fast = S2 * (N - i)
		result = slow
		while slow > fast:
			result = slow
			i -= 1
			slow = S1 * i
			fast = S2 * (N - i)
		return min(result, fast)


class Solution:

	def minTime(self, s1, s2, n):
		min_val = n * min(s1, s2)
		min_side = min(s1, s2)
		max_side = max(s1, s2)
		low = 0
		high = n
		while low <= high:
			mid = (low + high) // 2
			min_val = min(min_val, max(min_side * mid, max_side * (n - mid)))
			if low == high:
				break
			if min_side * mid < max_side * (n - mid):
				low = mid + 1
			else:
				high = mid - 1
		return min_val


class Solution:

	def minTime(self, S1, S2, N):
		ans1 = S1 * N
		ans2 = S2 * N
		if S1 > S2:
			(S1, S2) = (S2, S1)
		low = 1
		high = N
		ans3 = 100000000000
		while low <= high:
			mid = (low + high) // 2
			su = max(mid * S1, (N - mid) * S2)
			ans3 = min(ans3, su)
			if mid * S1 > (N - mid) * S2:
				high = mid - 1
			else:
				low = mid + 1
		return min(ans1, ans2, ans3)


class Solution:

	def minTime(self, s1, s2, n):

		def itmget(s1, s2, temp):
			ans = 0
			ans += temp // s1 + temp // s2
			return ans

		def bs(s1, s2, n, mx):
			low = 1
			high = mx
			while low < high:
				mid = (low + high) // 2
				itm = itmget(s1, s2, mid)
				if itm < n:
					low = mid + 1
				else:
					high = mid
			return high
		return bs(s1, s2, n, max(s1, s2) * n)


class Solution:

	def minTime(self, S1, S2, N):
		if S1 > S2:
			(S1, S2) = (S2, S1)
		left = 0
		right = N
		minim = N * S2
		while left <= right:
			mid = (left + right) // 2
			minim = min(minim, max(mid * S1, (N - mid) * S2))
			if mid * S1 <= (N - mid) * S2:
				left = mid + 1
			else:
				right = mid - 1
		return minim


class Solution:

	def minTime(self, S1, S2, N):

		def check(mid, minval, maxval, n):
			mincount = mid // minval
			maxcount = mid // maxval
			if mincount + maxcount >= n:
				return True
			else:
				return False
		minval = min(S1, S2)
		maxval = max(S1, S2)
		ans = N * minval
		left = minval
		right = N * minval
		while left <= right:
			mid = (left + right) // 2
			if check(mid, minval, maxval, N):
				ans = mid
				right = mid - 1
			else:
				left = mid + 1
		return ans


class Solution:

	def minTime(self, S1, S2, N):
		a = S1
		b = S2
		if a > b:
			(a, b) = (b, a)
		end = N
		start = 0
		mini = b * N
		while start <= end:
			mid = (start + end) // 2
			mini = min(mini, max(a * mid, b * (N - mid)))
			if a * mid <= b * (N - mid):
				start = mid + 1
			else:
				end = mid - 1
		return mini


import math

class Solution:

	def minTime(self, S1, S2, N):
		mini = 100000000000
		if S1 > S2:
			(S1, S2) = (S2, S1)
		i = 0
		j = N
		while i <= j:
			mid = math.ceil((i + j) / 2)
			left = max(S1 * (mid - 1), S2 * (N - mid + 1))
			x = max(S1 * mid, S2 * (N - mid))
			right = max(S1 * (mid + 1), S2 * (N - mid - 1))
			if left >= x and x <= right:
				return x
			if left > x and right < x:
				i = mid
				continue
			if left < x and x < right:
				j = mid
				continue


class Solution:

	def minTime(self, S1, S2, N):
		l = 0
		r = N
		while l <= r:
			m = (l + r) // 2
			time_m = max(m * S1, (N - m) * S2)
			time_l = max((m - 1) * S1, (N - m + 1) * S2) if m - 1 >= 0 else float('inf')
			time_r = max((m + 1) * S1, (N - m - 1) * S2) if m + 1 <= N else float('inf')
			if time_r >= time_m <= time_l:
				return time_m
			if time_r > time_l:
				r = m - 1
			else:
				l = m + 1
		return -1


class Solution:

	def minTime(self, S1, S2, N):
		if S1 > S2:
			(S1, S2) = (S2, S1)
		low = 0
		high = N
		minimum = min(S1, S2) * N
		while low <= high:
			mid = low + (high - low) // 2
			minimum = min(minimum, max(S1 * mid, S2 * (N - mid)))
			if S1 * mid <= S2 * (N - mid):
				low = mid + 1
			else:
				high = mid - 1
		return minimum
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S1, S2, N) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.minTime(S1, S2, N))


class Solution:

	def minTime(self, S1, S2, N):
		lo = 0
		hi = N
		ans = N * min(S1, S2)
		while lo <= hi:
			mid = (lo + hi) // 2
			R1 = mid * S1
			R2 = (N - mid) * S2
			if max(R1, R2) < ans:
				ans = max(R1, R2)
			if R1 > R2:
				hi = mid - 1
			else:
				lo = mid + 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S1, S2, N) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.minTime(S1, S2, N))


class Solution:

	def minTime(self, S1, S2, N):
		lo = 0
		hi = N
		mn = 10 ** 32
		while lo <= hi:
			mid = (lo + hi) // 2
			mn = min(mn, max(S1 * mid, S2 * (N - mid)))
			if S1 * mid <= S2 * (N - mid):
				lo = mid + 1
			else:
				hi = mid - 1
		return mn
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S1, S2, N) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.minTime(S1, S2, N))


class Solution:

	def minTime(self, S1, S2, N):
		result = float('inf')
		floor = 0
		ceil = N
		while ceil >= floor:
			i = floor + (ceil - floor) // 2
			s1_docs = i
			s2_docs = N - i
			s1_time = S1 * s1_docs
			s2_time = S2 * s2_docs
			time = s1_time if s1_time > s2_time else s2_time
			result = result if result < time else time
			if s2_time > s1_time:
				floor = i + 1
			else:
				ceil = i - 1
		return result
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S1, S2, N) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.minTime(S1, S2, N))


import sys

class Solution:

	def minTime(self, S1, S2, N):
		low = 0
		high = N
		ans = sys.maxsize
		while low <= high:
			mid = (low + high) // 2
			n1 = mid * S1
			n2 = (N - mid) * S2
			ans = min(ans, max(n1, n2))
			if n1 == n2:
				return ans
			if n1 < n2:
				low = mid + 1
			if n1 > n2:
				high = mid - 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S1, S2, N) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.minTime(S1, S2, N))


def bs(S1, S2, n, M, high):
	low = 1
	while low < high:
		mid = high + low >> 1
		items = findItems(S1, S2, mid)
		if items < N:
			low = mid + 1
		else:
			high = mid
	return high

def findItems(S1, S2, temp):
	ans = 0
	ans += temp // S1
	ans += temp // S2
	return ans

class Solution:

	def minTime(self, S1, S2, N):
		maxVal = max(S1, S2)
		minVal = min(S1, S2)
		return bs(minVal, maxVal, 2, N, maxVal * N)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S1, S2, N) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.minTime(S1, S2, N))


import math

class Solution:

	def minTime(self, S1, S2, N):
		low = 0
		high = max(S1, S2) * N
		ans = -1
		while low < high:
			mid = (low + high) // 2
			possible = mid // S1 + mid // S2
			if possible >= N:
				ans = mid
				high = mid
			else:
				low = mid + 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S1, S2, N) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.minTime(S1, S2, N))


class Solution:

	def minTime(self, S1, S2, N):
		if S1 > S2:
			temp = S1
			S1 = S2
			S2 = temp
		l = 0
		h = N
		ma = 99999999
		while l <= h:
			m = (l + h) // 2
			ans = max(S1 * m, S2 * (N - m))
			ma = min(ans, ma)
			if S1 * m > S2 * (N - m):
				h = m - 1
			else:
				l = m + 1
		return ma
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S1, S2, N) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.minTime(S1, S2, N))


import sys

class Solution:

	def minTime(self, S1, S2, N):
		low = 0
		high = N
		ans = sys.maxsize
		while low <= high:
			mid = int((low + high) / 2)
			temp = max(S1 * mid, S2 * (N - mid))
			ans = min(temp, ans)
			if S1 * mid > S2 * (N - mid):
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def minTime(self, S1, S2, N):

		def ok(t):
			return t // S1 + t // S2 >= N
		lo = min(S1, S2)
		hi = min(S1, S2) * N + 1
		while lo < hi:
			mi = lo + (hi - lo) // 2
			if ok(mi):
				hi = mi
			else:
				lo = mi + 1
		return lo


class Solution:

	def minTime(self, S1, S2, N):
		a = min(S1, S2)
		b = max(S1, S2)
		low = 0
		high = N
		mini = N * b
		while low <= high:
			mid = low + (high - low) // 2
			mini = min(mini, max(mid * a, (N - mid) * b))
			if mid * a <= (N - mid) * b:
				low = mid + 1
			else:
				high = mid - 1
		return int(mini)


class Solution:

	def minTime(self, S1, S2, N):
		wt = N * S1 * S2 // (S1 + S2)
		if N - (wt // S1 + wt // S2) == 0:
			return wt
		else:
			return wt + min(S1 - wt % S1, S2 - wt % S2)


class Solution:

	def minTime(self, s1, s2, n):
		wt = n * s1 * s2 // (s1 + s2)
		if n - (wt // s1 + wt // s2) == 0:
			return wt
		else:
			return wt + min(s1 - wt % s1, s2 - wt % s2)


class Solution:

	def minTime(self, S1, S2, N):
		l = 0
		h = N
		while l <= h:
			middle = (l + h) // 2
			m_time = max(middle * S1, (N - middle) * S2)
			if l == h:
				return m_time
			left_time = max((middle - 1) * S1, (N - middle + 1) * S2) if middle - 1 >= 0 else float('inf')
			right_time = max((middle + 1) * S1, (N - middle - 1) * S2) if middle + 1 <= N else -float('inf')
			if left_time >= m_time <= right_time:
				return m_time
			if left_time > m_time and right_time < m_time:
				l = middle + 1
			else:
				h = middle - 1
		return -1


class Solution:
	import math

	def minTime(self, S1, S2, N):
		T_x = N * S1 * S2 / (S1 + S2)
		N1 = T_x * 1 / S1 // 1
		N2 = T_x * 1 / S2 // 1
		N_rest = N - N1 - N2
		return int(max(min(N1 * S1 + N_rest * S1, N2 * S2 + N_rest * S2), N1 * S1, N2 * S2))


class Solution:

	def minTime(self, S1, S2, N):
		s = min(S1, S2)
		(lo, hi) = (1, N * s)
		result = -1
		while lo <= hi:
			mid = (lo + hi) // 2
			value = mid // S1 + mid // S2
			if value == N:
				result = mid
				hi = mid - 1
			elif value > N:
				if (mid - 1) // S1 + (mid - 1) // S2 < N:
					result = mid
				hi = mid - 1
			else:
				if (mid + 1) // S1 + (mid + 1) // S2 > N:
					result = mid + 1
				lo = mid + 1
		return result


class Solution:

	def minTime(self, S1, S2, N):
		l = 0
		h = N
		ans = 1000000000.0
		while l <= h:
			mid = l + (h - l) // 2
			ans = min(ans, max(S1 * mid, S2 * (N - mid)))
			if S1 * mid <= S2 * (N - mid):
				l = mid + 1
			else:
				h = mid - 1
		return ans


class Solution:

	def minTime(self, S1, S2, N):
		low = 0
		high = N
		min_time = 2 ** 31 + 1
		while low <= high:
			mid = low + (high - low) // 2
			max_time = max(S1 * mid, S2 * (N - mid))
			min_time = min(min_time, max_time)
			if S1 * mid >= S2 * (N - mid):
				high = mid - 1
			else:
				low = mid + 1
		return min_time


import math

class Solution:

	def minTime(self, S1, S2, N):
		lowerBound = 0
		upperBound = min(S1, S2) * N
		time = upperBound
		while lowerBound <= upperBound:
			mid = math.floor((lowerBound + upperBound) / 2)
			numOfDocs = math.floor(mid / S1) + math.floor(mid / S2)
			if numOfDocs >= N:
				time = mid
				upperBound = mid - 1
			else:
				lowerBound = mid + 1
		return time


class Solution:

	def is_possible(self, S1, S2, mid, N):
		num_of_doc = mid // S1 + mid // S2
		if num_of_doc >= N:
			return True
		return False

	def minTime(self, S1, S2, N):
		s = 1
		e = max([S1, S2]) * N
		mid = (s + e) // 2
		while s < e:
			if self.is_possible(S1, S2, mid, N):
				e = mid
			else:
				s = mid + 1
			mid = (s + e) // 2
		return e


class Solution:

	def minTime(self, S1, S2, N):
		x = N * S2 // (S2 + S1)
		y = N * S1 // (S2 + S1)
		ax = x
		ay = N - x
		ans1 = max(ax * S1, ay * S2)
		ay = y
		ax = N - y
		ans2 = max(ax * S1, ay * S2)
		ans = min(ans1, ans2)
		return ans


class Solution:

	def minTime(self, S1, S2, N):
		l = 0
		h = N
		a = float('inf')
		while l <= h:
			m = (l + h) // 2
			t = max(S1 * m, S2 * (N - m))
			a = min(a, t)
			if S1 * m > S2 * (N - m):
				h = m - 1
			else:
				l = m + 1
		return a


import math

class Solution:

	def minTime(self, S1, S2, N):
		if S1 < S2:
			(S1, S2) = (S2, S1)
		t1 = S1 * N
		t2 = 0
		while t1 > t2:
			t1 -= S1
			t2 += S2
		max1 = max(t1, t2)
		t1 += S1
		t2 -= S2
		max2 = max(t1, t2)
		return min(max1, max2)


class Solution:

	def minTime(self, s1, s2, n):
		t = 1 + (s1 * s2 * n - 1) // (s1 + s2)
		if t // s1 + t // s2 < n:
			return t + min(s1 - t % s1, s2 - t % s2)
		return t


class Solution:

	def minTime(self, S1, S2, N):
		if S1 == S2:
			if N % 2 == 0:
				return N // 2 * S1
			else:
				return (N // 2 + 1) * S1
		else:
			min1 = S1
			max1 = S2
			if S1 > S2:
				min1 = S2
				max1 = S1
			low = 1
			high = N
			minimum = min(S1, S2) * N
			while low < high:
				mid = (low + high) // 2
				sum1 = min1 * mid
				sum2 = max1 * (N - mid)
				minimum = min(minimum, max(sum1, sum2))
				if sum1 == sum2:
					return sum1
				elif sum1 < sum2:
					low = mid + 1
				else:
					high = mid
			return minimum


class Solution:

	def findans(self, time, s1, s2):
		return time // s1 + time // s2

	def minTime(self, S1, S2, N):
		low = 1
		high = max(S1, S2) * N
		res = 2 ** 32
		while low <= high:
			mid = low + (high - low) // 2
			ans = self.findans(mid, S1, S2)
			if ans >= N:
				res = min(res, mid)
				high = mid - 1
			else:
				low = mid + 1
		return res if res != 2 ** 32 else -1


class Solution:

	def minTime(self, S1, S2, N):
		faster = min(S1, S2)
		slower = max(S1, S2)
		fasterTime = N * faster
		slowerTime = 0
		if fasterTime > slower:
			while fasterTime > slowerTime + slower:
				fasterTime -= faster
				slowerTime += slower
		return max(fasterTime, slowerTime)


import math

class Solution:

	def minTime(self, S1, S2, N):
		time_fn = lambda a: max(S1 * a, S2 * (N - a))
		if S1 > S2:
			(S1, S2) = (S2, S1)
		minTime = N * S1
		l = 0
		h = N
		while l <= h:
			mid = l + (h - l) // 2
			t = time_fn(mid)
			minTime = min(minTime, t)
			if S1 * mid <= S2 * (N - mid):
				l = mid + 1
			else:
				h = mid - 1
		return minTime


from math import ceil, floor

class Solution:

	def minTime(self, S1, S2, N):
		if S2 > S1:
			(S1, S2) = (S2, S1)
		cycles = floor(N / (S1 / S2 + 1))
		rest = N - cycles * (S1 / S2 + 1)
		return int(round(cycles * S1 + min(rest * S2, max((rest - 1) * S2, S1))))


class Solution:

	def minTime(self, S1, S2, N):
		a = min(S1, S2)
		b = S1 + S2 - a
		mini = b * N
		l = 0
		r = N
		while l <= r:
			m = (l + r) // 2
			mini = min(mini, max(a * m, b * (N - m)))
			if a * m <= b * (N - m):
				l = m + 1
			else:
				r = m - 1
		return mini


class Solution:

	def minTime(self, s1, s2, N):
		if s2 < s1:
			(s1, s2) = (s2, s1)
		mc = s2 * N

		def getCost(ind):
			return max(s1 * ind, (N - ind) * s2)
		left = 0
		right = N
		while left <= right:
			mid = (left + right) // 2
			mc = min(mc, getCost(mid))
			if mid * s1 > (N - mid) * s2:
				right = mid - 1
			else:
				left = mid + 1
		return mc


class Solution:

	def minTime(self, S1, S2, N):
		if S1 > S2:
			(S1, S2) = (S2, S1)
		low = 0
		high = N - 1
		Min = min(S1, S2) * N
		while low <= high:
			mid = (low + high) // 2
			Min = min(Min, max(S1 * mid, S2 * (N - mid)))
			if S1 * mid <= S2 * (N - mid):
				low = mid + 1
			else:
				high = mid - 1
		return Min


class Solution:

	def minTime(self, S1, S2, N):
		n = N // 2
		time = []
		if N % 2 == 0:
			for i in range(n + 1):
				if S1 >= S2:
					t1 = S1 * (n - i)
					t2 = S2 * (n + i)
					if t1 >= t2:
						time.append(t1)
					else:
						time.append(t2)
					if time[i] <= time[0]:
						time[0] = time[i]
					else:
						break
				else:
					t1 = S1 * (n + i)
					t2 = S2 * (n - i)
					if t1 >= t2:
						time.append(t1)
					else:
						time.append(t2)
					if time[i] <= time[0]:
						time[0] = time[i]
					else:
						break
			return time[0]
		else:
			for i in range(n + 1):
				if S1 >= S2:
					t1 = S1 * (n - i)
					t2 = S2 * (n + 1 + i)
					if t1 >= t2:
						time.append(t1)
					else:
						time.append(t2)
					if time[i] <= time[0]:
						time[0] = time[i]
					else:
						break
				else:
					t1 = S1 * (n + 1 + i)
					t2 = S2 * (n - i)
					if t1 >= t2:
						time.append(t1)
					else:
						time.append(t2)
					if time[i] <= time[0]:
						time[0] = time[i]
					else:
						break
			return time[0]


class Solution:

	def minTime(self, S1, S2, N):
		(i, j, prev, t) = (0, N, float('inf'), 0)
		while i <= j:
			mid = (i + j) // 2
			mn = min(S1, S2) * mid
			mx = max(S1, S2) * (N - mid)
			if mx > mn:
				i = mid + 1
				t = mx
			else:
				j = mid - 1
				t = mn
			if prev > t:
				prev = t
		return min(prev, t)


class Solution:

	def ispossible(self, t):
		if t // self.S1 + t // self.S2 >= N:
			return True

	def minTime(self, S1, S2, N):
		(self.S1, self.S2) = (S1, S2)
		left = 0
		right = N * min(S1, S2)
		ret = right
		while left <= right:
			mid = (left + right) // 2
			if self.ispossible(mid):
				ret = mid
				right = mid - 1
			else:
				left = mid + 1
		return ret


class Solution:

	def minTime(self, S1, S2, N):
		if S1 == S2:
			temp = N // 2
			if N % 2 == 1:
				temp += 1
			return temp * S1
		if S1 * N <= S2 or S2 * N <= S1:
			minS = min(S1, S2)
			return minS * N
		low = 0
		high = N
		minTime = 1000000001
		while low <= high:
			mid = low + (high - low) // 2
			minTime = min(minTime, max(S1 * mid, S2 * (N - mid)))
			if S1 * mid <= S2 * (N - mid):
				low = mid + 1
			else:
				high = mid - 1
		return minTime


def docs(S1, S2, t):
	doc = t // S1 + t // S2
	return doc

class Solution:

	def minTime(self, S1, S2, N):
		L = 1
		R = max(S1, S2) * N
		while L < R:
			M = L + (R - L) // 2
			doc = docs(S1, S2, M)
			if doc < N:
				L = M + 1
			else:
				R = M
		return R


class Solution:

	def minTime(self, s1, s2, n):
		(a, b) = (s1, s2)
		if a > b:
			(a, b) = (b, a)
		(l, h) = (0, n)
		mid = 0
		mini = b * n
		while l <= h:
			mid = (l + h) // 2
			mini = min(mini, max(mid * a, (n - mid) * b))
			if mid * a <= (n - mid) * b:
				l = mid + 1
			else:
				h = mid - 1
		return mini


class Solution:

	def minTime(self, S1, S2, N):
		l = 0
		res = r = max(S1, S2) * N
		while l <= r:
			mid = l + (r - l) // 2
			if mid // S1 + mid // S2 >= N:
				res = mid
				r = mid - 1
			else:
				l = mid + 1
		return res


class Solution:

	def minTime(self, S1, S2, m):
		maxm = max(S1, S2)
		high = m * maxm
		low = 1
		while high > low:
			mid = (high + low) // 2
			ans = mid // S1 + mid // S2
			if ans < m:
				low = mid + 1
			else:
				high = mid
		return high


class Solution:

	def minTime(self, S1, S2, N):
		l = min(S1, S2)
		r = l * N
		while l < r:
			mid = (l + r) // 2
			pageMid = mid // S1 + mid // S2
			if pageMid < N:
				l = mid + 1
			else:
				r = mid
		return r


class Solution:

	def minTime(self, S1, S2, m):

		def findItems(arr, n, temp):
			ans = 0
			for i in range(n):
				ans += temp // arr[i]
			return ans

		def bs(arr, n, m, high):
			low = 1
			while low < high:
				mid = low + high >> 1
				itm = findItems(arr, n, mid)
				if itm < m:
					low = mid + 1
				else:
					high = mid
			return high
		arr = [S1, S2]
		n = len(arr)
		maxval = max(S1, S2)
		return bs(arr, n, m, maxval * m)


class Solution:

	def minTime(self, SSSS1, SSSS2, N):
		s1 = SSSS1
		s2 = SSSS2
		if s1 > s2:
			t = s2
			s2 = s1
			s1 = t
		t1 = s1 * N
		t2 = s2 * N
		mini = min(t1, t2)
		t2 = 0
		for i in range(N // 2):
			t1 = t1 - s1
			t2 = t2 + s2
			t = max(t1, t2)
			if t < mini:
				mini = t
			else:
				break
		return mini


class Solution:

	def minTime(self, S1, S2, N):
		f = 0
		r = N
		if S1 > S2:
			(S1, S2) = (S2, S1)
		min1 = S1 * N
		while f <= r:
			i = (f + r) // 2
			min1 = min(min1, max(i * S1, (N - i) * S2))
			if i * S1 > (N - i) * S2:
				r = i - 1
			else:
				f = i + 1
		return min1


class Solution:

	def minTime(self, S1, S2, N):
		if S1 > S2:
			a = S2
			b = S1
		else:
			(a, b) = (S1, S2)
		start = 0
		last = N
		mt = max(S1 * N, S2 * N)
		while start <= last:
			mid = start + last >> 1
			mt = min(mt, max(mid * a, (N - mid) * b))
			if mid * a > (N - mid) * b:
				last = mid - 1
			else:
				start = mid + 1
		return mt


class Solution:

	def hcfCount(self, x, y):
		if x > y:
			smaller = y
		else:
			smaller = x
		for i in range(1, smaller + 1):
			if x % i == 0 and y % i == 0:
				hcf = i
		return hcf

	def min(self, x1, x2):
		if x1 < x2:
			return True
		return False

	def max(self, x1, x2):
		if x1 > x2:
			return x1
		return x2

	def handleRem(self, x1, x2, rem):
		n1 = 0
		n2 = 0
		while n1 + n2 < rem:
			if self.min((n1 + 1) * x1, (n2 + 1) * x2):
				n1 += 1
			else:
				n2 += 1
		return self.max(x1 * n1, x2 * n2)

	def minTime(self, S1, S2, N):
		hcf = self.hcfCount(S1, S2)
		sum = (S1 + S2) // hcf
		small = S1
		big = S2
		if S2 < S1:
			small = S2
			big = S1
		rem = N % sum
		return S1 * S2 // hcf * (N // sum) + self.handleRem(S1, S2, rem)


class Solution:

	def minTimeLinear(self, S1, S2, N):
		total_time = 0
		s1_time = 0
		s2_time = 0
		for i in range(N):
			new_s1 = s1_time + S1
			new_s2 = s2_time + S2
			if new_s1 < new_s2:
				s1_time = new_s1
				total_time = s1_time
			else:
				s2_time = new_s2
				total_time = s2_time
		return total_time

	def minTime(self, S1, S2, N):
		total_time = 0
		s1_time = 0
		s2_time = 0
		left = min(S1, S2)
		right = max(S1, S2) * N
		while left < right:
			mid = left + (right - left) // 2
			num_docs = mid // S1 + mid // S2
			if num_docs >= N:
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def minTime(self, S1, S2, N):
		a = min(S1, S2)
		b = max(S1, S2)
		l = 0
		h = N
		m = 0
		mi = b * N
		while l <= h:
			m = (l + h) // 2
			mi = min(mi, max(m * a, (N - m) * b))
			if m * a <= (N - m) * b:
				l = m + 1
			else:
				h = m - 1
		return mi


class Solution:

	def item(self, S1, S2, n):
		return n // S1 + n // S2

	def minTime(self, S1, S2, N):
		temp = max(S1, S2)
		low = 1
		high = temp * N
		while low < high:
			mid = low + (high - low) // 2
			it = self.item(S1, S2, mid)
			if it < N:
				low = mid + 1
			else:
				high = mid
		return high


import math

class Solution:

	def minTime(self, S1, S2, goal):
		workers = [S1, S2]
		workers = sorted(workers)
		min_day = math.ceil(goal / 2) * workers[0]
		max_day = math.ceil(goal / 2) * workers[-1]
		while min_day < max_day:
			day = (max_day + min_day) // 2
			day_sum = sum((day // m for m in workers))
			if day_sum >= goal:
				max_day = day
			else:
				min_day = day + 1
		return min_day


class Solution:

	def minTime(self, S1, S2, N):
		low = 0
		high = min(S1, S2) * N
		res = -1
		while low <= high:
			mid = low + (high - low) // 2
			if self.isvalid(S1, S2, mid, N):
				res = mid
				high = mid - 1
			else:
				low = mid + 1
		return res

	def isvalid(self, S1, S2, limit, N):
		stud1 = limit // S1
		stud2 = limit // S2
		if stud1 + stud2 >= N:
			return True
		else:
			return False


import math

class Solution:

	def minTime(self, S1, S2, N):
		N1 = N * S2 / (S1 + S2)
		if N1 == int(N1):
			return int(N * S1 * S2 / (S1 + S2))
		Nfloor = max(math.floor(N1) * S1, (N - math.floor(N1)) * S2)
		Nceil = max(math.ceil(N1) * S1, (N - math.ceil(N1)) * S2)
		return int(min(Nfloor, Nceil))


class Solution:

	def minTime(self, s1, s2, n):
		t1 = min(s1, s2)
		t2 = max(s1, s2)
		mtime = t1 * n
		(low, high) = (0, mtime)
		while low <= high:
			mid = (low + high) // 2
			if mid == low:
				return mtime
			ns1 = mid // t1
			ns2 = mid // t2
			if ns1 + ns2 >= n:
				high = mid
				mtime = min(mtime, mid)
			if ns1 + ns2 < n:
				low = mid
		return mtime


class Solution:

	def minTime(self, S1, S2, N):
		hi = N
		lo = 0
		while abs(hi - lo) > 1:
			mid = (hi + lo) // 2
			a = S1 * mid
			b = S2 * (N - mid)
			if a > b:
				hi = mid
			elif a == b:
				return a
			else:
				lo = mid
		mid = (hi + lo) // 2
		a = S1 * mid
		b = S2 * (N - mid)
		ans1 = max(a, b)
		mid = (hi + lo) // 2 + 1
		a = S1 * mid
		b = S2 * (N - mid)
		ans2 = max(a, b)
		return min(ans1, ans2)


class Solution:

	def minTime(self, S1, S2, N):
		if S1 < S2:
			(S1, S2) = (S2, S1)
		lo = 0
		hi = N
		time = S2 * N
		while lo <= hi:
			mid = (lo + hi) // 2
			time = min(time, max(S1 * mid, (N - mid) * S2))
			if S1 * mid < S2 * (N - mid):
				lo = mid + 1
			else:
				hi = mid - 1
		return time