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

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

#sum_a = sum(A)
x = 0
ans = 1000000000000000

for i in range(N-1):
        x += A[i]
        ans = min(ans, abs(2*x-sum(A)))

print(ans)

### FIXED CODE ###

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

sum_a = sum(A)
x = 0
ans = 1000000000000000

for i in range(N-1):
        x += A[i]
        ans = min(ans, abs(2*x-sum_a))

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

n,m=map(int,input().split())
ans=list(0 for _ in range(n))
a=list(int(input())for _ in range(m))
count=list(0 for _ in range(n+1))
ans=0
if n==1:
    ans=1
else:
    if 1 not in a:
        count[1]=1
    if 2 not in a:
        count[2]=count[1]+1
    for i in range(3,n+1):
        if i not in a:
            count[i]=count[i-1]+count[i-2]
            
    ans=count[n]
print(ans%(10**9+7))
           

### FIXED CODE ###

n,m=map(int,input().split())
flag=list(1 for _ in range(n+1))
count=list(0 for _ in range(n+1))
ans=0
for i in range(m):
    x=int(input())
    flag[x]=0

if n==1:
    ans=1
else:
    if flag[1]==1:
        count[1]=1
    if flag[2]==1:
        count[2]=count[1]+1
    for i in range(3,n+1):
        if flag[i]==1:
            count[i]=count[i-1]+count[i-2]
            
    ans=count[n]
print(ans%(10**9+7))
### BUGGY CODE ###

import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense

input = sys.stdin.readline


def main():
    N = int(input())
    edge = [[0] * N for j in range(N)]
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        edge[a - 1][b - 1] = c
        edge[b - 1][a - 1] = c

    G = csgraph_from_dense(edge, null_value=0)
    d = bellman_ford(G)

    Q, K = [int(x) for x in input().split()]
    for _ in range(Q):
        x, y = [int(x) for x in input().split()]
        print(int(d[x - 1][K - 1] + d[K - 1][y - 1]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

d = []
ABC = []

sys.setrecursionlimit(10 ** 8)


def solve(i, dis):
    global d
    global ABC
    d[i] = dis

    for n, c in ABC[i]:
        if d[n] == -1:
            solve(n, dis + c)


def main():
    N = int(input())
    global ABC
    ABC = [[] for _ in range(N + 1)]
    global d
    d = [-1] * (N + 2)
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        ABC[a - 1].append([b - 1, c])
        ABC[b - 1].append([a - 1, c])

    Q, K = [int(x) for x in input().split()]

    solve(K - 1, 0)

    for _ in range(Q):
        x, y = [int(x) for x in input().split()]
        print(d[x - 1] + d[y - 1])


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

def c_alternating_path(H, W, Grid):
    from collections import deque
    ans = 0
    for h in range(H):
        for w in range(W):
            if Grid[h][w] == '#':
                is_visit = [[False] * W for _ in range(H)]
                q = deque([(h, w)])
                while q:
                    row, col = q.pop()
                    if is_visit[row][col]:
                        continue
                    is_visit[row][col] = True
                    if Grid[row][col] == '.':
                        ans += 1
                    for dr, dc in zip((1, 0, -1, 0), (0, 1, 0, -1)):
                        nr, nc = row + dr, col + dc
                        if (0 <= nr < H and 0 <= nc < W
                                and Grid[row][col] != Grid[nr][nc]
                                and not is_visit[nr][nc]):
                            q.appendleft((nr, nc))
    return ans

H, W = [int(i) for i in input().split()]
Grid = [input() for _ in range(H)]
print(c_alternating_path(H, W, Grid))

### FIXED CODE ###

def c_alternating_path(H, W, Grid):
    from itertools import product
    from collections import deque

    ans = 0
    is_visited = [[False] * W for _ in range(H)]
    for h, w in product(range(H), range(W)):
        if Grid[h][w] == '#' and not is_visited[h][w]:
            count_white, count_black = 0, 0
            q = deque([(h, w)])
            while q:
                row, col = q.popleft()
                if is_visited[row][col]:
                    continue

                is_visited[row][col] = True
                if Grid[row][col] == '#':
                    count_black += 1
                else:
                    count_white += 1

                for dr, dc in [(0, -1), (1, 0), (0, 1), (-1, 0)]:
                    nr, nc = row + dr, col + dc
                    if (0 <= nr < H and 0 <= nc < W
                        and Grid[row][col] != Grid[nr][nc]
                            and not is_visited[nr][nc]):
                        q.append((nr, nc))
            ans += count_black * count_white
    return ans

H, W = [int(i) for i in input().split()]
Grid = [input() for _ in range(H)]
print(c_alternating_path(H, W, Grid))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7

a.sort(reverse = True)

l = len(bin(a[0])[2:])

ans  = 0
for b in range(l):
    count_1 = 0
    count_0 = 0
    for i in range(n):
        if (a[i] >> b) & 1:
            count_1 += 1
        else:
            count_0 += 1
    ans += (count_1 * count_0 * 2**b)%mod


print(ans%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7

a.sort(reverse = True)

#l = len(bin(a[0])[2:])

ans  = 0
for b in range(60+1):
    count_1 = 0
    count_0 = 0
    for i in range(n):
        if (a[i] >> b) & 1:
            count_1 += 1
        else:
            count_0 += 1
    count_1 %= mod
    count_0 %= mod
    ans += (count_1 * count_0 * pow(2,b,mod))%mod


print(ans%mod)
### BUGGY CODE ###

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

A.sort()
F.sort(reverse=True)

max_a = max(A)
max_f = max(F)

left = 0
right = max_a * max_f

while left <= right:
    x = (left + right) // 2

    sum_ = 0
    for i in range(N):
        if A[i] * F[i] > x:
            sum_ += (A[i] - int(x / F[i]))

    if sum_ > K:
        left = x + 1

    if sum_ <= K:
        right = x - 1


print(left)


### FIXED CODE ###

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

A.sort()
F.sort(reverse=True)

max_a = max(A)
max_f = max(F)

left = 0
right = max_a * max_f

while left <= right:
    x = (left + right) // 2

    sum_ = 0
    for i in range(N):
        if A[i] * F[i] > x:
            sum_ += (A[i] - int(x / F[i]))

    if sum_ > K:
        left = x + 1

    if sum_ <= K:
        right = x - 1


print(left)
### BUGGY CODE ###

s = input()
x, y = map(int,input().split())

s = s.split("T")
s = [len(e) for e in s]
a = []
b = []
for i, s in enumerate(s):
    if i % 2 == 0:
        a.append(s)
    else:
        b.append(s)

x -= a.pop(0)
ans = True

dpx = [[False] * (2*abs(x) + 1) for _ in range(len(a) + 1)]
dpx[0][abs(x)] = True

for i in range(1,len(a)+1):
    for j in range(2*abs(x) + 1):
        if j + a[i-1] < 2*abs(x) + 1:
            dpx[i][j] |= dpx[i-1][j+a[i-1]]
        if j - a[i-1] >= 0:
            dpx[i][j] |= dpx[i-1][j-a[i-1]]

ans &= dpx[len(a)][x+abs(x)]

dpy = [[False] * (2*abs(y) + 1) for _ in range(len(b) + 1)]
dpy[0][abs(y)] = True

for i in range(1, len(b) + 1):
    for j in range(2*abs(y) + 1):
        if j + b[i-1] < 2*abs(y) + 1:
            dpy[i][j] |= dpy[i-1][j+b[i-1]]
        if j - b[i-1] >= 0:
            dpy[i][j] |= dpy[i-1][j-b[i-1]]

ans &= dpy[len(b)][y+abs(y)]

if ans:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input()
x, y = map(int,input().split())

s = s.split("T")
s = [len(e) for e in s]
a = []
b = []
for i, s in enumerate(s):
    if i % 2 == 0:
        a.append(s)
    else:
        b.append(s)

x -= a.pop(0)
ans = True

dpx = [[False] * (2*abs(x) + 1) for _ in range(len(a) + 1)]
dpx[0][abs(x)] = True

for i in range(1,len(a)+1):
    for j in range(2*abs(x) + 1):
        if j + a[i-1] < 2*abs(x) + 1:
            dpx[i][j] |= dpx[i-1][j+a[i-1]]
        if j - a[i-1] >= 0:
            dpx[i][j] |= dpx[i-1][j-a[i-1]]

ans &= dpx[len(a)][x+abs(x)]

dpy = [[False] * (2*abs(y) + 1) for _ in range(len(b) + 1)]
dpy[0][abs(y)] = True

for i in range(1, len(b) + 1):
    for j in range(2*abs(y) + 1):
        if j + b[i-1] < 2*abs(y) + 1:
            dpy[i][j] |= dpy[i-1][j+b[i-1]]
        if j - b[i-1] >= 0:
            dpy[i][j] |= dpy[i-1][j-b[i-1]]

ans &= dpy[len(b)][y+abs(y)]

if ans:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

s = input()
num = len(s)

kb = []

for i in range(num):
    kb.append(s[i])

mae = 0
usi = num-1

while mae < usi:
    #print(i)
    if s[mae] != s[usi]:
        if s[mae] == 'x':
            kb.append('x')
            mae += 1
        elif s[usi] == 'x':
            kb.insert(mae,'x')
            usi -= 1
        else:
            print(-1)
            exit()
    else:
        mae += 1
        usi -= 1

print(len(kb)-num)

### FIXED CODE ###

s = input()
num = len(s)

kb = []

for i in range(num):
    kb.append(s[i])

mae = 0
usi = num-1
ans = 0

while mae < usi:
    #print(i)
    if s[mae] != s[usi]:
        if s[mae] == 'x':
            #kb.append('x')
            ans += 1
            mae += 1
        elif s[usi] == 'x':
            #kb.insert(mae,'x')
            ans += 1
            usi -= 1
        else:
            print(-1)
            exit()
    else:
        mae += 1
        usi -= 1

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

import sys
input = sys.stdin.readline
N , W = map(int , input().split())
weight = []
value = []
for _ in range(N):
    w , v = map(int , input().split())
    weight.append(w)
    value.append(v)
 
def knapsack():
    dp = [[-1] * (W + 1) for _ in range(N + 1)]
    def solve(i,w):
        if dp[i][w] != -1:
            return dp[i][w]
        if N == i:
            ret_val = 0
        elif w - weight[i] < 0:
            ret_val = solve(i + 1,w)
        else:
            ret_val = max(solve(i + 1, w), solve(i + 1,w - weight[i]) + value[i])
        dp[i][w] = ret_val
        return dp[i][w]
    solve(0,W)
    #print(dp)
    return max(dp[0])
 
if __name__ == "__main__":
    print(knapsack())

### FIXED CODE ###

import numpy as np
N , W = map(int, input().split())
goods = np.array([list(map(int , input().split())) for _ in range(N)])
dp = np.zeros((N + 1 , W + 1) , dtype = np.int)

for i in range(0,N):
    w, v = goods[i,:]
    dp[i + 1, w:] = np.maximum(dp[i,w:] , dp[i,:-w] + v)
    dp[i + 1, :] = np.maximum(dp[i + 1,:],dp[i,:])
print(int(dp[N,W]))
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = [list(input()) for i in range(H)]
 
from collections import deque
 
q = deque([(CH-1, CW-1)])
 
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            S[i][j] = 10**7
S[CH-1][CW-1] = 0

while q:
    h, w = q.popleft()
    for dh, dw in directions:
        if 0 <= h+dh < H and 0 <= w+dw < W and S[h+dh][w+dw] != "#":
            if S[h+dh][w+dw] > S[h][w]:
                S[h+dh][w+dw] = S[h][w]
                q.append((h+dh, w+dw))
    for wh, ww in warp:
        if 0 <= h+wh < H and 0 <= w+ww < W and S[h+wh][w+ww] != "#":
            if S[h+wh][w+ww] > S[h][w] + 1:
                S[h+wh][w+ww] = S[h][w] + 1
                q.append((h+wh, w+ww))
 
if S[DH-1][DW-1] == 10**7:
    print(-1)
else:
    print(S[DH-1][DW-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

import sys
def input():
    return sys.stdin.readline()[:-1]

H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = [list(input()) for i in range(H)]
 
from collections import deque
 
q = deque([(CH-1, CW-1)])
 
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
        (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
        (0, -2), (0, -1), (0, 1), (0, 2), 
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            S[i][j] = 10**7
S[CH-1][CW-1] = 0

while q:
    h, w = q.popleft()
    for wh, ww in warp:
        if 0 <= h+wh < H and 0 <= w+ww < W and S[h+wh][w+ww] != "#":
            if (wh, ww) in directions:
                if S[h+wh][w+ww] > S[h][w]:
                    S[h+wh][w+ww] = S[h][w]
                    q.appendleft((h+wh, w+ww))
            else:
                if S[h+wh][w+ww] > S[h][w] + 1:
                    S[h+wh][w+ww] = S[h][w] + 1
                    q.append((h+wh, w+ww))

if S[DH-1][DW-1] == 10**7:
    print(-1)
else:
    print(S[DH-1][DW-1])
### BUGGY CODE ###

n,m = map(int,input().split())
list = [[int(i) for i in input().split()] for i in range(n)]
list = sorted(list)
dp = [ [0 for i in range(m+1)] for j in range(n+1)]

for i in range(1,n+1):
  for j in range(1,m+1):
    if list[i-1][0] <= j:
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+list[i-1][1])
    else:
      dp[i][j] = dp[i-1][j]
print(dp[n][m])

### FIXED CODE ###

import heapq as hp
import sys
def input():
    return sys.stdin.readline()

n,m = map(int,input().split())
list = [[int(i) for i in input().split()] for i in range(n)]
temp = [0]
ans = 0
a = 0
j = 0
list = sorted(list)

for i in range(1,1+m):
  for j in range(a,len(list)):
    if list[j][0] == i:
      hp.heappush(temp,-list[j][1])
    else:
      a = j
      break
  if len(temp) > 0:
    ans -= hp.heappop(temp)
print(ans)
### BUGGY CODE ###

N, M = [int(item) for item in input().split()]
A = [int(item) for item in input().split()]
B = []
C = []
A.sort()
for i in range(M):
  b, c = [int(item) for item in input().split()]
  B.append(b)
  C.append(c)
 
B = [x for y, x in sorted(zip(C, B))]
C = sorted(C)

P = []
for idx in range(len(B)):
  P.extend([C[idx]]*B[idx])
 
res = 0
# print (A)
i = 0
while i < N:
  # print (A[i],P)
  if len(P)>0:
    p = P.pop()
  else:
    p=0
  if A[i] < p:
    res += p
  else:
    res += A[i]
  i+=1
  
print (res)

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1],reverse=True)
for b,c in bc:
    a.extend([c]*b)
    if len(a)>2*n:
        break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

a,b = map(int,input().split())
A = [i for i in range(a,b+1)]
if a > 0:
    print('Positive')
elif 0 in A:
    print('Zero')
elif len(A)%2 == 0:
    print('Positive')
else:
    print('Negative')

### FIXED CODE ###

a,b = map(int,input().split())
if a > 0:
    print('Positive')
elif b > 0:
    print('Zero')
elif (b-a+1)%2 == 0:
    print('Positive')
else:
    print('Negative')
### BUGGY CODE ###

import numpy as np

N = int(input())
check_arr = np.zeros([N, 26])

for i in range(N):
    word = input()
    for j in range(len(word)):
        check_arr[i, ord(word[j])-ord('a')] += 1
count = 0
for l in range(N):
    for m in range(l+1, N):
        if (check_arr[l] - check_arr[m] == np.zeros(26)).all():
            count += 1
            
print(count)

### FIXED CODE ###

N = int(input())
s_list = [input() for i in range(N)]

ans = 0
word= {}

for j in s_list:
#     a = ''.join(sorted(list(j)))
    a = ''.join(sorted(j))
    if a in word:
        ans += word[a]
        word[a] += 1
    else:
        word[a] = 1
    
print(ans)
### BUGGY CODE ###

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

max_length = 0

for i in range(1, n-1):
    tmp_len = 0
    for c1, c2 in zip(s[0:n-i:], s[i::]):
        if c1 == c2:
            tmp_len += 1
        else:
            tmp_len = 0

        max_length = max(max_length, tmp_len)
        if tmp_len >= i:
            break

print(max_length)


### FIXED CODE ###

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

max_length = 0

for i in range(1, n-1):
    tmp_len = 0
    for c1, c2 in zip(s[0:n-i:], s[i::]):
        if c1 == c2:
            tmp_len += 1
        else:
            tmp_len = 0

        max_length = max(max_length, tmp_len)
        if tmp_len >= i:
            break

print(max_length)
### BUGGY CODE ###

N=int(input())
print(0)
S0 = input()[0]
if S0=="V":exit()
print(N-1)
if input()[0]=="V":exit()

r,l=0,N-1
while r-l>1:
    med=(r+l)//2
    print(med)
    S1=input()[0]
    if S1=="V":
        exit()
    elif (med%2==0 and S1==S0) or (med%2==1 and S1!=S0):
        r=med
    else:
        l=med
print(l)


### FIXED CODE ###

N=int(input())
print(0)
S0 = input()[0]
if S0=="V":exit()
print(N-1)
if input()[0]=="V":exit()

l,r=0,N-1
while r-l>1:
    med=(r+l)//2
    print(med)
    S1=input()[0]
    if S1=="V":
        exit()
    elif (med%2==0 and S1==S0) or (med%2==1 and S1!=S0):
        l=med
    else:
        r=med
print(r)
### BUGGY CODE ###

A, B, N = list(map(int,input().split()))
t= list()
for x in range(N+1):
  S= A*x//B
  T=x//B
  ans= S-A*T
  t.append(ans)

print(max(t))



### FIXED CODE ###

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

x = min(N,B-1)
print(A*x//B)
### BUGGY CODE ###

import sys,math
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202007_2nd/C_input.txt")
else:
    f=sys.stdin
# Find the number of triples of integers (x,y,z) such that
# (x+y)**2 + (y+z)**2 + (x+z)**2 = 2*N
N=int(f.readline().strip())
for _ in range(N):
    A=(_+1)*2
    I=int(math.sqrt(A))
    cnt=0
    for __ in range(I):
        A2=A-((__+1)**2)
        if A2<=0:
            break
        I2=int(math.sqrt(A2))
        for ___ in range(I2):
            A3=A2-((___+1)**2)
            if A3<=0:
                break
            I3=int(math.sqrt(A3))
            for ____ in range(I3):
                if ((__+___+2)**2)+((___+____+2)**2)+((__+____+2)**2)==A:
                    cnt+=1
                    break
    print(cnt)
f.close()

### FIXED CODE ###

import sys,math
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202007_2nd/C_input.txt")
else:
    f=sys.stdin
# Find the number of triples of integers (x,y,z) such that
# (x+y)**2 + (y+z)**2 + (x+z)**2 = 2*N
N=int(f.readline().strip())
ans=[0 for _ in range(N)]
I=int(math.sqrt(N))
for __ in range(I):
    A2=N-((__+1)**2)
    if A2<=0:
        break
    I2=int(math.sqrt(A2))
    for ___ in range(I2):
        A3=A2-((___+1)**2)
        if A3<=0:
            break
        I3=int(math.sqrt(A3))
        for ____ in range(I3):
            tmp=((__+___+2)**2)+((___+____+2)**2)+((__+____+2)**2)
            if tmp<=2*N:
                ans[int(tmp/2)-1]+=1
            else:
                break
for _ in range(N):
    print(ans[_])
f.close()
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0

for r in range(min(3000, 3000 // R) + 1):
    for g in range(min(3000, 3000 // G) + 1):
        v = R * r + G * g
        if N >= v and (N - v) % B == 0:
            ans += 1

print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0

for r in range(min(3000, 3000 // R) + 1):
    if R * r <= N:
        for g in range(min(3000, 3000 // G) + 1):
            v = R * r + G * g
            if N >= v and (N - v) % B == 0:
                ans += 1

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

n=int(input())
p=list(map(int,input().split()))
ct=1
i=1
maxn=p.index(i)
while True:
    if maxn==0:
        break
    p=p[0:maxn]
    i+=1
    maxn=p.index(min(p))
    ct+=1
print(ct)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
ct=1
minn=p[0]
for i in range(1,n):
    if minn==1:
        #ct+=1
        break
    elif minn>p[i]:
        minn=p[i]
        ct+=1
print(ct)
### BUGGY CODE ###

import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n = int(input())

res = 0
for i in range(1, n):
    res += i

print(res)

### FIXED CODE ###

import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n = int(input())

print((n) * (n-1)//2)
### BUGGY CODE ###

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

for i in range(int(round(y/10000, 0)) + 1):
    for j in range(int(round(y/5000, 0)) + 1):
        for k in range(int(round(y/1000, 0)) + 1):
            if i+j+k > n:
                break
            elif (10000*i) + (5000*j) + (1000*k) == y and i+j+k == n:
                print(i, j, k)
                exit()

print("-1 -1 -1")

### FIXED CODE ###

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

for i in range(n+1):
    for j in range(n-i+1):
        if (10000*i) + (5000*j) + (1000*(n-i-j)) == y:
            print(i, j, n-i-j)
            exit()

print("-1 -1 -1")
### BUGGY CODE ###

N=int(input())
a_l=[int(i) for i in input().split()]

def xor(i,j):
    l=max(len(str(format(i,'b'))),len(str(format(j,'b'))))
    i2=str(format(i,'b').zfill(l))
    j2=str(format(j,'b').zfill(l))
    ans=0
    for k in range(l):
        if i2[k]!=j2[k]:
            ans+=2**(l-k-1)
    return ans

sum1=0
j=1
for i in range(N-1):
    while j<N:
        sum1+=xor(a_l[i],a_l[j])
        j+=1
    j=i+2
print(sum1%(7+10**9))

### FIXED CODE ###

n=int(input())
lis=list(map(lambda x:format(int(x),'b'),input().split()))
l=0
for i in range(n):
    l=max(l,len(lis[i]))

d0=[0]*60
d1=[0]*60

for i in range(n):
    lis[i]=lis[i].zfill(l)
    for j in range(l):
        if lis[i][-j-1]=='0':
            d0[j]+=1
        else:
            d1[j]+=1

ans=0
for i in range(60):
    ans+=(d0[i]*d1[i]*2**i)%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

# input = sys.stdin.readline


def main():
    n = int(input())

    ans = 0

    for i in range(1, n):
        ans += i

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

# input = sys.stdin.readline


def main():
    n = int(input()) - 1
    ans = 0

    if n % 2:
        print((1 + n) * (n // 2) + (n // 2 + 1))

    else:
        print((1 + n) * (n // 2))


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

def is_nine(x):
    res = 0
    while x > 0:
        t = x % 10
        res += t
        x //= 10
    return res

if __name__ == '__main__':
    N = int(input())
    e = is_nine(N)
    if (e % 9 == 0):
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

def is_nine(x):
    res = 0
    while x > 0:
        t = x % 10
        res += t
        x //= 10
    return res

if __name__ == '__main__':
    N = list(input())
    e = 0
    for i in N:
        e += int(i)
        
    if (e % 9 == 0):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    *z,=zip(sorted(a[:n])[::-1],sorted(a[n:]))
    ok=10**12
    ng=-1
    while ok-ng>1:
        mid=(ok+ng)//2
        l=k
        for b,g in z:
            if b*g>mid:
                l-=b-mid//g
        if l<0:ng=mid
        else:ok=mid
    print(ok)
main()

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    a,f=sorted(a[:n])[::-1],sorted(a[n:])
    ok=10**12
    ng=-1
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        l=k
        for b,g in zip(a,f):
            if b*g>mid:
                l-=b-mid//g
        if l<0:ng=mid
        else:ok=mid
    print(ok)
main()