There are n squirrel(s) waiting below the feet of m chestnut tree(s). The first chestnut of the i-th tree will fall right after T_{i} second(s), and one more every P_{i} second(s) after that. The “big mama” of squirrels wants them to bring their nest no less than k chestnuts to avoid the big storm coming, as fast as possible! So they are discussing to wait below which trees to take enough chestnuts in the shortest time. Time to move to the positions is zero, and the squirrels move nowhere after that.

------ Request ------ 

Calculate the shortest time (how many seconds more) the squirrels can take enough chestnuts.

------ Input ------ 

The first line contains an integer t, the number of test cases, for each:
The first line contains the integers m,n,k, respectively.
The second line contains the integers T_{i}  (i=1..m), respectively.
The third line contains the integers P_{i}  (i=1..m), respectively.

(Each integer on a same line is separated by at least one space character, there is no added line between test cases)

------ Output ------ 

For each test cases, output in a single line an integer which is the shortest time calculated.

------ Limitations ------ 

0
0
07
0i,P_{i}≤100

----- Sample Input 1 ------ 
2
3 2 5
5 1 2
1 2 1
3 2 5
5 1 2
1 1 1
----- Sample Output 1 ------ 
4
3
----- explanation 1 ------ 
Test case $1$: Two squirrels wait below trees $2$ and $3$.
- After $1$ second, a chestnut from tree $2$ falls. Total chestnuts the squirrels have is $1$.
- After $2$ seconds, a chestnut from tree $3$ falls. Total chestnuts the squirrels have is $2$.
- After $3$ seconds, two chestnuts fall from trees $2$ and $3$. Total chestnuts the squirrels have is $4$.
- After $4$ seconds, a chestnut from tree $3$ falls. Total chestnuts the squirrels have is $5$.

Total time to gather $5$ chestnuts is $5$ seconds.

Test case $2$: Two squirrels wait below trees $2$ and $3$.
- After $1$ second, a chestnut from tree $2$ falls. Total chestnuts the squirrels have is $1$.
- After $2$ seconds, two chestnuts fall from trees $2$ and $3$. Total chestnuts the squirrels have is $3$.
- After $3$ seconds, two chestnuts fall from trees $2$ and $3$. Total chestnuts the squirrels have is $5$.

Total time to gather $5$ chestnuts is $3$ seconds.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Complete search
Skill types: Dynamic programming

Sorting

Complete search

Starter code:

Solutions:
for _ in range(int(input())):
	(m, n, k) = map(int, input().split())
	T = list(map(int, input().split()))
	P = list(map(int, input().split()))
	t_min = 0
	t_max = 10000000
	t_ans = 0
	while t_min <= t_max:
		t_mid = (t_min + t_max) // 2
		fa = [(t_mid - T[i]) // P[i] + 1 for i in range(m) if t_mid >= T[i]]
		fm = sum(sorted(fa, reverse=True)[:n])
		if fm < k:
			t_min = t_mid + 1
		else:
			t_max = t_mid - 1
		if fm >= k:
			t_ans = t_mid
	print(t_ans)


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	(m, n, k) = map(int, input().split())
	t = list(map(int, input().split()))
	p = list(map(int, input().split()))
	lo = 0
	hi = 1000000000
	ans = 0
	while lo <= hi:
		mid = (lo + hi) // 2
		temp = [(mid - t[i]) // p[i] + 1 for i in range(m) if mid >= t[i]]
		temp.sort(reverse=True)
		temp_sum = sum(temp[:n])
		if temp_sum >= k:
			hi = mid - 1
			ans = mid
		else:
			lo = mid + 1
	print(ans)


def BinarySearch():
	left = 0
	right = 10 ** 9 + 101
	res = 0
	while left <= right:
		Sum = [0] * m
		mid = (left + right) // 2
		for i in range(m):
			Sum[i] = max((mid - t[i]) // p[i] + 1, 0)
		Sum.sort(reverse=True)
		x = sum(Sum[0:n])
		if x >= k:
			right = mid - 1
			res = mid
		else:
			left = mid + 1
	return res
a = int(input())
while a != 0:
	a -= 1
	(m, n, k) = map(int, input().split())
	t = list(map(int, input().split()))
	p = list(map(int, input().split()))
	print(BinarySearch())


def soln(m, n, k, t, p):
	low = 0
	res = high = 10 ** 9
	while low <= high:
		time = (low + high) // 2
		cur = []
		for i in range(m):
			cur.append(max((time - t[i]) // p[i] + 1, 0))
		nuts = sum(sorted(cur, reverse=True)[:n])
		if nuts < k:
			low = time + 1
		else:
			high = time - 1
			res = time
	return res
for _ in range(int(input())):
	(m, n, k) = map(int, input().split())
	t = list(map(int, input().split()))
	p = list(map(int, input().split()))
	print(soln(m, n, k, t, p))


for _ in range(int(input())):
	(m, n, k) = map(int, input().split())
	t = list(map(int, input().split()))
	p = list(map(int, input().split()))
	start = 0
	end = 10 ** 9
	res = 0
	while start <= end:
		sum1 = [0] * m
		mid = start + (end - start) // 2
		for i in range(m):
			sum1[i] = max((mid - t[i]) // p[i] + 1, 0)
		sum1.sort(reverse=True)
		val = sum(sum1[:n])
		if val >= k:
			end = mid - 1
			res = mid
		else:
			start = mid + 1
	print(res)


import math

def find_best_count(m, n, k, t_arr, p_arr, t):
	per_tree = [0] * m
	for i in range(m):
		p = p_arr[i]
		ti = t_arr[i]
		if t >= ti:
			count = 1 + (t - ti) // p
			per_tree[i] = count
	per_tree.sort(reverse=True)
	total = sum(per_tree[0:n])
	return total

def solve(m, n, k, t_arr, p_arr):
	ans = 0
	tmin = 0
	tmax = 1000000000
	while tmin <= tmax:
		mid = (tmin + tmax) // 2
		count = find_best_count(m, n, k, t_arr, p_arr, mid)
		if count < k:
			tmin = mid + 1
		else:
			tmax = mid - 1
		if count >= k:
			ans = mid
	return ans
t = int(input())
for r in range(1, t + 1):
	(m, n, k) = list(map(int, input().strip().split(' ')))
	t = list(map(int, input().strip().split(' ')))
	p = list(map(int, input().strip().split(' ')))
	result = solve(m, n, k, t, p)
	print(result)


def sol():
	l = 0
	r = 10 ** 9
	final = 0
	while l <= r:
		mid = (l + r) // 2
		ans = [0] * m
		for i in range(m):
			ans[i] = max(0, (mid - t[i]) // p[i] + 1)
		ans.sort(reverse=True)
		x = sum(ans[0:n])
		if x >= k:
			r = mid - 1
			final = mid
		else:
			l = mid + 1
	print(final)
for i in range(int(input())):
	(m, n, k) = [int(x) for x in input().split()]
	t = [int(x) for x in input().split()]
	p = [int(x) for x in input().split()]
	sol()


def check(t):
	chestnuts = []
	for el in arr:
		chestnuts.append((t - el[0]) // el[1] + 1)
	chestnuts.sort(reverse=True)
	if sum(chestnuts[:n]) >= k:
		return True
	else:
		return False
t = int(input())
for i in range(t):
	(length, n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = [[a[i], b[i]] for i in range(length)]
	r = 1000000000000
	l = 0
	ans = 1000000000000
	while r >= l:
		m = (l + r) // 2
		if check(m):
			r = m - 1
			ans = min(ans, m)
		else:
			l = m + 1
	print(l)


def binary_search():
	l = 0
	r = 10 ** 9 + 101
	res = 0
	while l <= r:
		Sum = [0] * m
		mid = (l + r) // 2
		for i in range(m):
			Sum[i] = max((mid - t[i]) // p[i] + 1, 0)
		Sum.sort(reverse=True)
		x = sum(Sum[0:n])
		if x >= k:
			r = mid - 1
			res = mid
		else:
			l = mid + 1
	return res
for i in range(int(input())):
	(m, n, k) = map(int, input().split())
	t = list(map(int, input().split()))
	p = list(map(int, input().split()))
	print(binary_search())


def compute(t, p, m, mid):
	ans = []
	for i in range(len(t)):
		v = 0
		if t[i] <= mid:
			v = 1 + (mid - t[i]) // p[i]
		ans.append(v)
	ans.sort()
	ans.reverse()
	ans = ans[:m]
	return sum(ans)
t = int(input())
for _ in range(t):
	(m, n, k) = map(int, input().split())
	t = list(map(int, input().split()))
	p = list(map(int, input().split()))
	tm = 2 ** 32 - 1
	for i in range(m):
		tm = min(tm, t[i] + p[i] * (k - 1))
	(st, en) = (0, tm)
	while st < en:
		mid = (st + en) // 2
		curr = compute(t, p, n, mid)
		if curr < k:
			st = mid + 1
		else:
			en = mid
	i = en - 1
	while compute(t, p, n, i) < k:
		i += 1
	print(i)


def geAns(m, n, k, t, p):
	(l, r) = (0, 10 ** 9 + 999)
	ans = 0
	while l <= r:
		md = (l + r) // 2
		v = [0] * m
		for i in range(m):
			v[i] = max(0, (md - t[i]) // p[i] + 1)
		v.sort(reverse=True)
		vl = sum(v[:n])
		if vl >= k:
			r = md - 1
			ans = md
		else:
			l = md + 1
	return ans
tn = int(input())
for _ in range(tn):
	(m, n, k) = map(int, input().split())
	t = list(map(int, input().split()))
	p = list(map(int, input().split()))
	print(geAns(m, n, k, t, p))


def f(time):
	l = [(time - T[i]) // P[i] + 1 for i in range(m) if time >= T[i]]
	return sum(sorted(l, reverse=True)[:n])
t = int(input())
for _ in range(t):
	(m, n, k) = map(int, input().split())
	T = [int(_) for _ in input().split()]
	P = [int(_) for _ in input().split()]
	t_min = 0
	t_max = 10000000
	t_ans = 0
	while t_min <= t_max:
		t_mid = (t_min + t_max) // 2
		fm = f(t_mid)
		if fm < k:
			t_min = t_mid + 1
		else:
			t_max = t_mid - 1
		if fm >= k:
			t_ans = t_mid
	print(t_ans)


for _ in range(int(input())):
	(m, n, k) = map(int, input().split())
	Ti = list(map(int, input().split()))
	Pi = list(map(int, input().split()))
	sm = [0] * m
	(l, r) = (1, 100000.0)
	ans = int()
	while l <= r:
		mid = (l + r) // 2
		for i in range(m):
			sm[i] = max((mid - Ti[i]) // Pi[i] + 1, 0)
		sm.sort(reverse=True)
		if sum(sm[:n]) < k:
			l = mid + 1
		else:
			ans = mid
			r = mid - 1
	print(int(ans))


t = int(input())
for _ in range(t):
	(m, n, k) = map(int, input().split())
	t = [int(item) for item in input().split()]
	p = [int(item) for item in input().split()]
	low = 0
	high = 10 ** 5 + 105
	ans = 0
	while low <= high:
		arr = [0] * m
		mid = low + (high - low) // 2
		for i in range(m):
			if mid < t[i]:
				arr[i] = 0
			arr[i] = 1 + (mid - t[i]) // p[i]
		arr.sort(reverse=True)
		temp = 0
		for i in range(min(m, n)):
			temp += arr[i]
		if temp >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	print(ans)


t = int(input())
for k in range(t):
	(m, n, k) = input().split()
	(m, n, k) = (int(m), int(n), int(k))
	s_t = input().split()
	s_p = input().split()
	arr_t = []
	arr_p = []
	for i in range(m):
		arr_t.append(int(s_t[i]))
		arr_p.append(int(s_p[i]))
	l = 0
	r = arr_t[0] + (k - 1) * arr_p[0]
	mn = r
	while l <= r:
		mid = l + (r - l) // 2
		if mid >= mn:
			r = mid - 1
		else:
			arr = []
			s = 0
			for i in range(m):
				if mid < arr_t[i]:
					arr.append(0)
				else:
					arr.append(1 + (mid - arr_t[i]) // arr_p[i])
				s += arr[i]
			if n >= m:
				if s >= k:
					mn = mid
					r = mid - 1
				else:
					l = mid + 1
				continue
			arr.sort(reverse=True)
			s = 0
			rem = n
			for i in range(m):
				if rem > 0:
					s += arr[i]
					rem -= 1
					if rem == 0:
						break
			if s >= k:
				mn = mid
				r = mid - 1
			else:
				l = mid + 1
	print(mn)


from sys import stdin
for _ in range(int(stdin.readline())):
	(m, n, k) = map(int, stdin.readline().split())
	first = list(map(int, stdin.readline().split()))
	second = list(map(int, stdin.readline().split()))
	time = list(map(list, zip(first, second)))
	low = 1
	high = 10 ** 9
	ans = 10 ** 9
	while low <= high:
		mid = (high + low) // 2
		nuts = []
		for i in time:
			if i[0] > mid:
				nuts.append(0)
			else:
				nuts.append(1 + (mid - i[0]) // i[1])
		nuts.sort(reverse=True)
		get = sum(nuts[:min(n, m)])
		if get >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	print(ans)


def solve(time):
	(s, e) = (1, 10 ** 9)
	ans = 0
	while s <= e:
		mid = (s + e) // 2
		nuts = 0
		temp = []
		for i in range(m):
			if mid - time[i][0] < 0:
				temp.append(0)
				continue
			temp.append(1 + (mid - time[i][0]) // time[i][1])
		temp.sort(reverse=True)
		nuts = sum(temp[:min(n, m)])
		if nuts >= k:
			ans = mid
			e = mid - 1
		else:
			s = mid + 1
	print(ans)
for _ in range(int(input())):
	(m, n, k) = list(map(int, input().split()))
	t = list(map(int, input().split()))
	tp = list(map(int, input().split()))
	time = list(map(list, zip(t, tp)))
	solve(time)