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

n, A = map(int,input().split())
x = list(map(int,input().split()))

dp = [list( [0 for _ in range(10**4)] for _ in range(n+1)) for _ in range(n+1)]
dp[0][0][0] = 1


for i in range(n):
    for k in range(n):
        for s in range(sum(x)+1):
                dp[i+1][k][s] += dp[i][k][s]
                dp[i+1][k+1][s+x[i]] += dp[i][k][s]

ans = 0
for i in range(1,n+1):
    ans += dp[n][i][A*i]
print(ans)



### FIXED CODE ###

n, A = map(int,input().split())
x = list(map(int,input().split()))

dp = [list( [0 for _ in range(3000)] for _ in range(n+1)) for _ in range(n+1)]
dp[0][0][0] = 1


for i in range(n):
    for k in range(n):
        for s in range(sum(x)+1):
                dp[i+1][k][s] += dp[i][k][s]
                dp[i+1][k+1][s+x[i]] += dp[i][k][s]

ans = 0
for i in range(1,n+1):
    ans += dp[n][i][A*i]
print(ans)
### BUGGY CODE ###

s = input()
c = 0
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        a = int(s[i:j])
        if a>2019 and a%2019==0:
            c+=1
print(c)

### FIXED CODE ###

s = input()
len_s = len(s)
pre = 0
mod = [0]*2019
mod[0]=1
x = 1
for i in range(len_s):
    pre = (x*int(s[len_s-i-1])+pre)%2019
    mod[pre] += 1
    x *= 10
    x %= 2019
print(sum([m*(m-1)//2 for m in mod]))
### BUGGY CODE ###

a=int(input())

d=list(map(int,input().split()))

sum=0

for i in range(a-1):
  for j in range(i+1,a):
    sum=sum+d[i]*d[j]

print(sum%(10**9+7))

### FIXED CODE ###

MOD = 10 ** 9 + 7

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

total=sum(alst)
sum=0

# for i in range(n-1):
#   for j in range(i+1,n):
#     sum=pow(sum+alst[i]*alst[j],1,MOD)

# print(sum)

for a in alst:
  sum = sum+a * (total - a)
  sum %= MOD

sum *= pow(2, MOD - 2, MOD)
sum %= MOD
print(sum)
### BUGGY CODE ###

n,k=map(int,input().split())
x=[0]*n
y=[0]*n
for i in range(n):
    x[i],y[i]=map(int,input().split())
ans=float('inf')
for i1 in range(n):
    for i2 in range(i1+1,n):
        for j1 in range(n):
            for j2 in range(j1+1,n):
                a,b=sorted([x[i1],x[i2]])
                c,d=sorted([y[j1],y[j2]])
                cnt=0
                for i in range(n):
                    if a<=x[i]<=b and c<=y[i]<=d:
                        cnt+=1
                if cnt>=k:
                    ans=min(ans,(b-a)*(d-c))
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
x=[0]*n
y=[0]*n
for i in range(n):
    x[i],y[i]=map(int,input().split())
ans=float('inf')
for i1 in range(n):
    for i2 in range(i1+1,n):
        for j1 in range(n):
            for j2 in range(j1+1,n):
                a,b=sorted([x[i1],x[i2]])
                c,d=sorted([y[j1],y[j2]])
                cnt=0
                for i in range(n):
                    if a<=x[i]<=b and c<=y[i]<=d:
                        cnt+=1
                if cnt>=k:
                    ans=min(ans,(b-a)*(d-c))
print(ans)
### BUGGY CODE ###

def inpl(): return [int(i) for i in input().split()]
def minisum(x):
    mini = x.index(min(x))
    d = len(x)
    if d == 0:
        return 0
    if d == 1:
        return x[0]
    result = 0
    if mini != 0:
        result += minisum(x[:mini])
    if mini != d-1:
        result += minisum(x[mini+1:])
    return result + (d-mini)*(mini+1)*x[mini]

N = input()
a = inpl()
print(minisum(a))

### FIXED CODE ###

def inpl(): return [int(i) for i in input().split()]
N = int(input())
a = inpl()
b = {a[i]: i for i in range(N)}

left = list(range(N+2))
right = list(range(N+2))

ans = 0
for i in range(N,0,-1):
    x = b[i]
    ans += i*(right[x]-x +1)*(x-left[x] +1)
    right[left[x] - 1] = right[x]
    left[right[x] + 1] = left[x]
print(ans)
### BUGGY CODE ###

import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
tree=[[] for i in range(n+1)]
for i in range(n-1):
    a,b,c=mp()
    tree[a].append((b,c))
    tree[b].append((a,c))
q,k=mp()
dist=[-1]*(n+1)
dist[k]=0
deq=deque()
deq.append(k)

while len(list(deq))>0:
    p=deq.popleft()
    for x,y in tree[p]:
        if dist[x]==-1:
            dist[x]=dist[p]+y
            deq.append(x)
for i in range(q):
    xi,yi=mp()
    print(dist[xi]+dist[yi])

### FIXED CODE ###

import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
tree=[[] for i in range(n+1)]
for i in range(n-1):
    a,b,c=mp()
    tree[a].append((b,c))
    tree[b].append((a,c))
q,k=mp()
dist=[-1]*(n+1)
dist[k]=0
deq=deque()
deq.append(k)

while len(deq):
    p=deq.popleft()
    for x,y in tree[p]:
        if dist[x]==-1:
            dist[x]=dist[p]+y
            deq.append(x)
for i in range(q):
    xi,yi=mp()
    print(dist[xi]+dist[yi])
### BUGGY CODE ###

N = int(input())
a = [list() for i in range(N+1)]
for i in range(N):
    b = int(input())
    a[i+1].append(b)

ans = 0
check = []
tmp = 1
check.append(tmp)
flag = False
while(1):
    tmp = a[tmp][0]
    ans += 1
    if tmp==2:
        flag = True
        break
    if tmp in check:
        break
    check.append(tmp)
    if ans >N:
        break
if flag:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

N = int(input())
a = []
for i in range(N):
    b = int(input())
    a.append(b)
ans = 0
tmp = 1
flag = False
while(1):
    tmp = a[tmp-1]
    ans += 1
    if tmp==2:
        flag = True
        break
    if ans > N:
        break
if flag:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

n = int(input())
A = [int(input()) for i in range(n)]

M = [1]
i = 1
while True:
  M.append(A[i-1])
  i = A[i-1]
  if 2 in M:
    print(len(M)-1)
    break
  else:
    for j in range(len(M)):
      if M.count(M[j]) > 1:
        print("-1")
        exit()
    

### FIXED CODE ###

n = int(input())

A = [int(input()) for i in range(n)]

A = [0] + A
count = 0
light = 1
if 2 not in A:
  print("-1")
  exit()
else:
  while light != 2 and count <= n:
    count += 1
    light = A[light] #A = [0] + Aとしているので，これでよい．light-1としなくてよい．

if count <= n:
  print(count)
else:
  print("-1")
### BUGGY CODE ###


from heapq import *
from collections import defaultdict

def Dijkstra(s, V, E):
    # https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95
    d = defaultdict(lambda:10**20)
    prev = defaultdict(lambda:None)
    d[s] = 0
    Q = []
    for v in V:
        heappush(Q, (d[v], v))
    while Q:
        x, u = heappop(Q)
        for v, y in E[u].items():
            alt = d[u] + y
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heappush(Q, (alt, v))
    return d, prev

N, M, S, T = [int(_) for _ in input().split()]
UVAB = [[int(_) for _ in input().split()] for i in range(M)]

Ea = defaultdict(dict)
Eb = defaultdict(dict)

for u, v, a, b in UVAB:
    Ea[u][v] = a
    Ea[v][u] = a
    Eb[u][v] = b
    Eb[v][u] = b
    
V = list(range(1, N + 1))

Da = Dijkstra(S, V, Ea)[0]
Db = Dijkstra(T, V, Eb)[0]

T = [None] * (N + 1)
t = 10**30

for i in range(N, 0, -1):
    r = Da[i] + Db[i]
    t = min(t, r)
    T[i] = t

ST = 10**15

for i in range(1, N + 1):
    print(ST-T[i])


### FIXED CODE ###


from heapq import *
from collections import defaultdict

def Dijkstra(s, N, E):
    # https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95
    d = [10**30] * (N + 1)
    d[s] = 0
    Q = []
    for v in range(1, N + 1):
        heappush(Q, (d[v], v))
    while Q:
        x, u = heappop(Q)
        for v, y in E[u].items():
            alt = d[u] + y
            if d[v] > alt:
                d[v] = alt
                heappush(Q, (alt, v))
    return d

N, M, S, T = [int(_) for _ in input().split()]
UVAB = [[int(_) for _ in input().split()] for i in range(M)]

Ea = defaultdict(dict)
Eb = defaultdict(dict)

for u, v, a, b in UVAB:
    Ea[u][v] = a
    Ea[v][u] = a
    Eb[u][v] = b
    Eb[v][u] = b
    
Da = Dijkstra(S, N, Ea)
Db = Dijkstra(T, N, Eb)

T = [None] * (N + 1)
t = 10**30

for i in range(N, 0, -1):
    r = Da[i] + Db[i]
    t = min(t, r)
    T[i] = t

ST = 10**15

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

N, Q = map(int, input().split())
s = input()

golems_in = dict([(i, 1) for i in range(N+2)])
golems_in[0] = 0
golems_in[N+1] = 0
alphabet_to_number = {}
for i in range(N):
    c = s[i]
    if not c in alphabet_to_number:
        alphabet_to_number[c] = [i + 1]
    else:
        alphabet_to_number[c].append(i + 1)

for i in range(Q):
    t, d = input().split()
    direction = 1 if d=="R" else -1
    n = len(alphabet_to_number[t]) if t in alphabet_to_number else 0
    for j in range(n):
        if(d == "R"):
            c = alphabet_to_number[t][n-j-1]
        else:
            c = alphabet_to_number[t][j]
        golems_in[c+direction] += golems_in[c]
        golems_in[c] = 0
print(N-golems_in[0]-golems_in[N+1])

### FIXED CODE ###

N, Q = map(int, input().split())
s = input()
td = [tuple(input().split()) for i in range(Q)]

def left_check(pos):
    nowpos = pos
    for t, d in td:
        if(d=="L" and t==s[nowpos]):
            nowpos -= 1
        elif(d=="R" and t==s[nowpos]):
            nowpos += 1
        if(nowpos == N):
            return False
        elif(nowpos == -1):
            return True
    return False

def right_check(pos):
    nowpos = pos
    for t, d in td:
        if(d=="L" and t==s[nowpos]):
            nowpos -= 1
        elif(d=="R" and t==s[nowpos]):
            nowpos += 1
        if(nowpos == N):
            return False
        elif(nowpos == -1):
            return True
    return True

def nibun(l, h, func):
    low = l
    high = h
    mid = (l+h)//2
    while low <= high:
        x = func(mid)
        if(x):
            low = mid+1
        else:
            high = mid-1
        mid = (low+high)//2
    return mid

print(nibun(0, N-1, right_check)-nibun(0, N-1, left_check))
### BUGGY CODE ###

H, W=map(int, input().split())
A=[list(map(int, input().split())) for i in range(H)]
B=[list(map(int, input().split())) for i in range(H)]
AB=[[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]

from collections import defaultdict
G=[[defaultdict(int) for j in range(W)] for i in range(H)]
G[0][0][AB[0][0]]+=1

for i in range(1, W):
  ks=G[0][i-1].keys()
  for k in ks:
    G[0][i][abs(k+AB[0][i])]+=1
    G[0][i][abs(k-AB[0][i])]+=1
    
for i in range(1, H):
  ks=G[i-1][0].keys()
  for k in ks:
    G[i][0][abs(k+AB[i][0])]+=1
    G[i][0][abs(k-AB[i][0])]+=1

from collections import deque

def f(data):
  i=data[0]
  j=data[1]
  tmp=AB[i][j]
  
  ks=G[i-1][j].keys()
  for k in ks:
    G[i][j][abs(k+tmp)]+=1
    G[i][j][abs(k-tmp)]+=1
    
  ks=G[i][j-1].keys()
  for k in ks:
    G[i][j][abs(k+tmp)]+=1
    G[i][j][abs(k-tmp)]+=1
    
  if i<H-1:
    q.append([i+1, j])
  if j<W-1:
    q.append([i, j+1])
    
q=deque()
q.append([1, 1])
while len(q)>0:
  data=q.popleft()
  f(data)
  
print(min(G[-1][-1].keys()))

### FIXED CODE ###

H, W=map(int, input().split())
A=[list(map(int, input().split())) for _ in range(H)]
B=[list(map(int, input().split())) for _ in range(H)]
AB=[[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]

G=[[[0]*(80*162) for j in range(W)] for i in range(H)]
G[0][0][AB[0][0]]=1
sumi=[[0]*W for i in range(H)]
  
from collections import deque

def f(data):
  i=data[0]
  j=data[1]
  owari=(i+j+1)*80+1
  if i<H-1 and j<W-1:
    for k in range(owari):
      if G[i][j][k]>0:
        G[i+1][j][k+AB[i+1][j]]=1
        G[i+1][j][abs(k-AB[i+1][j])]=1
        G[i][j+1][k+AB[i][j+1]]=1
        G[i][j+1][abs(k-AB[i][j+1])]=1
    if sumi[i+1][j]==0:
      q.append([i+1, j])
      sumi[i+1][j]=1
    if sumi[i][j+1]==0:
      q.append([i, j+1])
      sumi[i][j+1]=1
  elif i>=H-1 and j<W-1:
    for k in range(owari):
      if G[i][j][k]>0:
        G[i][j+1][k+AB[i][j+1]]=1
        G[i][j+1][abs(k-AB[i][j+1])]=1
    if sumi[i][j+1]==0:
      q.append([i, j+1])
      sumi[i][j+1]=1
  elif i<H-1 and j>=W-1:
    for k in range(owari):
      if G[i][j][k]>0:
        G[i+1][j][k+AB[i+1][j]]=1
        G[i+1][j][abs(k-AB[i+1][j])]=1
    if sumi[i+1][j]==0:
      q.append([i+1, j])
      sumi[i+1][j]=1
    
q=deque()
q.append([0, 0])
while len(q)>0:
  data=q.popleft()
  f(data)
  
out=0
while G[-1][-1][out]==0:
  out+=1
print(out)
### BUGGY CODE ###

n = int(input())
s = str(input())
d = []
for i in range(0,n):
    list_1 = s[0:i]
    list_2 = s[i+1:n]
    c = list_1.count('W') + list_2.count('E')
    d.append(c)
print(min(d))

### FIXED CODE ###

n = int(input())
s = str(input())

a = [(0,0) for _ in range(n + 1)]
b = []
for i in range(n):
    if s[i] == "W":
        a[i+1] = (a[i][0] + 1,a[i][1])
    else:
        a[i+1] = (a[i][0],a[i][1] + 1)
    b.append(a[i+1][1]-a[i+1][0])
    
ans = s[0:b.index(max(b))].count('W') + s[b.index(max(b))+1:].count('E')
print(ans)
### BUGGY CODE ###

X = input().strip()
i = 0
while i<len(X):
    if X[i:i+2]=="ST":
        X = X[:i]+X[i+2:]
        i -= 1
    else:
        i += 1
print(len(X))

### FIXED CODE ###

X = input().strip()
cnt = 0
cntmax = 0
for i in range(len(X)):
    if X[i]=="T":
        cnt += 1
        cntmax = max(cntmax,cnt)
    else:
        cnt -= 1
print(cntmax*2)
### BUGGY CODE ###

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

class segtree:
    x_unit=0 # 要素として入れられる最大値
    def __init__(self,N):
        self.n=(1<<len(bin(N-1)[2:]))
        self.x=[self.x_unit]*(2*self.n)

    def build(self, seq):
        for i,j in enumerate(seq, start=self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = 0
            # セグ木トーナメント表の左右を比較
            # 例えばn=8の時、seq[4]はx[12]に、seq[5]はx[13]に入っている
            # さらにx[14]とx[15]の間に来るのはx[7]、x[12]とx[13]の間に来るのはx[6]

    def fold(self,l,r): # 区間[l, r)値に+1 
        l+=self.n
        r+=self.n-1
        while l<r:
            if l%2==1: # lが奇数
                self.x[l]+=1
                l+=1 # 偶数に調節
            if r%2==0: # rが偶数
                self.x[r]+=1
                r-=1 # 開区間なので1個前は奇数番目の要素
            l //= 2
            r //= 2
        if l==r:
            self.x[l]+=1
        #print(self.x)
    def get(self,i): # seq[i]に対する値を取得 
        i+=self.n
        ret=self.x[i]
        while i>1:
            i //= 2
            ret+=self.x[i]
        return ret

for z in range(k):
    seq=[0]*n
    q=[(max(0, i-a[i]), min(n,i+a[i]+1)) for i in range(n)]
    seg=segtree(n)
    seg.build(seq)
    for i in range(n):
        l,r=q[i]
        seg.fold(l,r)
    ans=[]
    for i in range(n):
        ans.append(seg.get(i))
        
    a=ans+[]
print(*a)

### FIXED CODE ###

n,k=map(int, input().split())
a=list(map(int, input().split()))
from itertools import accumulate
for _ in range(k):
    new=[0]*n
    for i in range(n):
        j=a[i]
        l=max(0,i-j)
        r=min(n-1,i+j)
        new[l]+=1
        if r+1<n:
            new[r+1]-=1
    new=list(accumulate(new))
    a=new
    if all([i==n for i in a]):
        break
print(*a)
### BUGGY CODE ###

from collections import deque

s = deque(input())
q = int(input())

for _ in range(q):
  Q = [x for x in input().split()]
  if Q[0] == '1':
    s.reverse()
  else:
    if Q[1] == '1':
      s.appendleft(Q[2])
    else:
      s.append(Q[2])

print('' . join(s))

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())
flg = 0

for _ in range(q):
  Q = [x for x in input().split()]
  if Q[0] == '1':
    flg += 1
  else:
    if (Q[1] == '1' and flg%2==0) or (Q[1] == '2' and flg%2==1):
      s.appendleft(Q[2])
    else:
      s.append(Q[2])
if flg%2==1:
  s.reverse()

print('' . join(s))
### BUGGY CODE ###

n,m = map(int,input().split())
uv = [[] for _ in range(n)]
for i in range(m):
  u,v = map(lambda x:int(x)-1,input().split())
  uv[u].append(v)
s,t = map(lambda x:int(x)-1,input().split())
time = 0
now = {s}
flag = 0
for _ in range(n):
  time += 1
  tmp = set()
  for x in now:
    for y in uv[x]:
      tmp.add(y)
  now = tmp
  time += 1
  tmp = set()
  for x in now:
    for y in uv[x]:
      tmp.add(y)
  now = tmp
  time += 1
  tmp = set()
  for x in now:
    for y in uv[x]:
      tmp.add(y)
  now = tmp
  if t in now:
    flag = 1
    break
if flag == 1:
  print(time//3)
else:
  print(-1)

### FIXED CODE ###

n,m = map(int,input().split())
pst = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  pst[a].append(b)
s,t = map(int,input().split())
s -= 1
t -= 1
cnt = [[0,0,0] for _ in range(n)]
cnt[s][0] = 1
now = [s]
time = 0
while now:
  time += 1
  last = now
  now = []
  for x in last:
    for y in pst[x]:
      if cnt[y][time%3] == 0:
        cnt[y][time%3] = 1
        now.append(y)
  #print(time,cnt,now)
  if cnt[t][0] == 1:
    print(time//3)
    break
else:
  print(-1)
### BUGGY CODE ###

a, b, m = input().split()
a, b, m = int(a), int(b), int(m)
a_values = input().split()
b_values = input().split()
m_values = {}
for i in range(m):
    m_values[i] = input().split()

min = int(a_values[int(m_values[0][0])-1]) + int(b_values[int(m_values[0][1])-1]) - int(m_values[0][2])
for i in range(1, m):
    now = int(a_values[int(m_values[i][0])-1]) + int(b_values[int(m_values[i][1])-1]) - int(m_values[i][2])
    if min > now:
        min = now
for i in a_values:
    for j in b_values:
        now = int(i) + int(j)
        if min > now:
            min = now
print(min)

### FIXED CODE ###

a, b, m = input().split()
a, b, m = int(a), int(b), int(m)
a_values = input().split()
b_values = input().split()
m_values = {}
for i in range(m):
    m_values[i] = input().split()

min_num = int(a_values[int(m_values[0][0]) - 1]) + int(b_values[int(m_values[0][1]) - 1]) - int(m_values[0][2])
for i in range(1, m):
    now = int(a_values[int(m_values[i][0]) - 1]) + int(b_values[int(m_values[i][1]) - 1]) - int(m_values[i][2])
    if min_num > now:
        min_num = now
now = int(min(a_values)) + int(min(b_values))
if min_num > now:
    print(now)
else:
    print(min_num)
### BUGGY CODE ###

n,m=map(int, input().split())
h = [list(map(str,input().split())) for _ in range(m)]
# print(h)
for i in range(m):
    h[i][0] = int(h[i][0])
l=[]
import numpy as np
p = np.zeros(n)
for i in range(m):
    if h[i][0] not in l:
        if h[i][1] == 'AC':
            l.append(h[i][0])
        else:
            p[h[i][0]-1] += 1
ansnum = len(l)
penalty = 0
for i in l:
    penalty += p[i-1]

print(ansnum,int(penalty))

### FIXED CODE ###

n,m=map(int, input().split())
h = [list(map(str,input().split())) for _ in range(m)]
# print(h)
for i in range(m):
    h[i][0] = int(h[i][0])
l=set()
penalty = 0
import numpy as np
p = np.zeros(n)
for i in range(m):
    if h[i][0] not in l:
        if h[i][1] == 'AC':
            l.add(h[i][0])
            penalty += p[h[i][0]-1]
        else:
            p[h[i][0]-1] += 1
ansnum = len(l)

# for i in l:
#     penalty += p[i-1]

print(ansnum,int(penalty))
### BUGGY CODE ###

a,b = map(int,input().split())
yakusuu = []
ans = 1
for i in range (2,min(a,b)+1):
         if a % i == 0 and b% i == 0:
                  yakusuu.append(i)
for j in range(len(yakusuu)):
         for k in range(2,yakusuu[j]):
                  if yakusuu[j] % k == 0:
                           break
         else:
                  ans += 1
print(ans)


### FIXED CODE ###

aa,bb = map(int,input().split())
n = min(aa,bb)
b = max(aa,bb)
ans = 1
arr = []
temp = n
for i in range(2, int(-(-n**0.5//1))+1):
         if temp%i==0:
                  cnt=0
                  while temp%i==0:
                           cnt+=1
                           temp //= i
                  arr.append(i)

if temp!=1:
         arr.append(temp)

if arr==[] and n != 1:
         arr.append(n)

for j in range(len(arr)):
         if b % arr[j] == 0:
                  ans += 1
print (ans)
### BUGGY CODE ###

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):
        for k in range(j+1,n):
            if l[k]<l[j]+l[i]:
                ans += 1

            
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)
ans = 0
for i in range(n-2):
    j = i+1
    k = n-1
    while j < k:
        if l[i]<l[j]+l[k]:
            ans += k-j
            j += 1
        else:
            k -= 1
print(ans)
### BUGGY CODE ###

import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = list(map(int, input().split()))
ans = []
for i in range(1,n+1):
    ans.append(A.index(i)+1)
print(*ans)

### FIXED CODE ###

import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
A=[(e,i) for i,e in enumerate(list(map(int,input().split())))]
#print(A)
A.sort(key=lambda tup: tup[0])
#print(A)
for e,i in A:
    print(i+1)
### BUGGY CODE ###

def solve():
        from itertools import permutations
        N, M, R = map(int, input().split())
        rs = map(lambda x: int(x) - 1, input().split())
        dist, ans = [[float("inf") for _ in range(N)] for _ in range(N)], float("inf")
        for _ in range(M):
            v1, v2, d = map(int, input().split())
            dist[v1-1][v2-1] = dist[v2-1][v1-1] = d
        for i in range(N):
            dist[i][i] = 0
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        for r in permutations(rs):
            t = 0
            for i in range(R-1):
                t += dist[r[i]][r[i+1]]
            ans = min(t, ans)
        print(ans)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

from itertools import permutations
N, M, R = map(int, input().split())
rs = map(lambda x: int(x) - 1, input().split())
dist = [[10**9 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    v1, v2, d = map(int, input().split())
    dist[v1-1][v2-1] = dist[v2-1][v1-1] = d
for i in range(N):
    dist[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ans = 10**9
for r in permutations(rs):
    t = 0
    for i in range(R-1):
        t += dist[r[i]][r[i+1]]
        if t > 10**9:
            break
    ans = min(t, ans)
print(ans)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
for i in range(N):
  B = A[:]
  del B[i]
  print(max(B))

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
A_max = max(A)
i = A.index(A_max)
del A[i]
B_max = max(A)
for j in range(N):
  if j == i:
    print(B_max)
  else:
    print(A_max)
### BUGGY CODE ###

from heapq import *
def abc144c():
  n,k=map(int,input().split())
  a=sorted(list(map(int,input().split())))
  f=sorted(list(map(int,input().split())))[::-1]
  q=[] 
  for i,j in zip(a,f):
    heappush(q,(-i*j,j))
  kk=min(k,10**12)
  for i in range(kk):
    tmp,key=heappop(q)
    heappush(q,(tmp+key,key))
  ans,key=heappop(q)
  if -ans>=0:
    print(-ans)
  else:
    print(0)
abc144c()

### FIXED CODE ###

n,k=map(int,input().split())
abilities=sorted(list(map(int,input().split())))
foods=sorted(list(map(int,input().split())),reverse=True)

if sum(abilities)<=k:
  print(0)
  exit()
  
def check(score):
  ret=0
  for a,f in zip(abilities,foods):
    ret+=max(0,(a*f-score+f-1)//f)
  return ret<=k

ok=10**12+1
ng=0
for _ in range(50):
  mid=(ok+ng)//2
  if check(mid):
    ok=mid
  else:
    ng=mid
print(ok)