Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

h,w,a,b = map(int, input().split())

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def comb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

ans=0
for i in range(h-a):
    pre=comb(i+b-1,i)
    post=comb(h+w-b-2-i,h-i-1)
    ans+=pre*post
    ans%=10**9+7
print(ans)

### FIXED CODE ###

h,w,a,b = map(int, input().split())
def find_power(n,mod=10**9+7):
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist
def find_inv_power(n):
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist
mod = 10**9+7
p_lis=find_power(4*10**5+100,mod)
ip_lis=find_inv_power(4*10**5+100)

def comb(n,r,mod=10**9+7):
    if n<r:
        return 0
    elif n>=r:
        return (p_lis[n]*ip_lis[r]*ip_lis[n-r])%(mod)
ans=0
for i in range(h-a):
    pre=comb(i+b-1,i)
    post=comb(h+w-b-2-i,h-i-1)
    ans+=pre*post
    ans%=10**9+7
print(ans)
### BUGGY CODE ###

from numba import njit

N = int(input())
S = input()
Q = int(input())
ks = list(map(int, input().split()))

@njit
def solve(N, S, k):
    k -= 1

    # i-th of these counts the thing in [ max(0, i-k), i ).
    D_counts  = [0]
    M_counts  = [0]
    DM_counts = [0]

    D = 0
    M = 0
    DM = 0
    for i in range(k):
        if S[i] == 'D':
            D += 1
        elif S[i] == 'M':
            DM += D
            M += 1
        D_counts.append(D)
        M_counts.append(M)
        DM_counts.append(DM)
    for i in range(k, N):
        if S[i-k] == 'D':
            D -= 1
            DM -= M
        elif S[i-k] == 'M':
            M -= 1

        if S[i] == 'D':
            D += 1
        elif S[i] == 'M':
            DM += D
            M += 1
            
        D_counts.append(D)
        M_counts.append(M)
        DM_counts.append(DM)

    ans = 0
    for i, c in enumerate(S):
        if c == 'C':
            ans += DM_counts[i]
    return ans

for k in ks:
    print(solve(N, S, k))
    

### FIXED CODE ###

import numpy as np
from numba import njit

N = int(input())
S = input()
Q = int(input())
ks = list(map(int, input().split()))

def func(ch):
    if ch == 'D':
        return 1
    if ch == 'M':
        return 2
    if ch == 'C':
        return 3
    return 0
    
S_arr = np.array([func(ch) for ch in S], dtype = np.int32)

@njit("i8(i8, i4[:], i8)", cache = True)
def solve(N, S_arr, k):
    ans = 0
    D = 0
    M = 0
    DM = 0
    for i in range(k):
        if S_arr[i] == 1:
            D += 1
        elif S_arr[i] == 2:
            DM += D
            M += 1
        elif S_arr[i] == 3:
            ans += DM
    for i in range(k, N):
        if S_arr[i-k] == 1:
            D -= 1
            DM -= M
        elif S_arr[i-k] == 2:
            M -= 1

        if S_arr[i] == 1:
            D += 1
        elif S_arr[i] == 2:
            DM += D
            M += 1
        elif S_arr[i] == 3:
            ans += DM

    return ans

for k in ks:
    print(solve(N, S_arr, k))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
res = 1
for i in range(n):
  res = res * a[i]
  if(res > pow(10,18)):
    res = -1
print(res)

### FIXED CODE ###

import sys
n = int(input())
a = list(map(int,input().split()))
if 0 in a:
  res = 0
  print(res)
  sys.exit()
  
res = 1
for i in range(n):
  if(res > pow(10,18)):
    break
  else:
    res = res * a[i]
if(res > pow(10,18)):
   res = -1
print(res)
### BUGGY CODE ###

n, m = map(int, input().split())
for i in range(1, m//n+1)[::-1]:
    if m%i == 0:
        print(i)
        break

### FIXED CODE ###

n, m = map(int, input().split())
r = 1
for i in range(1, int(m**0.5)+1)[::-1]:
    if i<=m//n and m%i==0:
        if m//i<=m//n:
            r = max(r, m//i)
        else:
            r = max(r, i)
print(r)
### BUGGY CODE ###

N=int(input())
di = dict()
for i in range(N):
    s = input()
    if s in di:
        di[s] += 1
    else:
        di[s] = 0

maxlist = [kv for kv in di.items() if kv[1] == max(di.values())]
dic2 = sorted(maxlist)
for d in dic2:
    print(d[0])


### FIXED CODE ###

import collections
import itertools
N=int(input())
di = dict()
l = list()
for i in range(N):
    l.append( input())

c = collections.Counter(l)
ct = c.most_common()
m = ct[0][1]
li = list()
for t in ct:
    if m == t[1]:
        li.append(t[0]) 
    else:
        break
lis = sorted(li)
for s in lis:
    print(s)
### BUGGY CODE ###

from operator import add


class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e # 単位元
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func # 処理(add or xor max minなど)

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        # [l, r) についてqueryを求める
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x


N = int(input())
S = input()
Q = int(input())
*k, = map(int, input().split())

l = [1 if s=="C" else 0 for s in S]
tree = SegTree(N, 0)
tree.set_list(l)

ans = 0

for a in k:
    ans = 0
    for i, s in enumerate(S):
        if s!="M":
            continue
        for j in range(max(i-a, 0), i):
            if S[j]=="D":
                ans += tree.get(i, min(a+j, N))
    print(ans)

### FIXED CODE ###

N = int(input())
S = input()
Q = int(input())
*k, = map(int, input().split())

acd = [0]*(N+1)
acm = [0]*(N+1)
acc = [0]*(N+1)
acmc = [0]*(N+2)

for i in range(1, N+1):
    acd[i] = acd[i-1] + (S[i-1]=="D")
    acm[i] = acm[i-1] + (S[i-1]=="M")
    acc[i] = acc[i-1] + (S[i-1]=="C")

ans = 0
for i in range(1, N+1):
    if S[i-1]=="M":
        ans += acd[i-1]*(acc[N]-acc[i])

for i in range(1, N)[::-1]:
    acmc[i] += acmc[i+1]
    if S[i-1]=="M":
        acmc[i] += acc[N]-acc[i]

for i in k:
    v = 0
    for j in range(1, N+1):
        if S[j-1]=="D":
            v += (acm[min(N, i+j-1)]-acm[j]) * (acc[N]-acc[min(N, i+j-1)]) + acmc[min(i+j, N)]
    print(ans-v)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

A.sort()
A_ = list(set(A))

for i in range(1, N+1):
    if i in A_:
        print(A.count(i))
        A = A[A.count(i):]
    else:
        print(0)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

import collections
c = collections.Counter(A)

for i in range(1, N+1):
    print(c[i])
### BUGGY CODE ###

n,m = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
x_diff = []
for i in range(1,m):
  x_diff.append(x[i]-x[i-1])
x_diff.sort()
if n >= m:
  print(0)
else:
  for j in range(1,n):
    x_diff.remove(x_diff[-1])
  print(sum(x_diff))

### FIXED CODE ###

n,m = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
x_diff = [x[i]-x[i-1] for i in range(1,m)]
x_diff.sort(reverse = True)
if n >= m:
  print(0)
else:
  del x_diff[:n-1]
  print(sum(x_diff))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.append(0)
b = [abs(a[0])]
c = [abs(a[1])]
for i in range(n):
    b.append(abs(a[i] - a[i+1]))
    if i < n-1:
        c.append(abs(a[i] - a[i+2]))

for i in range(n):
    ans = c[i]
    for j in range(0,i):
        ans += b[j]
    for k in range(i+2,n+1):
        ans += b[k]
    print(ans)


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.append(0)
b = [abs(a[0])]
c = [abs(a[1])]

for i in range(n):
    b.append(abs(a[i] - a[i+1]))
    if i < n-1:
        c.append(abs(a[i] - a[i+2]))
sum_b = sum(b)
for i in range(n):
    print(sum_b + c[i] - b[i] - b[i+1])
### BUGGY CODE ###

from bisect import bisect_right#(sorted_list,x)で昇順ソート位置

n = int(input())
l = list(map(int, input().split()))

l.sort()
ans = 0
for i in reversed(range(2,n)):
  for j in reversed(range(1,i)):
    s = l[i]-l[j]
    ans += len(l[:j])-bisect_right(l[:j],s)
print(ans)

### FIXED CODE ###

from bisect import bisect_left#(sorted_list,x)で昇順ソート位置

n = int(input())
l = list(map(int, input().split()))

l.sort()
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    s = l[i]+l[j]
    ans += bisect_left(l,s,j+1)-j-1
print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N = int(input())
A = list(map(int, input().split()))

A.sort()
# print(A)

ans = 0
for i in range(N):
    is_ok = True
    for j in range(i+2):
        if i == j:
            continue
        if j == N:
            break
        if A[i] % A[j] == 0:
            # print("break {} {}".format(i, j))
            is_ok = False
            break
    if is_ok:
        # print(A[i])
        ans += 1
print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

import collections
N = int(input())
A = list(map(int, input().split()))
cA = collections.Counter(A)

LIM = 10 ** 6 + 1
# LIM = 25

A.sort()
dp = [1] * LIM

for i in set(A):
    s = i * 2
    while s < LIM:
        dp[s] = 0
        s += i

ans = 0
# print(dp)
for a in A:
    # print("{} {}".format(dp[a], cA[a]))
    if dp[a] and cA[a] == 1:
        # print(a)
        ans += 1
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))

for _ in range(M):
    B, C = map(int, input().split())
    A.sort()
    A[:B] = map(lambda x:max(x, C), A[:B])

print(sum(A))


### FIXED CODE ###

import numpy as np
import heapq as hq
N, M = map(int, input().split())
A = list(map(int, input().split()))

class BC():
    def __init__(self, b, c):
        self.b = b
        self.c = c

    def __eq__(self, other):
        return self.c == other.c    

    def __lt__(self, other):
        return self.c > other.c

    def __ne__(self, other):
        return not self.__eq__(other)

    def __le__(self, other):
        return self.__lt__(other) or self.__eq__(other)

    def __gt__(self, other):
        return not self.__le__(other)

    def __ge__(self, other):
        return not self.__lt__(other)

heap = []
for _ in range(M):
    hq.heappush(heap, BC(*map(int, input().split())) )

result = []
for _ in range(M):
    bc = hq.heappop(heap)
    result.extend([bc.c] * bc.b)

    if len(result) > N:
        break

A.extend(result)
A.sort(reverse=True)
print(np.sum(A[:N]))
### BUGGY CODE ###

while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break

    comb = set()
    for i in range(1, n+1):
        for j in range(2, n+1):
            for k in range(3, n+1):
                if i == j or j == k or i == k:
                    continue
                elif i + j + k == x:
                    sort_9 = sorted((i, j, k))
                    comb.add(tuple(sort_9))

    print(len(comb))



### FIXED CODE ###

while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break

    comb = set()
    for i in range(1, n+1):
        for j in range(i+1, n+1):
            for k in range(j+1, n+1):
                if i == j or j == k or i == k:
                    continue
                elif i + j + k == x:
                    sort_9 = sorted((i, j, k))
                    comb.add(tuple(sort_9))

    print(len(comb))
### BUGGY CODE ###

import bisect as bis

n = int(input())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))

ans = 0
for i in range(n):
    top = a[i]
    for j in range(n):
        mid = b[j]
        if top >= mid:
            continue
        k = bis.bisect_right(c, mid)
        ans += n - k

print(ans)

### FIXED CODE ###

import bisect as bis

n = int(input())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))

ans = 0
for b_e in b:
    n_top = bis.bisect_left(a, b_e)
    n_bottom = n - bis.bisect_right(c, b_e)
    ans += n_top * n_bottom

print(ans)
### BUGGY CODE ###

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

dup = sum(a) - n * (n + 1) // 2
d1 = a.index(dup)
d2 = a.index(dup, d1 + 1)

C = n + 1
Cdup = 1
for k in range(1, n + 2):
    print((C - Cdup) % (10 ** 9 + 7))
    C = C * (n + 1 - k) // (k + 1)
    Cdup = Cdup * (d1 + n - d2 - k + 1) // k


### FIXED CODE ###

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

dup = sum(a) - n * (n + 1) // 2
d1 = a.index(dup)
d2 = a.index(dup, d1 + 1)

N = n + 1
Ndup = d1 + n - d2

MOD = 10 ** 9 + 7

def power(x, n):
    ans = 1
    while n:
        if n % 2 == 1:
            ans = (ans * x) % MOD
        x = (x * x) % MOD
        n //= 2
    return ans

# fack[k]: kの階乗
fact = [0 for i in range(N + 1)]
fact[0] = 1
for i in range(1, N + 1):
    fact[i] = (fact[i - 1] * i) % MOD

# inv[k]: kの階乗の逆元
inv = [0 for i in range(N + 1)]
inv[N] = power(fact[N], MOD - 2) % MOD
for i in range(N - 1, -1, -1):
    inv[i] = (inv[i + 1] * (i + 1)) % MOD

def comb(n, r):
    if n < r:
        return 0
    else:
        return (fact[n] * inv[n - r] * inv[r]) % MOD

for k in range(1, N + 1):
    C = comb(N, k)
    Cdup = comb(Ndup, k - 1)
    print((C - Cdup) % MOD)
### BUGGY CODE ###

import math
from functools import reduce
import itertools
k=int(input())
def gcd(*numbers):
    return reduce(math.gcd,numbers)
ans=0
for i,j,m in itertools.product(range(1,k+1),range(1,k+1),range(1,k+1)):
    ans+=gcd(i,j,m)
print(ans)

### FIXED CODE ###

import math
from functools import reduce
import itertools
k=int(input())
def gcd(*numbers):
    return reduce(math.gcd,numbers)
ans=0
for i,j,m in itertools.product(range(1,k+1),range(1,k+1),range(1,k+1)):
    ans+=gcd(i,j,m)
print(ans)
### BUGGY CODE ###

a,b,k = map(int,input().split())
     
for i in range(k):
  if a == b == 0 : break
  if a > 0:
    a -= 1
  elif b > 0:
    b -= 1
     
print(str(a) + " " + str(b))

### FIXED CODE ###

A, B, K = map(int,input().split())

A -= K
if(A < 0):
    B -= abs(A)
    A = 0
    if(B < 0):
        B = 0

print(str(A) + " " + str(B))
### BUGGY CODE ###

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

from collections import deque

def main():

    input_buffer = """
    
    """
    #8
    #1 2
    #2 3
    #2 4
    #2 5
    #4 7
    #5 6
    #6 8
    
    INPUT = list(reversed(input_buffer.strip().splitlines()))
    if INPUT:
        n = int(INPUT.pop())
        edges = [0] * (n-1)
        for i in range(n-1):
            edges[i] = tuple(map(int, INPUT.pop().split()))
    else:
        n = int(input())
        edges = [0] * (n-1)
        for i in range(n-1):
            edges[i] = tuple(map(int, input().split()))
        
    
    adjacency_list = [[] for i in range(n+1)]
    for edge in edges:
        adjacency_list[edge[0]].append(edge[1])
        adjacency_list[edge[1]].append(edge[0])
    
    
    max_order = max(len(i) for i in adjacency_list)
    root = 0
    for i in range(0, n+1):
        if len(adjacency_list[i]) == max_order:
            root = i
                 
    
    node_history = set()
    edge_dict = dict()
    node_deque = deque()
    
    
    node_deque.append(root)
    while len(node_deque):
        current_node = node_deque.popleft()
        undef_edges = []
        kinds = {i for i in range(1, max_order + 1)}
        
        for a in adjacency_list[current_node]:
            if a not in node_history:
                node_history.add(a)
                node_deque.append(a)
                
            if current_node < a:
                temp_edge = (current_node, a)
            else:
                temp_edge = (a, current_node)    
            
            if temp_edge in edge_dict.keys():
                kinds.remove(edge_dict[temp_edge])
            else:
                undef_edges.append(temp_edge)
                
        for undef_edge in undef_edges:
            kind = min(kinds)
            edge_dict[undef_edge] = kind
            kinds.remove(kind)
    
    
    print(max_order)
    for e in edges:
        print(edge_dict[e])
        
main()

### FIXED CODE ###

from collections import deque

def main():
	N, *AB = map(int, open(0).read().split())
	B = AB[1::2]

	E = [[] for _ in range(N + 1)]
	for a, b in zip(*[iter(AB)] * 2):
		E[a].append(b)

	Q = deque([1])
	C = [0] * (N + 1)
	while Q:
		v = Q.popleft()
		c = 0
		for u in E[v]:
			c += 1 + (c + 1 == C[v])
			C[u] = c
			Q.append(u)

	print(max(C))
	for b in B:
		print(C[b])

main()
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
a.sort()

cnt = []
tmp = a[0]
cnt1 = 1
for i in range(1, N):
    if(abs(tmp-a[i]) <= 2):
        cnt1 += 1
    else:
        cnt.append(cnt1)
        if(abs(a[i]-a[i-1]) <= 1):
            cnt1 = a.count(a[i-1]-1)+a.count(a[i-1])+1
            tmp = a[i-1]-1
        else:
            cnt1 = 1
            tmp = a[i]
if(len(cnt) > 0):
    print(max(cnt1, max(cnt)))
else:
    print(cnt1)

### FIXED CODE ###

import collections

N = int(input())
a = list(map(int, input().split()))
a.sort()
c = collections.Counter(a)

cnt = []
tmp = a[0]
cnt1 = 1
for i in range(1, N):
    if(abs(tmp-a[i]) <= 2):
        cnt1 += 1
    else:
        cnt.append(cnt1)
        if(a[i]-a[i-1] <= 1):
            cnt1 = c.get(a[i-1]-1, 0)+c.get(a[i-1], 0)+1
            tmp = a[i-1]-1
        else:
            cnt1 = 1
            tmp = a[i]
if(len(cnt) > 0):
    print(max(cnt1, max(cnt)))
else:
    print(cnt1)
### BUGGY CODE ###

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

import math

total=1
for i in range(n):
    total*=a[i]

b = int(math.pow(10,18))

if total-b>0:
    print(-1)
else:
    print(total)



### FIXED CODE ###

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

if a.count(0)>0:
    print(0)
    exit(0)

total=1
for i in a:
    total *=i

    if total>10**18:
        print(-1)
        exit(0)
    
print(total)
### BUGGY CODE ###

#
# abc077 c
#
import sys
from io import StringIO
import unittest
import bisect


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2
1 5
2 4
3 6"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
1 1 1
2 2 2
3 3 3"""
        output = """27"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """6
3 14 159 2 6 53
58 9 79 323 84 6
2643 383 2 79 50 288"""
        output = """87"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    A.sort()
    B.sort()
    C.sort()

    ans = 0
    for a in A:
        if a >= B[-1]:
            break
        bi = bisect.bisect(B, a)
        BT = B[bi:]
        for b in BT:
            if b >= C[-1]:
                break
            ans += len(C) - bisect.bisect(C, b)

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()


### FIXED CODE ###

#
# abc077 c
#
import sys
from io import StringIO
import unittest
import bisect


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2
1 5
2 4
3 6"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
1 1 1
2 2 2
3 3 3"""
        output = """27"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """6
3 14 159 2 6 53
58 9 79 323 84 6
2643 383 2 79 50 288"""
        output = """87"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    A.sort()
    B.sort()
    C.sort()

    ans = 0
    for b in B:
        an = bisect.bisect_left(A, b)
        cn = N - bisect.bisect_right(C, b)
        ans += an*cn

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()
### BUGGY CODE ###

from heapq import heappush, heappop
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))

a.sort(reverse=True)
f.sort()


def check(x):
    red = 0
    for i in range(n):
        if a[i] * f[i] > x:
            red += a[i] - x // f[i]

    return (red <= k)


lb = -1  # false
ub = max([a[i] * f[i] for i in range(n)])  # true
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)


### FIXED CODE ###

from heapq import heappush, heappop
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))

a.sort(reverse=True)
f.sort()


def check(x):
    red = 0
    for i in range(n):
        if a[i] * f[i] > x:
            red += a[i] - x // f[i]

    return (red <= k)


lb = -1  # false
ub = max([a[i] * f[i] for i in range(n)])  # true
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)
### BUGGY CODE ###

N, A, B = map(int, input().split())

b_count = 0
n_count = 0
while n_count < N:
    if n_count + A < N:
        b_count += A
    else:
        b_count += N - n_count
        break
    n_count += A + B
print(b_count)

### FIXED CODE ###

N, A, B = map(int, input().split())

division = N // (A + B)
count = division * A

count += N - division * (A + B) if A > N - division * (A + B) else A
print(count)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

flag = True
for i in range(n - 1):
    if a[i + 1] - a[i] >= 2:
        flag = False
if a[0] != 0:
    flag = False

count = 0
start = 0
if flag == True:
    while a != [0] * n:
        for i in range(start, n - 1):
            if a[i] + 1 == a[i + 1]:
                start = i
                break
        for j in range(start, n - 1):
            if a[j] + 1 != a[j + 1]:
                end = j
                break
            if j == n - 2:
                end = n - 1
        for k in range(end, start - 1, -1):
            if end != n - 1:
                a[k] = max(0, a[k + 1] - 1)
            else:
                a[k] = 0
        count = count + end - start
if flag == False:
    print(-1)
else:
    print(count)

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

flag = True
for i in range(n - 1):
    if a[i + 1] - a[i] >= 2:
        flag = False
if a[0] != 0:
    flag = False

count = 0
if flag == True:
    for i in range(n - 1):
        if a[i] != 0:
            count = count + 1
        if a[i] >= a[i + 1]:
            count = count + max(0, a[i + 1] - 1)
   
if flag == False:
    print(-1)
elif a[n - 1] != 0:
    print(count + 1)
else:
    print(count)