You are given two arrays $a$ and $b$ of positive integers, with length $n$ and $m$ respectively. 

Let $c$ be an $n \times m$ matrix, where $c_{i,j} = a_i \cdot b_j$. 

You need to find a subrectangle of the matrix $c$ such that the sum of its elements is at most $x$, and its area (the total number of elements) is the largest possible.

Formally, you need to find the largest number $s$ such that it is possible to choose integers $x_1, x_2, y_1, y_2$ subject to $1 \leq x_1 \leq x_2 \leq n$, $1 \leq y_1 \leq y_2 \leq m$, $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1) = s$, and $$\sum_{i=x_1}^{x_2}{\sum_{j=y_1}^{y_2}{c_{i,j}}} \leq x.$$


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 2000$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 2000$).

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($1 \leq b_i \leq 2000$).

The fourth line contains a single integer $x$ ($1 \leq x \leq 2 \cdot 10^{9}$).


-----Output-----

If it is possible to choose four integers $x_1, x_2, y_1, y_2$ such that $1 \leq x_1 \leq x_2 \leq n$, $1 \leq y_1 \leq y_2 \leq m$, and $\sum_{i=x_1}^{x_2}{\sum_{j=y_1}^{y_2}{c_{i,j}}} \leq x$, output the largest value of $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$ among all such quadruplets, otherwise output $0$.


-----Examples-----
Input
3 3
1 2 3
1 2 3
9

Output
4

Input
5 1
5 4 2 4 5
2
5

Output
1



-----Note-----

Matrix from the first sample and the chosen subrectangle (of blue color):

 [Image] 

Matrix from the second sample and the chosen subrectangle (of blue color):

 $\left. \begin{array}{l l l l l}{10} & {8} & {4} & {8} & {10} \end{array} \right.$

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Sorting

Amortized analysis

Implementation


Solutions:
(m, n) = list(map(int, input().split()))
M = list(map(int, input().split()))
N = list(map(int, input().split()))
bound = int(input())
res = 0
if m > n:
	(m, n) = (n, m)
	(M, N) = (N, M)
multis = []
for L in range(1, m + 1):
	cur = sum((M[i] for i in range(L)))
	mini = cur
	for i in range(L, m):
		cur += M[i] - M[i - L]
		mini = min(mini, cur)
	multis.append(mini)
for (i, multi) in enumerate(multis):
	cur_sum = 0
	cur_l = 0
	for j in range(n):
		cur_sum += N[j]
		cur_l += 1
		while cur_sum * multi > bound:
			cur_l -= 1
			cur_sum -= N[j - cur_l]
		res = max(res, (i + 1) * cur_l)
print(res)


from itertools import accumulate
from sys import stdout
R = lambda : map(int, input().split())
(n, m) = R()
(a, b) = (list(accumulate(R())), list(R()))
x = int(input())
res = 0
for al in range(1, n + 1):
	sa = min((ar - al for (ar, al) in zip(a[al - 1:], [0] + a[:])))
	(l, s) = (-1, 0)
	for r in range(m):
		s += b[r] * sa
		while s > x:
			l += 1
			s -= b[l] * sa
		res = max(res, al * (r - l))
print(res)


from sys import stdin, stdout
(N, M) = [int(x) for x in stdin.readline().split()]
arrA = [int(x) for x in stdin.readline().split()]
arrB = [int(x) for x in stdin.readline().split()]
K = int(input())
A = [0] * N
B = [0] * M
prefix_A = [0] * N
s = 0
for i in range(N):
	s += arrA[i]
	prefix_A[i] = s
prefix_B = [0] * M
s = 0
for i in range(M):
	s += arrB[i]
	prefix_B[i] = s
A[0] = min(arrA)
B[0] = min(arrB)
for i in range(1, N):
	m = prefix_A[i]
	for j in range(i + 1, N):
		m = min(m, prefix_A[j] - prefix_A[j - i - 1])
	A[i] = m
for i in range(1, M):
	m = prefix_B[i]
	for j in range(i + 1, M):
		m = min(m, prefix_B[j] - prefix_B[j - i - 1])
	B[i] = m
res = 0
for i in range(N):
	for j in range(M):
		d = A[i] * B[j]
		if d <= K:
			res = max(res, (i + 1) * (j + 1))
print(res)


import bisect
(n, m) = map(int, input().split())
L1 = list(map(int, input().split()))
L2 = list(map(int, input().split()))
x = int(input())
newL1 = [0]
newL2 = [0]
for i in L1:
	newL1.append(newL1[-1] + i)
for i in L2:
	newL2.append(newL2[-1] + i)
min1 = []
min2 = []
mx = 9999999999999999999
for i in range(1, n + 1):
	m1 = mx
	for j in range(n - i + 1):
		if newL1[j + i] - newL1[j] < m1:
			m1 = newL1[j + i] - newL1[j]
	min1.append(m1)
for i in range(1, m + 1):
	m2 = mx
	for j in range(m - i + 1):
		if newL2[j + i] - newL2[j] < m2:
			m2 = newL2[j + i] - newL2[j]
	min2.append(m2)
area = 0
for i in range(n):
	k = x // min1[i]
	for j in range(m):
		if min2[j] > k:
			break
	if min2[-1] <= k:
		j += 1
	if area < j * (i + 1):
		area = j * (i + 1)
print(area)


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = int(input())
rows = [float('inf')] * (n + 1)
cols = [float('inf')] * (m + 1)
for i in range(n):
	summ = 0
	for j in range(i, n):
		summ += a[j]
		l = j - i + 1
		rows[l] = min(rows[l], summ)
for i in range(m):
	summ = 0
	for j in range(i, m):
		summ += b[j]
		l = j - i + 1
		cols[l] = min(cols[l], summ)
ans = 0
for i in range(1, n + 1):
	for j in range(1, m + 1):
		cur = rows[i] * cols[j]
		if cur <= x:
			ans = max(ans, i * j)
print(ans)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = int(input())
sum_a = [0] * (n + 1)
sum_b = [0] * (m + 1)
add_a = 0
add_b = 0
for i in range(1, n + 1):
	add_a += a[i - 1]
	sum_a[i] = add_a
for i in range(1, m + 1):
	add_b += b[i - 1]
	sum_b[i] = add_b
collect_a = [99999999999] * (n + 1)
collect_b = [99999999999] * (m + 1)
for i in range(1, n + 1):
	for j in range(i, n + 1):
		collect_a[j - i + 1] = min(collect_a[j - i + 1], sum_a[j] - sum_a[i - 1])
for i in range(1, m + 1):
	for j in range(i, m + 1):
		collect_b[j - i + 1] = min(collect_b[j - i + 1], sum_b[j] - sum_b[i - 1])
ans = 0
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if collect_a[i] * collect_b[j] <= x:
			ans = max(ans, i * j)
print(ans)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = int(input())

def calc(arr):
	k = len(arr)
	ret = [10 ** 10 for i in range(k + 1)]
	for l in range(0, k):
		cur = 0
		for r in range(l, k):
			cur += arr[r]
			ret[r - l + 1] = min(ret[r - l + 1], cur)
	return ret
bestA = calc(a)
bestB = calc(b)
ans = 0
for a in range(1, n + 1):
	for b in range(1, m + 1):
		if bestA[a] * bestB[b] <= x:
			ans = max(ans, a * b)
		else:
			break
print(ans)


import bisect
(N, M) = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
X = int(input())
leftA = [0] * (N + 1)
leftB = [0] * (M + 1)
for i in range(1, N + 1):
	leftA[i] = leftA[i - 1] + A[i - 1]
for i in range(1, M + 1):
	leftB[i] = leftB[i - 1] + B[i - 1]
avs = [float('inf') for _ in range(N + 1)]
for al in range(N):
	for ar in range(al + 1, N + 1):
		a = leftA[ar] - leftA[al]
		if a > X:
			break
		l = ar - al
		avs[l] = min(avs[l], a)
bvs = [float('inf') for _ in range(M + 1)]
for bl in range(M):
	for br in range(bl + 1, M + 1):
		b = leftB[br] - leftB[bl]
		if b > X:
			break
		l = br - bl
		bvs[l] = min(bvs[l], b)
ans = 0
bvs[0] = 0
for (i, a) in enumerate(avs):
	b = X // a
	j = bisect.bisect_right(bvs, b)
	if j == 0:
		break
	ans = max(ans, i * (j - 1))
print(ans)


import sys
from math import inf

def rint():
	return list(map(int, sys.stdin.readline().split()))
(n, m) = rint()
a = list(rint())
b = list(rint())
x = int(input())
asum = [0]
for i in range(n):
	asum.append(asum[-1] + a[i])
bsum = [0]
for i in range(m):
	bsum.append(bsum[-1] + b[i])
amin = [inf] * (n + 1)
for i in range(n + 1):
	for j in range(i + 1, n + 1):
		partsum = asum[j] - asum[i]
		if amin[j - i] > partsum:
			amin[j - i] = partsum
bmin = [inf] * (m + 1)
for i in range(m + 1):
	for j in range(i + 1, m + 1):
		partsum = bsum[j] - bsum[i]
		if bmin[j - i] > partsum:
			bmin[j - i] = partsum
max_area = 0
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if amin[i] * bmin[j] <= x and i * j > max_area:
			max_area = i * j
print(max_area)


(n, m) = list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
A = [0] * (n + 1)
B = [0] * (m + 1)
x = int(input())
for i in range(1, n + 1):
	a[i] = a[i - 1] + a[i]
	A[i] = a[i]
	for j in range(1, i):
		A[i - j] = min(A[i - j], a[i] - a[j])
for i in range(1, m + 1):
	b[i] = b[i - 1] + b[i]
	B[i] = b[i]
	for j in range(1, i):
		B[i - j] = min(B[i - j], b[i] - b[j])
res = 0
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if A[i] * B[j] <= x:
			res = max(res, i * j)
print(res)


from itertools import accumulate
(n, m) = map(int, input().split(' '))
c = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
a = list(accumulate(c))
x = int(input())
res = 0
for i in range(1, n + 1):
	sa = min((ar - al for (ar, al) in zip(a[i - 1:], [0] + a[:])))
	(l, s) = (-1, 0)
	for r in range(m):
		s += sa * b[r]
		while s > x:
			l += 1
			s -= sa * b[l]
		res = max(res, i * (r - l))
print(res)


import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
x = int(input())
ASUM = [0]
BSUM = [0]
for i in range(n):
	ASUM.append(A[i] + ASUM[-1])
for i in range(m):
	BSUM.append(B[i] + BSUM[-1])
ALIST = dict()
BLIST = dict()
for i in range(n + 1):
	for j in range(i + 1, n + 1):
		if ALIST.get(j - i, 10 ** 15) > ASUM[j] - ASUM[i]:
			ALIST[j - i] = ASUM[j] - ASUM[i]
for i in range(m + 1):
	for j in range(i + 1, m + 1):
		if BLIST.get(j - i, 10 ** 15) > BSUM[j] - BSUM[i]:
			BLIST[j - i] = BSUM[j] - BSUM[i]
ANS = 0
for i in ALIST:
	for j in BLIST:
		if ALIST[i] * BLIST[j] <= x and i * j > ANS:
			ANS = i * j
print(ANS)


[n, m] = list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
x = int(input())
for i in range(1, n + 1):
	a[i] += a[i - 1]
for i in range(1, m + 1):
	b[i] += b[i - 1]
INF = 4 * 10 ** 9 + 1
A = [INF] * (n + 1)
B = [INF] * (m + 1)
for i in range(1, n + 1):
	for j in range(1, i + 1):
		A[i - j + 1] = min(A[i - j + 1], a[i] - a[j - 1])
for i in range(1, m + 1):
	for j in range(1, i + 1):
		B[i - j + 1] = min(B[i - j + 1], b[i] - b[j - 1])
answ = 0
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if A[i] * B[j] <= x:
			answ = max(answ, i * j)
print(answ)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l1 = list(map(int, input().split()))
x = int(input())
l = [0] + l
l1 = [0] + l1
for i in range(1, n + 1):
	l[i] += l[i - 1]
for j in range(1, m + 1):
	l1[j] += l1[j - 1]
maxsum = [999999999999999999] * n
for i in range(1, n + 1):
	for j in range(i, n + 1):
		sum = l[j] - l[j - i]
		maxsum[i - 1] = min(maxsum[i - 1], sum)
maxsum1 = [999999999999999999] * m
for i in range(1, m + 1):
	for j in range(i, m + 1):
		sum = l1[j] - l1[j - i]
		maxsum1[i - 1] = min(maxsum1[i - 1], sum)
ans = 0
for i in range(n):
	for j in range(m - 1, -1, -1):
		if maxsum[i] * maxsum1[j] <= x:
			ans = max(ans, (i + 1) * (j + 1))
print(ans)


(n, m) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
suma = list()
suma.append(0)
for i in range(len(a)):
	suma.append(a[i] + suma[i])
sumb = list()
sumb.append(0)
for i in range(len(b)):
	sumb.append(b[i] + sumb[i])
mina = list()
mina.append(0)
minb = list()
minb.append(0)
maxnum = 3000 * 3000
for tmplen in range(1, n + 1):
	mina.append(maxnum)
	for loc in range(n):
		if loc + tmplen > n:
			break
		else:
			mina[tmplen] = min(mina[tmplen], suma[loc + tmplen] - suma[loc])
for tmplen in range(1, m + 1):
	minb.append(maxnum)
	for loc in range(m):
		if loc + tmplen > m:
			break
		else:
			minb[tmplen] = min(minb[tmplen], sumb[tmplen + loc] - sumb[loc])
x = int(input())
ans = 0
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if mina[i] * minb[j] <= x:
			ans = max(ans, i * j)
print(ans)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = int(input())
gooda = [10000000] * n
goodb = [10000000] * m
for i in range(n):
	tots = 0
	lent = 0
	for j in range(i, n):
		tots += a[j]
		lent += 1
		gooda[lent - 1] = min(gooda[lent - 1], tots)
for i in range(m):
	tots = 0
	lent = 0
	for j in range(i, m):
		tots += b[j]
		lent += 1
		goodb[lent - 1] = min(goodb[lent - 1], tots)
best = 0
aind = 0
bind = m - 1
while aind < n and bind >= 0:
	if gooda[aind] * goodb[bind] <= x:
		best = max(best, (aind + 1) * (bind + 1))
		aind += 1
	else:
		bind -= 1
print(best)


def get_input_list():
	return list(map(int, input().split()))
(n, m) = get_input_list()
a = get_input_list()
b = get_input_list()
x = int(input())
sa = [0]
for i in range(1, n + 1):
	s = sum(a[:i])
	mi = s
	j = i
	while j < n:
		s = s - a[j - i] + a[j]
		if mi > s:
			mi = s
		j += 1
	sa.append(mi)
sb = [0]
for i in range(1, m + 1):
	s = sum(b[:i])
	mi = s
	j = i
	while j < m:
		s = s - b[j - i] + b[j]
		if mi > s:
			mi = s
		j += 1
	sb.append(mi)
r = 0
for i in range(n + 1):
	for j in range(m + 1):
		if sa[i] * sb[j] <= x:
			if i * j > r:
				r = i * j
print(r)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = int(input())
b_acc = [0]
for bi in b:
	b_acc.append(b_acc[-1] + bi)
max_length = [0] * (4 * 10 ** 6 + 100)
for i in range(m):
	for j in range(i, m):
		B = b_acc[j + 1] - b_acc[i]
		max_length[B] = max(max_length[B], j - i + 1)
for i in range(1, 4 * 10 ** 6 + 100):
	max_length[i] = max(max_length[i], max_length[i - 1])
a_acc = [0]
for ai in a:
	a_acc.append(a_acc[-1] + ai)
ans = 0
sb = sum(b)
for i in range(n):
	for j in range(i, n):
		A = a_acc[j + 1] - a_acc[i]
		B = x // A
		if B >= sb:
			ans = max(ans, (j - i + 1) * m)
		else:
			ans = max(ans, (j - i + 1) * max_length[B])
print(ans)


from bisect import bisect_left
(n, m) = map(int, input().split())
arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))
threshold = int(input())
arr1map = dict()
arr2map = dict()
for idx in range(len(arr1)):
	sm = 0
	for jdx in range(idx, len(arr1)):
		sm += arr1[jdx]
		if sm not in arr1map or arr1map[sm][1] - arr1map[sm][0] < jdx - idx:
			arr1map[sm] = (idx, jdx)
for idx in range(len(arr2)):
	sm = 0
	for jdx in range(idx, len(arr2)):
		sm += arr2[jdx]
		if sm not in arr2map or arr2map[sm][1] - arr2map[sm][0] < jdx - idx:
			arr2map[sm] = (idx, jdx)
arr1keys = list(sorted(arr1map))
arr2keys = list(sorted(arr2map))
ans = 0
for v in arr1keys:
	lookup = threshold // v
	idx = bisect_left(arr2keys, lookup)
	if idx == len(arr2keys):
		x1 = arr1map[v][1] - arr1map[v][0] + 1
		x2 = arr2map[arr2keys[idx - 1]][1] - arr2map[arr2keys[idx - 1]][0] + 1
		ans = max(ans, x1 * x2)
	elif arr2keys[idx] <= lookup:
		x1 = arr1map[v][1] - arr1map[v][0] + 1
		x2 = arr2map[arr2keys[idx]][1] - arr2map[arr2keys[idx]][0] + 1
		ans = max(ans, x1 * x2)
	else:
		idx -= 1
		if idx >= 0:
			x1 = arr1map[v][1] - arr1map[v][0] + 1
			x2 = arr2map[arr2keys[idx]][1] - arr2map[arr2keys[idx]][0] + 1
			ans = max(ans, x1 * x2)
for v in arr2keys:
	lookup = threshold // v
	idx = bisect_left(arr1keys, lookup)
	if idx == len(arr1keys):
		x1 = arr2map[v][1] - arr2map[v][0] + 1
		x2 = arr1map[arr1keys[idx - 1]][1] - arr1map[arr1keys[idx - 1]][0] + 1
		ans = max(ans, x1 * x2)
	elif arr1keys[idx] <= lookup:
		x1 = arr2map[v][1] - arr2map[v][0] + 1
		x2 = arr1map[arr1keys[idx]][1] - arr1map[arr1keys[idx]][0] + 1
		ans = max(ans, x1 * x2)
	else:
		idx -= 1
		if idx >= 0:
			x1 = arr2map[v][1] - arr2map[v][0] + 1
			x2 = arr1map[arr1keys[idx]][1] - arr1map[arr1keys[idx]][0] + 1
			ans = max(ans, x1 * x2)
print(ans)


(n, m) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
x = int(input())
csa = [0] * (n + 1)
csb = [0] * (m + 1)
ans = 0
for i in range(1, n + 1):
	csa[i] = csa[i - 1] + a[i - 1]
for i in range(1, m + 1):
	csb[i] = csb[i - 1] + b[i - 1]
misubsa = [9999999999999] * (n + 1)
misubsb = [9999999999999] * (m + 1)
for i in range(1, n + 1):
	for j in range(i, n + 1):
		misubsa[j - i + 1] = min(misubsa[j - i + 1], csa[j] - csa[i - 1])
for i in range(1, m + 1):
	for j in range(i, m + 1):
		misubsb[j - i + 1] = min(misubsb[j - i + 1], csb[j] - csb[i - 1])
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if misubsa[i] * misubsb[j] <= x:
			ans = max(ans, i * j)
print(ans)


from sys import stdin, stdout
(n, m) = stdin.readline().strip().split(' ')
(n, m) = (int(n), int(m))
row = list(map(int, stdin.readline().strip().split(' ')))
col = list(map(int, stdin.readline().strip().split(' ')))
x = int(stdin.readline().strip())
lowest_row_array = [0]
for i in range(1, n + 1):
	s = sum(row[:i])
	j = i
	min_till_now = s
	while j < n:
		s = s - row[j - i] + row[j]
		if s < min_till_now:
			min_till_now = s
		j += 1
	lowest_row_array.append(min_till_now)
lowest_col_array = [0]
for i in range(1, m + 1):
	s = sum(col[:i])
	j = i
	min_till_now = s
	while j < m:
		s = s - col[j - i] + col[j]
		if s < min_till_now:
			min_till_now = s
		j += 1
	lowest_col_array.append(min_till_now)
max_size = 0
if len(lowest_col_array) == 1:
	lowest_col_array[0] = 1
if len(lowest_row_array) == 1:
	lowest_row_array[0] = 1
for i in range(len(lowest_row_array)):
	for j in range(len(lowest_col_array)):
		if lowest_row_array[i] * lowest_col_array[j] <= x:
			if i * j > max_size:
				max_size = i * j
print(max_size)


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
e = int(input())
c = [0] * (n + 1)
x = [0]
x1 = 0
for i in range(n):
	x1 += a[i]
	x.append(x1)
y = [0]
y1 = 0
for i in range(m):
	y1 += b[i]
	y.append(y1)
for i in range(1, n + 1):
	d = x[i]
	for j in range(n - i + 1):
		if x[j + i] - x[j] < d:
			d = x[j + i] - x[j]
	c[i] = d
s = 0
for i in range(m):
	for j in range(i, m):
		(l, r) = (0, n)
		while r - l > 1:
			m1 = (l + r) // 2
			if c[m1] * (y[j + 1] - y[i]) >= e:
				r = m1
			else:
				l = m1
		while r > 0 and c[r] * (y[j + 1] - y[i]) > e:
			r -= 1
		s = max(s, r * (j - i + 1))
print(s)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = int(input())
mina = []
base = 0
prev = 0
for i in range(1, n + 1):
	base = a[i - 1] + prev
	min1 = base
	prev = base
	for j in range(i, n):
		base -= a[j - i]
		base += a[j]
		min1 = min(min1, base)
	mina.append(min1)
minb = []
base = 0
prev = 0
for i in range(1, m + 1):
	base = prev + b[i - 1]
	min1 = base
	prev = base
	for j in range(i, m):
		base -= b[j - i]
		base += b[j]
		min1 = min(min1, base)
	minb.append(min1)
area = 0
for i in range(n):
	for j in range(m):
		if mina[i] * minb[j] <= x:
			area = max(area, (i + 1) * (j + 1))
print(area)


(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
c = [0] * (n + 1)
d = [0] * (m + 1)
x = int(input())
for i in range(1, n + 1):
	a[i] = a[i - 1] + a[i]
	c[i] = a[i]
	for j in range(1, i):
		c[i - j] = min(c[i - j], a[i] - a[j])
for i in range(1, m + 1):
	b[i] = b[i - 1] + b[i]
	d[i] = b[i]
	for j in range(1, i):
		d[i - j] = min(d[i - j], b[i] - b[j])
ans = 0
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if c[i] * d[j] <= x:
			ans = max(ans, i * j)
print(ans)


(n, m) = [int(i) for i in input().split(' ')]
a = [int(x) for x in input().split(' ')]
b = [int(x) for x in input().split(' ')]
x = int(input())
max_a = {}
for i in range(n):
	cur_sum = 0
	for j in range(i, n):
		cur_sum += a[j]
		if j - i + 1 not in max_a or cur_sum < max_a[j - i + 1]:
			max_a[j - i + 1] = cur_sum
max_b = {}
for i in range(m):
	cur_sum = 0
	for j in range(i, m):
		cur_sum += b[j]
		if j - i + 1 not in max_b or cur_sum < max_b[j - i + 1]:
			max_b[j - i + 1] = cur_sum
best_area = 0
for i in max_a:
	for j in max_b:
		cur_sum = max_a[i] * max_b[j]
		cur_area = i * j
		if cur_sum <= x:
			best_area = max(best_area, cur_area)
print(best_area)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(N, M) = [int(x) for x in input().split()]
arrA = [int(x) for x in input().split()]
arrB = [int(x) for x in input().split()]
K = int(input())
A = [0] * N
B = [0] * M
prefix_A = [0] * N
s = 0
for i in range(N):
	s += arrA[i]
	prefix_A[i] = s
prefix_B = [0] * M
s = 0
for i in range(M):
	s += arrB[i]
	prefix_B[i] = s
A[0] = min(arrA)
B[0] = min(arrB)
for i in range(1, N):
	m = prefix_A[i]
	for j in range(i + 1, N):
		m = min(m, prefix_A[j] - prefix_A[j - i - 1])
	A[i] = m
for i in range(1, M):
	m = prefix_B[i]
	for j in range(i + 1, M):
		m = min(m, prefix_B[j] - prefix_B[j - i - 1])
	B[i] = m
res = 0
for i in range(N):
	for j in range(M):
		d = A[i] * B[j]
		if d <= K:
			res = max(res, (i + 1) * (j + 1))
print(res)


(n, m) = map(int, input().split())
a = [0] * (n + 1)
j = 1
b = [0]
for i in input().split():
	a[j] += int(i) + a[j - 1]
	j += 1
b.extend(list(map(int, input().split())))
b.append(0)
x = int(input())
ans = 0
for i in range(1, n + 1):
	k1 = 10 ** 9
	for j in range(0, n - i + 1):
		k1 = min(k1, a[j + i] - a[j])
	l = r = 1
	k2 = b[1]
	while r <= m:
		if k1 * k2 <= x:
			ans = max(ans, i * (r - l + 1))
			r += 1
			k2 += b[r]
		else:
			k2 -= b[l]
			l += 1
print(ans)


from math import *
import re
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = int(input())
ms = [10 ** 18] * (n + 1)
for i in range(n):
	s = 0
	for j in range(i, n):
		s += a[j]
		ms[j - i + 1] = min(ms[j - i + 1], s)
ans = 0
for i in range(1, n + 1):
	r = 0
	s = 0
	for l in range(m):
		while r < m and ms[i] * (s + b[r]) <= x:
			s += b[r]
			r += 1
		ans = max(ans, i * (r - l))
		s -= b[l]
print(ans)


import sys
input = sys.stdin.readline
from itertools import permutations
from math import *
from bisect import *
(n, m) = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
x = int(input())
d = []
p = {}
for i in range(n):
	c = 0
	for j in range(i, n):
		c += a[j]
		if j - i + 1 not in p:
			p[j - i + 1] = c
		else:
			p[j - i + 1] = min(p[j - i + 1], c)
g = [0 for i in range(n)]
for i in p:
	g[i - 1] = p[i]
maxi = 0
d = []
p = {}
h = [0 for i in range(m)]
for i in range(m):
	c = 0
	for j in range(i, m):
		c += b[j]
		if j - i + 1 not in p:
			p[j - i + 1] = c
		else:
			p[j - i + 1] = min(p[j - i + 1], c)
for i in range(len(d)):
	if d[i][1] not in p:
		p[d[i][1]] = d[i][0]
	else:
		p[d[i][1]] = min(p[d[i][1]], d[i][0])
for i in p:
	h[i - 1] = p[i]
for i in range(m):
	if h[i] > x:
		continue
	r = bisect_right(g, x // h[i])
	maxi = max(maxi, (i + 1) * r)
print(maxi)