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.$

Difficulty: competition

Starter code:

Solutions:
import bisect
n,m=list(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)


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)
        




#!/usr/bin/env python3
import sys
from math import inf

def rint():
    return list(map(int, sys.stdin.readline().split()))
#lines = stdin.readlines()

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)


import bisect
n,m=list(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=99999999999999

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)
ot=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 ot<j*(i+1):
        ot=j*(i+1)
print(ot)
        






n,m=list(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
    #print(base,i)
    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
#print(mina,minb)
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)



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)




# help from rols

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)



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 bisect import bisect_left

n, m = list(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)


# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 11/20/18

"""
import bisect

N, M = list(map(int, input().split()))
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
X = int(input())
#

# import time
# t0 = time.time()
#
# N, M = 2000, 2000
# A = [2000 for _ in range(N)]
# B = [2000 for _ in range(M)]
# X = 2*10**9

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)




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)

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(lowest_col_array)
# print(lowest_row_array)
print(max_size)


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)


# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
from sys import stdin, stdout
 
#N = int(input())
#s = input()
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)


[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);


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)

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)

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)

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)


from itertools import accumulate

n,m=list(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)


n,m=list(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]
#print(l,l1)
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 
#print(maxsum,maxsum1)
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)
        



#yeh dil maange more
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])
#print(c)
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)