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

n,k = map(int,input().split())
dp = [[0]*k for _ in range(n)]
dp[0] = [1]*k

gcd = [[0]*k for _ in range(k)]
for i in range(k):
    for j in range(k):
        if i == j:
            gcd[i][j] = i+1
        else:
            if i > j:
                gcd[i][j] = gcd[i-j-1][j]
            else:
                gcd[i][j] = gcd[i][j-i-1]
        
for i in range(1,n):
    for j in range(k):
        if dp[i-1][j] != 0:
            for l in range(k):
                dp[i][gcd[j][l]-1] += dp[i-1][j]

ans = 0
mod = 10**9+7
for i,j in enumerate(dp[n-1]):
    ans += (i+1)*j
    ans %= mod

print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
dp = [0]*k
mod = 10**9 + 7
ans = 0
for i in range(k,0,-1):
    dp[i-1] += pow(k//i,n,mod)
    for j in range(k//i,1,-1):
        dp[i-1] -= dp[i*j-1]
    ans += dp[i-1]*i
    ans %= mod
    
print(ans)
### BUGGY CODE ###

firstvar = input()
l = int(firstvar.split(" ")[0])
r = int(firstvar.split(" ")[1])
i = l
min = 2019
for i in range(l,r + 1):
    for j in range(i + 1, r + 1):
        mod = (i*j)%2019
        if mod < min:
            min = mod
            if mod == 0:
                break;
        j = j + 1
    i = i + 1
print(min)

### FIXED CODE ###

firstvar = input()
l = int(firstvar.split(" ")[0])
r = int(firstvar.split(" ")[1])
i = l
min = 2019
if (r/2019 - l/2019) >= 1:
    print(0)
else:
    for i in range(l,r + 1):
        for j in range(i + 1, r + 1):
            mod = (i*j)%2019
            if mod < min:
                min = mod
                if mod == 0:
                    break;
    print(min)
### BUGGY CODE ###

N = int(input())
C = input()

if "R" not in C:
    print(0)
    exit()
count = 0
for i in range(N):
    if C[i] == 'W':

        index = C.rfind('R', i)
        if index >= 0:
            count += 1
        c = list(C)
        c[i] = 'R'
        c[index] = 'W'
        C = "".join(c)

print(count)



### FIXED CODE ###

N = int(input())
C = input()

from collections import Counter

if "R" not in C:
    print(0)
    exit()
count = 0

c = Counter(C)
k = c["R"]
D = C[:k]
d = Counter(D)
print(d["W"])
### BUGGY CODE ###

import bisect
n, m = map(int, input().split())
*a, = sorted(map(int, input().split()))

for i in range(m):
    _a = a.pop()//2
    bisect.insort_left(a, _a)

print(sum(a))


### FIXED CODE ###

import heapq
n, m = map(int, input().split())
*a, = map(lambda x: -x, map(int, input().split()))

heapq.heapify(a)
for i in range(m):
    _a = int(heapq.heappop(a)/2)
    heapq.heappush(a, _a)

print(sum(a)*-1)
### BUGGY CODE ###

n = int(input())
L = sum([list(map(int, input().split())) for i in range(n)], [])
next = 1
count = 0
for i in range(n):
  if next == 2:
    print(i)
    exit()
  next = L[next-1]
print(-1)

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
cur = 1
cnt = 0
while True:
    if cur == 2:
        print(cnt)
        exit()
    elif cnt > n:
        print(-1)
        exit()
    else:
        cur = a[cur - 1]
        cnt += 1
### BUGGY CODE ###

n = int(input())
c = [int(input()) for i in range(n)]
dp = [1 for i in range(2*(10**5)+1)]
dp2 = [-1 for i in range(2*(10**5)+1)]
dp3 = [0 for i in range(2*(10**5)+1)]

ans = 1

def count(s):
  memo = {}
  res = 1
  for i in range(len(s)):
    if s[i] not in memo:
      memo[s[i]] = 1
    else:
      memo[s[i]] += 1
  for i in memo:
    res = res*2**(memo[i]-1)
  return res


dp2[c[0]] = 0
dp3[c[0]] += 1
#print("dp",dp)
#print("dp2",dp2)
     
for i in range(1,n):
  
  if c[i] != c[i-1]:
    if dp2[c[i]] == -1:
      dp2[c[i]] = i
      dp3[c[i]] += 1
    else:
      dp[c[i]] = count(c[dp2[c[i]]:i])*dp[c[i]]*(dp3[c[i]])
      ans += dp[c[i]]
      dp3[c[i]] += 1
      
      dp2[c[i]] = i
#  print(i,"dp",dp)
#  print(i,"dp2",dp2)
#  print(i,ans)
print(ans)

### FIXED CODE ###

n = int(input())
cc = [int(input()) for i in range(n)]
c = [cc[0]]
for i in range(1,n):
  if cc[i] != cc[i-1]:
    c.append(cc[i])

n = len(c)
dp = [0 for i in range(n)]
pos_dp = [-1 for i in range(2*10**5+1)]

dp[0] = 1
pos_dp[c[0]] = 0
     
for i in range(1,n):
  if pos_dp[c[i]]!=-1:
    dp[i] = (dp[i-1] + dp[pos_dp[c[i]]])%1000000007
  else:
    dp[i] = dp[i-1] 
  pos_dp[c[i]] = i

print(dp[n-1])
### BUGGY CODE ###

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

for i in range(K):
    if A > (i + 1):
        result += 1
        continue
    elif A == (i + 1):
        result += 1
        continue

    if B > (i + 1 - A):
        result += 0
        continue
    elif B == (i + 1 - A):
        result += 0
        continue

    if C > (i + 1 - A - B):
        result -= 1
        continue
    elif C == (i + 1 - A - B):
        result -= 1
        break
    else:
        break

print(result)


### FIXED CODE ###

A, B, C, K = map(int, input().split())
if A >= K:
    print(K)
elif (A + B) >= K:
    print(A)
elif (A + B + C) > K:
    print(A - (K - A - B))
elif (A + B + C) == K:
    print(A - C)
### BUGGY CODE ###

#51 C - Many Medians
N = int(input())
X = list(map(int,input().split()))
Xsrt = sorted(X,reverse = False)

ans = []
for x in X:
    Xc = Xsrt.copy()
    Xc.remove(x)
    B = Xc[len(Xc)//2]
    ans.append(B)

for i in ans:
    print(i)

### FIXED CODE ###

#51 C - Many Medians
N = int(input())
X = list(map(int,input().split()))
Xsrt = sorted(X,reverse = False)
XL = set(Xsrt[:N//2])
XR = set(Xsrt[N//2:])

ans = []
for x in X:
    if x in XR:
        ans.append(Xsrt[N//2-1])
    elif x in XL:
        ans.append(Xsrt[N//2])
for a in  ans:
    print(a)
### BUGGY CODE ###

def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    from collections import Counter
    c = Counter(A)

    for a in set(A):
        v = 2*a
        while v <= 10**6:
            c[v] += 1
            v += a

    ans = 0
    for a in A:
        if c[a] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    B = [True]*(10**6+1)

    from collections import Counter
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)

    ans = 0
    for a in set(A):
        if a not in bl and B[a]:
            ans += 1
        for i in range(1, 10**6):
            if 10**6 < a*i:
                break
            B[a*i] = False
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n, m = map(int, input().split())
h = np.array(input().split(), dtype='int')
good_tower = np.arange(1, n+1)
bad_tower = np.zeros((), dtype='int')

for i in range(m):
    way = np.array(input().split(), dtype='int')

    if h[way[0]-1] > h[way[1]-1]:
        bad_tower = np.append(bad_tower, way[1])
    elif h[way[0]-1] < h[way[1]-1]:
        bad_tower = np.append(bad_tower, way[0])
    elif h[way[0]-1] == h[way[1]-1]:
        bad_tower = np.append(bad_tower, way[0])
        bad_tower = np.append(bad_tower, way[1])

bad_tower = np.array(list(set(bad_tower)))

for i in bad_tower:
    good_tower = good_tower[~(good_tower == i)]

print(len(good_tower))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n, m = map(int, input().split())
h = np.array(input().split(), dtype='int')
bad_tower = np.zeros((n), dtype='int')

for i in range(m):
    a, b = map(int, input().split())
    ha = h[a-1]
    hb = h[b-1]

    if ha > hb:
        bad_tower[b-1] = 1
    elif ha < hb:
        bad_tower[a-1] = 1
    elif ha == hb:
        bad_tower[a-1] = 1
        bad_tower[b-1] = 1

ans = n - np.sum(bad_tower)

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

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

c = 0

while True:
    gusu = False

    for i, aa in enumerate(a):
        if gusu is False and a[i] % 2 == 0:
            a[i] /= 2
            gusu = True
            continue

    if gusu is False:
        break

    c += 1

print(c)


### FIXED CODE ###

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

c = 0

for i, aa in enumerate(a):
    while a[i] % 2 == 0:
        a[i] /= 2
        c += 1

print(c)
### BUGGY CODE ###

from fractions import gcd
import sys 
input = sys.stdin.readline

def lcm(a,b):
    return a*b//gcd(a,b)


def pow_mod(x,n):
    if n==0:
        return 1
    
    K = 1
    while n>1:
        if n%2 != 0:
            K *= x
            K %= mod
        x *= x
        x %= mod
        n //= 2

    return K*x

mod=10**9+7
N = int(input())
A = list(map(int,input().split()))

if N==1:
    print(1)
    exit()

Gcd = lcm(A[0],A[1])
ans = (Gcd//A[0]+Gcd//A[1])%mod
temp = Gcd//A[1]
#print(temp)

for i in range(1,N-1):
    Gcd = lcm(A[i],A[i+1])
    temp2 = Gcd//A[i]
    Gcd2 = lcm(temp,temp2)
    a = Gcd2//temp
    b = Gcd2//temp2

    temp = Gcd//A[i+1]*b

    a %= mod
    b %= mod
    ans *= a
    ans %= mod

    Gcd %= mod #注意
    c = A[i+1]
    c %= mod
    d = Gcd*pow_mod(c,mod-2)
    #d = Gcd//c
    d %= mod

    e = b*d%mod
    ans += e
    #ans += Gcd//A[i+1]*b
    ans %= mod


print(ans)

### FIXED CODE ###

from fractions import gcd
import sys 
input = sys.stdin.readline

def pow_mod(x,n):
    if n==0:
        return 1
    
    K = 1
    while n>1:
        if n%2 != 0:
            K *= x
            K %= mod
        x *= x
        x %= mod
        n //= 2

    return K*x

mod=10**9+7
N = int(input())
A = list(map(int,input().split()))

if N==1:
    print(1)
    exit()

Gcd = gcd(A[0],A[1])
ans = (A[0]//Gcd+A[1]//Gcd)%mod
temp = A[0]//Gcd

for i in range(1,N-1):
    #Gcd = lcm(A[i],A[i+1])
    Gcd = gcd(A[i],A[i+1])
    #temp2 = Gcd//A[i]
    temp2 = A[i+1]//Gcd
    #Gcd2 = lcm(temp,temp2)
    Gcd2 = gcd(temp,temp2)

    #a = Gcd2//temp
    a = temp2//Gcd2
    #b = Gcd2//temp2
    b = temp//Gcd2

    temp = A[i]//Gcd*b

    a %= mod
    b %= mod
    ans *= a
    ans %= mod


    Gcd %= mod #注意
    c = A[i]
    c %= mod
    d = c*pow_mod(Gcd,mod-2)
    #d = Gcd//c
    d %= mod


    e = b*d%mod
    ans += e
    #ans += Gcd//A[i+1]*b
    ans %= mod


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

N = int(input())
A = [input() for i in range(N)]
B = list(set(A))
C = [0]*len(B)
for i in range(len(B)):
  C[i] = A.count(B[i])
D = max(C)
E = sorted([B[i] for i, x in enumerate(C) if x == D])
for i in range(len(E)):
  print(E[i])




### FIXED CODE ###

N = int(input())

d = {}
for _ in range(N):
    S = input()
    if S in d:
        d[S] += 1
    else:
        d[S] = 1

m = max(d.values())
for s in sorted(k for k in d if d[k] == m):
    print(s)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
graph = [[2000 for i in range(w)] for j in range(h)]
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
def bfs(que):
    finished = set()
    while que:
        x , y, cost = que.popleft()
        if (x,y) not in finished and graph[y][x] > cost:
            finished.add((x,y))
            graph[y][x] = cost
            if check(y,x+1):
                que.append([x+1,y,cost+1])
            if check(y+1,x):
                que.append([x, y+1, cost+1])
            if check(y,x-1):
                que.append([x-1,y,cost+1])
            if check(y-1,x):
                que.append([x,y-1,cost+1])
for i in range(h):
    grid.append(list(input()))
que = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            que.append((j,i,0))
bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
graph = [[2000 for i in range(w)] for j in range(h)]
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
def bfs(que):
    finished = set()
    while que:
        x ,y = que.popleft()
        if y*w+x not in finished:
            finished.add(y*w+x)
            for n_x,n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
                if check(n_y,n_x) and graph[n_y][n_x] > graph[y][x] + 1:
                    graph[n_y][n_x] = graph[y][x] + 1
                    que.append((n_x,n_y))
for i in range(h):
    grid.append(list(input()))
que = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            graph[i][j] = 0
            que.append((j,i))
bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7

N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]

dp = [[0] * (1 << (N)) for _ in range(N + 1)]

dp[0][0] = 1
# for tmp in dp:
#     print (tmp)
lst = [0]

for i in range(N):
    tmp = []
    for j in range(N):
        if A[i][j] == 0: #仲良くない時
            continue
        #以下仲が良い時のみの処理        
        for k in lst:
            if (1 << j) & k == 0: #まだペアになっていない女の人の時
                dp[i + 1][k + (1 << j)] = (dp[i + 1][k + (1 << j)] + dp[i][k]) % MOD
                tmp.append(k + (1 << j))
    
        # print (dp[i + 1])
        # print (lst)
    lst = tmp

print (dp[N][(1 << N) - 1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7

N = int(input())

A = [tuple(map(int, input().split())) for _ in range(N)]

dp = [-1] * (1 << N)
dp[(1 << N) - 1] = 1

def dfs(group, count):
    if dp[group] != -1:
        return dp[group]
    res = 0
    for i in range(N):
        if (group >> i) & 1 == 0 and A[count][i] == 1:
            res += dfs(group + (1 << i), count + 1)
    dp[group] = res % MOD
    return dp[group]

tmp = dfs(0, 0)

print (tmp)
### BUGGY CODE ###

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

for i in range(n):
    if a.count(a[i]) == 1:
        continue
    else:
        print('NO')
        exit()

print('YES')

### FIXED CODE ###

import collections

n = int(input())
a = list(input().split())
c = collections.Counter(a)

if c.most_common()[0][1] != 1:
    print('NO')
    exit()

print('YES')
### BUGGY CODE ###

S = input()
dp = [[0] * 13 for _ in range(2)]

mod = 10**9 + 7
dp[0][0] = 1
pow10 = 1
for i, s in enumerate(S[::-1]):
    now_idx, next_idx = i & 1, (i + 1) & 1
    dp[next_idx] = [0] * 13
    if s == '?':
        for j in range(13):
            for k in range(10):
                next_mod = (j + k * pow10) % 13
                dp[next_idx][next_mod] += dp[now_idx][j]
                dp[next_idx][next_mod] %= mod
    else:
        k = int(s)
        for j in range(13):
            next_mod = (j + k * pow10) % 13
            dp[next_idx][next_mod] += dp[now_idx][j]
            dp[next_idx][next_mod] %= mod
    pow10 = (pow10 * 10) % 13
print(dp[len(S) & 1][5])


### FIXED CODE ###

S = input()
dp = [[0] * 13 for _ in range(2)]

mod = 10**9 + 7
dp[0][0] = 1
pow10 = 1
for i, s in enumerate(S[::-1]):
    now_idx, next_idx = i & 1, (i + 1) & 1
    dp[next_idx] = [0] * 13
    if s == '?':
        for j in range(13):
            for k in range(10):
                next_mod = (j + k * pow10) % 13
                dp[next_idx][next_mod] += dp[now_idx][j]
                dp[next_idx][next_mod] %= mod
    else:
        k = int(s)
        for j in range(13):
            next_mod = (j + k * pow10) % 13
            dp[next_idx][next_mod] += dp[now_idx][j]
            dp[next_idx][next_mod] %= mod
    pow10 = (pow10 * 10) % 13
print(dp[len(S) & 1][5])
### BUGGY CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N, M, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))


    nowtime = 0

    Asum = [0]
    Bsum = [0]
    tmp = 0
    for a in A:
        tmp += a
        Asum.append(tmp)
    tmp = 0
    for b in B:
        tmp += b
        Bsum.append(tmp)

    maxbooks = 0
    before = M
    for acount in range(N+1):
        for bcount in range(0, before+1):
            if K < Asum[acount] + Bsum[bcount]:
                bcount -= 1
                break
        before = bcount
        if bcount < 0:
            break
        maxbooks = max(maxbooks, acount+bcount)

    print(maxbooks)



if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N, M, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))


    nowtime = 0

    Asum = [0]
    Bsum = [0]
    tmp = 0
    for a in A:
        tmp += a
        Asum.append(tmp)
    tmp = 0
    for b in B:
        tmp += b
        Bsum.append(tmp)

    maxbooks = 0
    before = M
    bcount = M
    for acount in range(N+1):
        if Asum[acount] > K:
            continue
        while K < Asum[acount] + Bsum[bcount]:
            bcount -= 1
        maxbooks = max(maxbooks, acount+bcount)

    print(maxbooks)



if __name__ == '__main__':
    solve()
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N=int(input())
P=list(map(float,input().split()))

dp=[[0]*(N+1) for i in range(N+1)]

dp[0][0]=1
for n in range(N):
    for i in range(n+1):
        j=n-i
        dp[j][i+1]+=dp[j][i]*P[n]
        dp[j+1][i]+=dp[j][i]*(1-P[n])

ans=0
for i in range((N+1)//2):
    ans+=dp[i][-i-1]

print(ans)


### FIXED CODE ###

# coding: utf-8
# Your code here!
N=int(input())
P=list(map(float,input().split()))

dp=[[0]*(N+1) for i in range(N+1)]

dp[0][0]=1
for n in range(N):
    for i in range(n+1):
        j=n-i
        dp[j][i+1]+=dp[j][i]*P[n]
        dp[j+1][i]+=dp[j][i]*(1-P[n])

ans=0
for i in range((N+1)//2):
    ans+=dp[i][-i-1]

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

from collections import deque
H, W = [int(x) for x in input().split()]
masu = [input() for i in range(H)]
move = [[0, 1], [0, -1], [1, 0], [-1, 0]]
d = [[-1] * W for i in range(H)]

def bfs():
    q = deque()
    for x in range(H):
        for y in range(W):
            if masu[x][y] == '#':
                q.append([x, y])
                d[x][y] = 0
    while q:
        x, y = q.popleft()
        for v in move:
            nx = x + v[0]
            ny = y + v[1]
            if 0 <= nx < H and 0 <= ny < W and d[nx][ny] == -1:
                q.append([nx, ny])
                d[nx][ny] = d[x][y] + 1
    ans = -1
    for x in range(H):
        for y in range(W):
            ans = max(ans, d[x][y])
    return ans

print(bfs())


### FIXED CODE ###

from collections import deque
H, W = [int(x) for x in input().split()]
masu = [input() for i in range(H)]
move = [[0, 1], [0, -1], [1, 0], [-1, 0]]
d = [[-1] * W for i in range(H)]

def bfs():
    q = deque()
    for x in range(H):
        for y in range(W):
            if masu[x][y] == '#':
                q.append([x, y])
                d[x][y] = 0
    while q:
        x, y = q.popleft()
        for v in move:
            nx = x + v[0]
            ny = y + v[1]
            if 0 <= nx < H and 0 <= ny < W and d[nx][ny] == -1:
                q.append([nx, ny])
                d[nx][ny] = d[x][y] + 1
    ans = -1
    for x in range(H):
        for y in range(W):
            ans = max(ans, d[x][y])
    return ans

print(bfs())
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    def ncr(n, r, mod):
        r = min(r, n-r)
        numer = denom = 1
        for i in range(1, r+1):
            numer = numer * (n+1-i) % mod
            denom = denom * i % mod
        return numer * pow(denom, mod-2, mod) % mod

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

    res_max, res_min = 0, 0
    for i in range(k-1, n):
        res_max += a[i] * ncr(i, k-1, mod) % mod
    for i in range(n-k+1):
        res_min += a[i] * ncr(n-i-1, k-1, mod) % mod
    
    print((res_max - res_min)%mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    max_n = 10**5
    fac, inv = [1]*(max_n+1), [0]*(max_n+1)
    for i in range(2, max_n+1):
        fac[i] = fac[i-1] * i % mod
    inv[-1] = pow(fac[-1], mod-2, mod)
    for i in range(max_n, 0, -1):
        inv[i-1] = inv[i] * i % mod

    def ncr(n, r):
        return fac[n]*inv[r]*inv[n-r]%mod

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

    res_max,res_min = 0, 0
    for i in range(k-1, n):
        temp = ncr(i, k-1)
        res_max += a[i]*temp
        res_min += a[-(i+1)]*temp

    print((res_max - res_min)%mod)

if __name__ == '__main__':
    main()
### BUGGY CODE ###


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 judge(x):
    val = 0
    for i in range(N):
        val += max(A[i] - x // F[i], 0)
        if val > K:
            return False
    if val <= K:
        return True


ub = 10**12
lb = 0

for i in range(150):
    x = (ub+lb)/2
    if judge(x):
        ub = x
    else:
        lb = x

print(int(x))

### FIXED CODE ###

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 judge(x):
    val = 0
    for i in range(N):
        val += max(A[i] - x // F[i], 0)
        if val > K:
            return False
    if val <= K:
        return True


ub = 10**12
lb = -1

while lb + 1 < ub:
    x = (ub+lb)/2
    if judge(x):
        ub = x
    else:
        lb = x

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

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

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

if ans > 10**18:
    print(-1)
else:
    print(ans)



### FIXED CODE ###

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

ans = 1
if 0 in a:
    ans = 0
else :
    for i in a:
        if  ans * i > 10**18:
            ans = -1
            break
        else:
            ans *= i

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

H, W, M = map(int, input().split())
 
h = [0] * H
w = [0] * W
Mem = [tuple(map(int, input().split())) for _ in range(M) ]
for i, j in Mem:
  h[i-1] += 1
  w[j-1] += 1

maxh = max(h)
maxw = max(w)
 
listh = [i for i, v in enumerate(h, 1) if v == maxh]
listw = [j for j, v in enumerate(w, 1) if v == maxw]

cnt = len(listh) * len(listw)

for i, j in Mem:
  if i in listh and j in listw:
    cnt -= 1
 
if cnt:
  ans = maxh + maxw
else:
  ans = maxh + maxw - 1

print(ans)

### FIXED CODE ###

h,w,m=map(int,input().split())
item=[list(map(int,input().split())) for i in range(m)]
row=[0]*h
col=[0]*w
for i in range(m):
    x,y=item[i]
    row[x-1]+=1
    col[y-1]+=1
mr,mc=max(row),max(col)
xr=set([i for i in range(h) if row[i]==mr])
xc=set([i for i in range(w) if col[i]==mc])
check=len(xr)*len(xc)
for i in range(m):
    r,c=item[i]
    if r-1 in xr and c-1 in xc:
        check-=1
print(mr+mc if check>0 else mr+mc-1)