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

import numpy as np
import collections
N = int(input())
D = [int(i) for i in input().split()]+[0, 24]

C = collections.Counter(D)
if C.most_common()[0][1] >= 3:
    print(0)
    exit()


ans = 0
for i in range(2 ** N):
    D0 = D
    for j in range(N):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            D0[j] = 24-D0[j]

        D0 = np.sort(np.array(D0))
        c = np.amin(np.diff(D0))
    ans = max(ans, c)

print(ans)


### FIXED CODE ###

import collections
import copy
N = int(input())
D = [int(i) for i in input().split()]

C = collections.Counter(D)
if C.most_common()[0][1] >= 3:
    print(0)
    exit()

D1 = [0, 24]
m = []
for k, v in C.items():
    if v == 2:
        D1.append(k)
        D1.append(24-k)
    elif v == 1:
        m.append(k)

ans = 0
for i in range(2 ** len(m)):
    D0 = copy.deepcopy(D1)
    for j in range(len(m)):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            D0.append(24-m[j])
        else:
            D0.append(m[j])

    # print(D0)

    D0 = sorted(D0)
    c = 24
    for i in range(N+1):
        c = min(c, D0[i+1]-D0[i])
    ans = max(ans, c)

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

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    A = in_nl()

    n1 = A.count(1)
    n2 = A.count(2)
    n3 = A.count(3)

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

    def solve(n1, n2, n3):

        if dp[n1][n2][n3] != -1:
            return dp[n1][n2][n3]

        cnt = n1 + n2 + n3
        ret = 0
        if n3 >= 1:
            ret += solve(n1, n2 + 1, n3 - 1) * n3 / cnt
        if n2 >= 1:
            ret += solve(n1 + 1, n2 - 1, n3) * n2 / cnt
        if n1 >= 1:
            ret += solve(n1 - 1, n2, n3) * n1 / cnt

        dp[n1][n2][n3] = ret + (N / cnt)
        return ret + (N / cnt)

    print(solve(n1, n2, n3))


if __name__ == '__main__':
    main()


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1.0 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0.0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=n
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))
### BUGGY CODE ###

N = input()[::-1]
iv = 1
MOD = 10**9+7
dp = [0]*13
dp[0]=1
ls = [0]*13
for i in range(len(N)):
  x = N[i]
  
  if x=='?':
    for j in range(13):
      for h in range(10):
        ls[(h*iv+j)%13] += dp[j]
        
  else:
    x = int(x)
    for j in range(13):
      ls[(j+x*iv)%13]+=dp[j]
      
  for j in range(13):
    dp[j] = (ls[j]%MOD)
    ls[j]=0
  iv *= 10
  iv %= 13
print(dp[5])

### FIXED CODE ###

S = input()
con = 10**9 + 7

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            i = (_r + r) % 13
            tdp[i] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)
### BUGGY CODE ###

x = int(input())
import math
from collections import defaultdict


def isprime(n):
    if n <= 1:
        return 0
    m = int(math.sqrt(n)) + 1
    for i in range(2, m):
        if n % i == 0:
            return 0
    return 1


if isprime(x):
    print(1)
else:
    res = 0
    value = defaultdict(int)


    def bprime(n):
        cnt = 2
        while n != 1:
            while n % cnt == 0:
                n //= cnt
                value[cnt] += 1
            cnt += 1
    def cal(n):
        j = 1
        cnt = 0
        while n >= j:
            n -= j
            j += 1
            cnt += 1
        return cnt
    bprime(x)
    for key in value.keys():
        res += cal(value[key])
    print(res)

### FIXED CODE ###

x = int(input())
import math
from collections import defaultdict

res = 0
value = defaultdict(int)
def isprime(n):
    if n <= 1:
        return 0
    m = int(math.sqrt(n)) + 1
    for i in range(2, m):
        if n % i == 0:
            return 0
    return 1
if isprime(x):
    print(1)
else:
    def bprime(n):
        cnt = 2
        m = int(math.sqrt(n)) + 1
        while n != 1 and cnt < m:
            while n % cnt == 0:
                n //= cnt
                value[cnt] += 1
            cnt += 1
        if cnt == m and n != 1:
            value[n] += 1
    def cal(n):
        if n <= 2:
            return 1
        j = 1
        cnt = 0
        while n >= j:
            n -= j
            j += 1
            cnt += 1
        return cnt
    bprime(x)
    for key in value.keys():
        res += cal(value[key])
    print(res)
### BUGGY CODE ###

N = int(input())
S = input()
R = [i+1 for i in range(N) if S[i] == 'R']
G = [i+1 for i in range(N) if S[i] == 'G']
B = [i+1 for i in range(N) if S[i] == 'B']

ans = 0

for r in R:
    for g in G:
        tmp = 0
        a,b = sorted([r,g])
        i = b-a
        if a-i in B:
            tmp+=1
        if b+i in B:
            tmp+=1
        if a+(i/2) == b -(i/2) and a+(i/2) in B:
            tmp += 1
        ans += len(B) - tmp
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
c=s.count
a=c('R')*c('G')*c('B')
for i in range(n):
  for j in range(i+2,n,2):
    if s[i]!=s[i+j>>1]!=s[j]!=s[i]:
      a-=1
print(a)
### BUGGY CODE ###

import numpy as np
n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]


def dfs(pos, value, weight):
    if pos == n:
        return value
    if W - weight >= wv[pos][0]:
        ret1 = dfs(pos + 1, value + wv[pos][1], weight + wv[pos][0])
    else:
        ret1 = 0
    ret2 = dfs(pos + 1, value, weight)

    return max(ret1, ret2)


print(dfs(0, 0, 0))


### FIXED CODE ###

n, w = map(int, input().split())

inf = 10 ** 10
dp = [[inf] * (10**5+3) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    weight, value = map(int, input().split())
    for j in range(10**5 + 3):
        if j - value >= 0:
            dp[i+1][j] = min(
                dp[i][j - value] + weight,
                dp[i][j]
            )
        else:
            dp[i+1][j] = dp[i][j]
for i in reversed(range(10**5+3)):
    if dp[n][i] <= w:
        print(i)
        break
### BUGGY CODE ###

#float型を許すな
#numpyはpythonで
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,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
seq=LI()
seq.sort()
c=Counter(seq)
lis=[seq[0]]
for i in range(1,n):
    count=0
    for x in lis:
        if seq[i]%x!=0:
            count+=1
    if count==len(lis):
        lis.append(seq[i])
#print(lis)
ans=len(lis)
for x in lis:
    if c[x]>1:
        ans-=1
print(ans)
        


        
        
        


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K=int(input())

i=1
j=1
k=1
r=0
list=[2,3,5,7,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199]

while(i<K+1):
  j=1
  f=0
  if(i in list == True):
    f=1
  while(j<K+1):
    k=1
    g=0
    if(j in list == True):
      g=1
    while(k<K+1):
      h=0
      if(k in list == True):
        h=1
      if(i==1 or j==1 or k==1):
        r+=1
      elif(i==j and j==k):
        r+=i
      elif(f==1 and g==1 and h==1):
        r+=1
      elif(f==1 or g==1 or h==1):
        r+=1
      else:
        r+=gcd(i, j, k)
      k+=1
    j+=1
  i+=1

print(r)


### FIXED CODE ###

import math

K=int(input())
r=0

for i in range(1,K+1):
  for j in range(1,K+1):
    a=math.gcd(i,j)
    for k in range(1,K+1):
      b=math.gcd(a,k)
      r+=b
print(r)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m = max(a)
for j in range(n):
	if a[j] < m:
		print(m)
	else:
		b = a[:]
		b[j] = 0
		print(max(b))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m1 = max(a)
c = a.count(m1)
if len(set(a)) == 1:
	for i in range(n):
		print(m1)
else:
	m2 = sorted(set(a))[-2]
	for i in range(n):
		if a[i] < m1:
			print(m1)
		elif a[i] == m1:
			if c > 1:
				print(m1)
			else:
				print(m2)
		else:
			print(m2)
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

com_mx=200005
mod=998244353
fac=[0]*com_mx
finv=[0]*com_mx
inv=[0]*com_mx
fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1
for i in range(2,com_mx):
  fac[i]=fac[i-1]*i%mod
  inv[i]=mod-inv[mod%i]*(mod//i)%mod
  finv[i]=finv[i-1]*inv[i]%mod

def com(n,k):
  if n<k or n<0 or k<0:
    return 0
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod

n,m,k=LI()
ans=0
col=m
for x in range(n)[::-1]:
  now=col
  now*=com(n-1,x)
  if x<=k:
    ans+=now
    ans%=mod
  col*=m-1
print(ans)


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

com_mx=200005
mod=998244353
fac=[0]*com_mx
finv=[0]*com_mx
inv=[0]*com_mx
fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1
for i in range(2,com_mx):
  fac[i]=fac[i-1]*i%mod
  inv[i]=-inv[mod%i]*(mod//i)%mod
  finv[i]=finv[i-1]*inv[i]%mod

def com(n,k):
  if n<k or n<0 or k<0:
    return 0
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod

def main():
  n,m,k=LI()
  res=0
  tmp=m*pow(m-1,n-k-1,mod)
   
  for r in range(n-k-1,n):
    res=(res+tmp*com(n-1,r)%mod)%mod
    tmp=tmp*(m-1)%mod
  return res

# main()
print(main())
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import collections
n = int(input())
s = list(input())

c = collections.Counter(s)
total = c['R'] * c['G'] * c['B']
tmp = 0
#print(total)
for i in range(1, n - 1):
    for j in range(i + 1, n):
        k = 2 * j - i
        if i <= k <= n:
            #print(i, j, k)
            if s[i-1] != s[j-1] and s[i-1] != s[k-1] and s[j-1] != s[k-1]:
                tmp += 1
print(total - tmp)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections
n = int(input())
s = list(input())

c = collections.Counter(s)
total = c['R'] * c['G'] * c['B']
tmp = 0
#print(total)
for i in range(1, n - 1):
    for j in range(i + 1, n):
        k = 2 * j - i
        if i <= k <= n:
            #print(i, j, k)
            if s[i-1] != s[j-1] and s[i-1] != s[k-1] and s[j-1] != s[k-1]:
                tmp += 1
print(total - tmp)
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
while True:
  c-=b
  if c<=0:
    print('Yes')
  a-=d
  if a<=0:
    print('No')

### FIXED CODE ###

a,b,c,d=map(int,input().split())
while True:
  c-=b
  if c<=0:
    print('Yes')
    break
  a-=d
  if a<=0:
    print('No')
    break
### BUGGY CODE ###

N, M = map(int,input().split())
all_city = [list(map(int,input().split())) for i in range(M)]

city = {}
for i in all_city:
    if i[0] in city:
        city[i[0]].append(i[1])
    else:
        city[i[0]] = [i[1]]

for i,k in city.items():
    city[i] = sorted(k)

def change_Prefecture_code(prefecture):
    return str(prefecture).zfill(6)

def change_birth_code(birth_num):
    return str(birth_num).zfill(6)


for i in all_city:
    city_num = i[0]
    ind = city[city_num].index(i[1]) + 1
    print(change_Prefecture_code(city_num) + change_birth_code(ind))

### FIXED CODE ###

N, M = map(int,input().split())
all_city = [list(map(int,input().split())) for i in range(M)]
 
city = {}
for i in all_city:
    if i[0] in city:
        city[i[0]].append(i[1])
    else:
        city[i[0]] = [i[1]]
 
under6 = {}
for i,k in city.items():
    city[i] = sorted(k)
    for j in range(len(city[i])):
        under6[city[i][j]] = j + 1

def change_Prefecture_code(prefecture):
    return str(prefecture).zfill(6)
 
def change_birth_code(birth_num):
    return str(birth_num).zfill(6)
 
for i in all_city:
    print(change_Prefecture_code(i[0]) + change_birth_code(under6[i[1]]))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
B = list(map(int, input().split()))
B.sort(reverse=True)
C = list(map(int, input().split()))
C.sort(reverse=True)

Bn = [0] * N
prea = 0
for b in range(N):
    for a in range(prea, N):
        if A[a] < B[b]:
            prea = a
            break
    else:
        a = N
    Bn[b] = N-a

ans = 0
preb = 0
for c in range(N):
    for b in range(preb, N):
        if B[b] < C[c]:
            preb = b
            break
    else:
        b = N
    ans += sum(Bn[b:])

print(ans)


### FIXED CODE ###

import bisect
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = list(map(int, input().split()))
C = list(map(int, input().split()))
C.sort()

ans = 0
for i in range(N):
    cnta = bisect.bisect_left(A, B[i])
    cntc = bisect.bisect_right(C, B[i])
    ans += cnta * (N - cntc)

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

def main():
    import fractions
    import sys
    input = sys.stdin.readline
    N = int(input())
    a = tuple(map(int,input().split()))
    MOD = 10**9+7
    g1 = 1
    for t in a[:N//2]:
        g1 = divmod(g1*t,fractions.gcd(g1,t))[0]

    g2 = 1
    for t in a[N//2:]:
        g2 = divmod(g2*t,fractions.gcd(g2,t))[0]
    res = 0
    g = fractions.gcd(g1,g2)

    r1 = (g2//g)%MOD
    for t in a[:N//2]:
        res += divmod(g1,t)[0]%MOD
    res = res*r1%MOD

    res2 = 0
    r2 = (g1//g)%MOD
    for t in a[N//2:]:
        res2 += divmod(g2,t)[0]%MOD
    res2 = res2*r2%MOD
    print((res+res2)%MOD)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = 1
res = 0
MOD = 10**9+7
for elem in a:
    tmp = g*elem//fractions.gcd(g,elem)
    res *= tmp//g
    g = tmp
    res += g//elem
print(res%MOD)
### BUGGY CODE ###

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

import itertools

X, Y = two_int()

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

def calc(a, b, p):
    if b==0:
        return 1
    elif b%2==0:
        d=calc(a,b//2, p)
        return (d*d)%p
    else:
        return (a*calc(a,b-1,p))%p

dan = (X+Y)/3
if dan.is_integer():
    n = int(dan+1)
    k = X-(n-1)+1
    print(int(comb(n-1,k-1,(10**9+7))))
else:
    print(0)

### FIXED CODE ###

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

import itertools

X, Y = two_int()

def comb(n,r,mod, N):
    def cmb(n, r, mod):
        if ( r<0 or r>n ):
            return 0
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod

    mod = 10**9+7 #出力の制限
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル

    for i in range( 2, N + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )

    return cmb(n,r,mod)

def calc(a, b, p):
    if b==0:
        return 1
    elif b%2==0:
        d=calc(a,b//2, p)
        return (d*d)%p
    else:
        return (a*calc(a,b-1,p))%p

dan = (X+Y)/3
if dan.is_integer():
    n = int(dan+1)
    k = Y-(n-1)+1
    print(int(comb(n-1,k-1,(10**9+7),X)))
else:
    print(0)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, K: int, h: "List[int]"):
    dp=[2**60]*N
    dp[0]=0
    cost=[[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(i):
            cost[i][j]=abs(h[i]-h[j])

    for i in range(1,N):
        for st in range(max(0,i-K), i):
            dp[i]=min(dp[i], dp[st]+cost[i][st])
    print(dp[N-1])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, h)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, K: int, h: "List[int]"):
    dp=[2**60]*N
    dp[0]=0
    for i in range(1,N):
        for st in range(max(0,i-K), i):
            dp[i]=min(dp[i], dp[st]+abs(h[st]-h[i]))
    print(dp[N-1])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, h)

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

N,K=input().split()
N,K=[int(N),int(K)]
A=list(map(int,input().split()))
F=list(map(int,input().split()))

A=sorted(A)
F=sorted(F,reverse=True)
time=list()

for i in range(N):
   time.append(A[i]*F[i])

while(K>0):
   cmax=max(time)
   if(cmax>0):
      A[time.index(cmax)]-=1
      time[time.index(cmax)]=A[time.index(cmax)]*F[time.index(cmax)]
      K-=1
   elif(cmax==0):
      break

cmax=max(time)
print(cmax)

### FIXED CODE ###

N,K=input().split()
N,K=[int(N),int(K)]
A=list(map(int,input().split()))
F=list(map(int,input().split()))

A=sorted(A)
F=sorted(F,reverse=True)

goal_max=10**12+1
goal_min=0-1

while(goal_max-goal_min!=1):
   goal=(goal_max+goal_min)//2
   counter=0

   for i in range(N):
      counter+=max(0,A[i]-goal//F[i])

   if(counter<=K):
      goal_max=goal

   else:
      goal_min=goal
      
print(goal_max)
### BUGGY CODE ###

from heapq import *
x, y, z, k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a = sorted(a, reverse = True)
b = sorted(b, reverse = True)
c = sorted(c, reverse = True)

ans = [[-(a[0] + b[0] + c[0]), 1, 1, 1]]
heapify(ans)
log = [[[0] * z for i in range(y)] for j in range(x)]
log[0][0][0] = 1

d = [(1, 0, 0), (0, 1, 0), (0, 0, 1)]
for i in range(k):
    temp, s, t, u = heappop(ans)
    temp = temp * (-1)
    print(temp)
    for ds, dt, du in d:
        ns = s + ds
        nt = t + dt
        nu = u + du
        if not(0 <= ns <= x and 0 <= nt <= y and 0 <= nu <= z):continue
        if log[ns - 1][nt - 1][nu - 1]:continue
        heappush(ans, [-(a[ns - 1] + b[nt - 1] + c[nu - 1]), ns, nt, nu])
        log[ns - 1][nt - 1][nu - 1] = 1


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

c = sorted(c, reverse=True)
ab = []
for i in range(x):
    for j in range(y):
        temp = a[i] + b[j]
        ab.append(temp)

ab = sorted(ab, reverse=True)
ans = []
for i in range(z):
    for j in range(min(x * y, k)):
        temp = c[i] + ab[j]
        ans += [temp]
ans = sorted(ans, reverse=True)

for i in range(k):
    print(ans[i])
### BUGGY CODE ###

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

from collections import Counter
d=Counter(a)
f={}
for k,v in d.items():
    f[k]=v*(v-1)/2

ans={}
for k in f.keys():
    ans[k]=(d[k]-1)*(d[k]-2)/2
    for v in f.values():
        ans[k]+=v
    ans[k]-=f[k]

for i in range(n):
    print(int(ans[a[i]]))


### FIXED CODE ###

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

from collections import Counter
d=Counter(a)
f={}
for k,v in d.items():
    f[k]=v*(v-1)/2

ans={}
s=sum(f.values())
for k in f.keys():
    ans[k]=(d[k]-1)*(d[k]-2)/2 + s- f[k]

for i in range(n):
    print(int(ans[a[i]]))
### BUGGY CODE ###

#1:初期化
N,W = map(int,input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int,input().split())))
dp = [[0]*(W+1) for i in range(N+1)]

#print(wv)
#print(dp)
#2:初期値(元からゼロなので記述無し)

#3:dp実行部(貰うDP)
for i in range(1,N+1):
    for j in range(1,W+1):
        if wv[i-1][0] <= j:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]
        #print(i,j)
        #print(*dp,sep="\n")

#4:出力
print(dp[N][W])


### FIXED CODE ###

"""memo
    numpyでやるときは配列を一気に更新するが(numpy使いたくないのでやらない)，
    このやり方は後ろの方から更新することで後の更新に影響を与えない(考え方すごい)．
    (参考#9889377)
"""

import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = map(int,input().split())
    dp = [0]*(W+1)

    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = map(int,input().split())
        for i in range(W, w-1, -1):
            tmp = dp[i-w] + v
            if dp[i] < tmp:
                dp[i] = tmp
        #print(dp,sep="\n")

    #4:出力
    print(max(dp))

if __name__ == '__main__':
    main()