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

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

if any(a>b for a,b in zip(A,B)):
    print(-1)
    exit()

hq = []
for i,(a,b) in enumerate(zip(A,B)):
    if a <= b - B[(i-1)%N] - B[(i+1)%N]:
        hq.append((-b,i))
heapq.heapify(hq)

ans = 0
while hq:
    _,i = heapq.heappop(hq)
    if B[i] == A[i]: continue
    l = B[(i-1)%N]
    r = B[(i+1)%N]
    if B[i]-l-r < A[i]: continue
    k = (B[i]-A[i]) // (l+r)
    ans += k
    B[i] -= k*(l+r)
    if A[i] <= B[i] - l - r:
        heapq.heappush(hq, (-B[i],i))
    ll = B[(i-2)%N]
    rr = B[(i+2)%N]
    if A[(i+1)%N] <= r - B[i] - rr:
        heapq.heappush(hq, (-r,(i+1)%N))
    if A[(i-1)%N] <= l - B[i] - ll:
        heapq.heappush(hq, (-l,(i-1)%N))

if all(a==b for a,b in zip(A,B)):
    print(ans)
else:
    print(-1)

### FIXED CODE ###

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

if any(a>b for a,b in zip(A,B)):
    print(-1)
    exit()

def pb(i):
    return i-1 if i-1 >= 0 else N-1
def nx(i):
    return i+1 if i+1 < N else 0

hq = []
for i,(a,b) in enumerate(zip(A,B)):
    if a <= b - B[pb(i)] - B[nx(i)]:
        hq.append((-b,i))
heapq.heapify(hq)

ans = 0
while hq:
    _,i = heapq.heappop(hq)
    if B[i] == A[i]: continue
    l = B[pb(i)]
    r = B[nx(i)]
    if B[i]-l-r < A[i]: continue
    k = (B[i]-A[i]) // (l+r)
    ans += k
    B[i] -= k*(l+r)
    ll = B[pb(pb(i))]
    rr = B[nx(nx(i))]
    if A[nx(i)] <= r - B[i] - rr:
        heapq.heappush(hq, (-r,nx(i)))
    if A[pb(i)] <= l - B[i] - ll:
        heapq.heappush(hq, (-l,pb(i)))

if all(a==b for a,b in zip(A,B)):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

def build_cost_table(n):
    ret = [[-1] * n for _ in range(n)]
    for r in range(n):
        dr = min(r, n - 1 - r)
        for c in range(n):
            if ~ret[r][c]: continue
            dc = min(c, n - 1 - c)
            ret[r][c] = ret[n - 1 - r][c] = ret[n - 1 - r][n - 1 - c] = ret[r][n - 1 - c] = min(dr, dc)
    return ret


def main():
    from collections import deque

    def next_coods(r, c):
        if r > 0:
            yield r - 1, c
        if c > 0:
            yield r, c - 1
        if r < N - 1:
            yield r + 1, c
        if c < N - 1:
            yield r, c + 1

    N = int(input())
    *p, = (int(x) - 1 for x in input().split())

    H = build_cost_table(N)  # 離席コスト
    S = [[1] * N for _ in range(N)]  # 着席

    ans = 0
    for pi in p:
        pi_r, pi_c = divmod(pi, N)

        hpi = H[pi_r][pi_c]  # piの離席コスト
        ans += hpi  # piの離席コストを加算
        S[pi_r][pi_c] = 0  # piを空席にする

        # BFSで離席コストを更新
        dq = deque()
        dq.append((pi_r, pi_c, hpi))
        while dq:
            r, c, h = dq.popleft()
            for nr, nc in next_coods(r, c):
                if H[nr][nc] > h:
                    H[nr][nc] = h
                    dq.append((nr, nc, h + S[nr][nc]))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def build_cost_table(n):
    ret = [-1] * (n ** 2)
    for r in range(n):
        dr = min(r, n - 1 - r)
        for c in range(n):
            dc = min(c, n - 1 - c)
            ret[r * n + c] = min(dr, dc)
    return ret


def main():
    from collections import deque

    N = int(input())
    *p, = (int(x) - 1 for x in input().split())

    H = build_cost_table(N)  # 離席コスト
    S = [1] * (N ** 2)  # 着席

    ans = 0
    for pi in p:
        hpi = H[pi]  # piの離席コスト
        ans += hpi  # piの離席コストを加算
        S[pi] = 0  # piを空席にする

        # BFSで離席コストを更新
        dq = deque()
        dq.append((pi, hpi))
        while dq:
            x, h = dq.popleft()
            r, c = divmod(x, N)

            nx = x - N
            if r != 0 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x + N
            if r != N - 1 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x - 1
            if c != 0 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x + 1
            if c != N - 1 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

    print(ans)


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

def solve():
    N,K = [int(i) for i in input().split()]
    P = [int(i) for i in input().split()]
    ans = 0
    for i in range(N-K+1):
        expected_sum = 0
        for j in range(i, i+K):
            expected_sum += (P[j]+1) / 2.0
        ans = max(expected_sum, ans)
    print(ans)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

def solve():
    N,K = [int(i) for i in input().split()]
    P = [int(i) for i in input().split()]
    prev_K_sum = max_K_sum = sum(P[:K])
    start = 0
    for i in range(N-K):
        cur_K_sum = prev_K_sum - P[i] + P[i+K]
        if cur_K_sum > max_K_sum:
            start = i + 1
            max_K_sum = cur_K_sum
        prev_K_sum = cur_K_sum
    target = P[start:start+K]
    ans = sum([(num+1)/2.0 for num in target])
    print(ans)

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

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]
Q = int(input())
VLs = list(map(lambda s: tuple(map(int, s.split())), readlines()))

n = min(2**10, N)

@njit(cache = True)
def pre(vws):
    dp = np.zeros((n, 10**5+1), np.int32)
    for i in range(n):
        v, w = vws[i]
        dp[i] = dp[(i-1)//2]
        dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])
    return dp

dp = pre(vws)

@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    mask = (weights <= L)     
    return np.amax(dp_[L - weights[mask]] + values[mask])

for V, L in VLs:
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        vs = []
        ws = []
        while V >= n:
            vs.append(vws[V][0])
            ws.append(vws[V][1])
            V = (V-1) // 2
        print(func(np.array(vs, np.int32), np.array(ws, np.int32), L, dp[V]))


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

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

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
res = []
tree = []
level = []
for i in range(210000):
    res.append(0)
    tree.append([])
    level.append(-1)

for loop in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

def make_level(index, lev):
    level[index] = lev
    for next in tree[index]:
        # 逆走はしない
        if level[next] != -1:
            continue
        make_level(next, lev + 1)
make_level(1, 0)
#print(level[0:10])

def do(index, lev, cost):
    res[index] += cost
    for next in tree[index]:
        if level[next] <= lev:
            continue
        do(next, lev + 1, cost)


for loop in range(q):
    p, x = map(int, input().split())
    do(p, level[p], x)

res = list(map(str, res))
print(" ".join(res[1:n+1]))

### FIXED CODE ###

edge = []
n, q = map(int, input().split())
for _ in range(n+100):
    edge.append([])
for _ in range(n-1):
    a,b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)
res = [0] * (n+1)
cost = [0] * (n+1)
for _ in range(q):
    a,b = map(int, input().split())
    res[a] += b

import collections
q = collections.deque([[1, 0]])
used = [False] * (n+1)
while len(q) > 0:
    #print(q)
    curnode, cost = q.popleft()
    res[curnode] += cost
    used[curnode] = True
    for i in range(len(edge[curnode])):
        nnext = edge[curnode][i]
        if used[nnext] is True:
            continue
        else:
            q.append([nnext, res[curnode]])
res=res[1:]
print(" ".join(list(map(str, res))))
### BUGGY CODE ###

import sys
import heapq

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  s = input()
  
  inf = pow(10, 6)
  ans = [inf]*(n+1)
  key = []
  heapq.heapify(key)
  heapq.heappush(key, (0, n))
  ans[n] = 0
  index = n-1
  while key:
    sub = heapq.heappop(key)
    s1, s2 = sub[0], sub[1]
    subindex = s2
    for i in range(min([index, s2-1]), max([-1, s2-m-1]), -1):
      if ans[i] != inf:
        continue
      if s[i] == "1":
        continue
      heapq.heappush(key, (s1+1, i))
      ans[i] = s2
      subindex = i
    index = subindex
      
  
  if ans[0] == inf:
    print(-1)
  else:
    index = 0
    answer = []
    while True:
      subindex = ans[index]
      answer.append(subindex-index)
      if subindex == n:
        break
      index = subindex
    print(*answer)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
import heapq

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  s = input()
  
  inf = pow(10, 6)
  ans = [inf]*(n+1)
  key = []
  heapq.heapify(key)
  heapq.heappush(key, (0, n))
  ans[n] = 0
  index = n-1
  count = 0
  while key:
    sub = heapq.heappop(key)
    s1, s2 = sub[0], sub[1]
    if s1 < count:
      continue
    count = s1+1
    subindex = index
    for i in range(min([index, s2-1]), max([-1, s2-m-1]), -1):
      if ans[i] != inf:
        continue
      if s[i] == "1":
        continue
      heapq.heappush(key, (count, i))
      ans[i] = s2
      subindex = i
    index = subindex
      
  if ans[0] == inf:
    print(-1)
  else:
    index = 0
    answer = []
    while True:
      subindex = ans[index]
      answer.append(subindex-index)
      if subindex == n:
        break
      index = subindex
  
    print(*answer)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import math

A,B=map(int,input().split())
min=min(A,B)
rng=math.ceil(math.sqrt(min))
divisor=[1]
stack=[]
for i in range(2,min+1):
    if A%i==0 and B%i==0:
        p=min//i
        stack.append(p)
        for x in divisor:
            if i%x==0 and x!=1:
                break
        else:
            divisor+=[i]

while len(stack)!=0:
    p=stack.pop()
    if A%p==0 and B%p==0:
        for x in divisor:
            if p%x==0 and x!=1:
                break
        else:
            divisor+=[p]

print(len(divisor))


### FIXED CODE ###

import math

divisor=[1]
stack=[]
#eiclidean algorithm
A,B=map(int,input().split())
p=max(A,B)
q=min(A,B)
int2=0
gcd=0
while True:
    int2=p%q
    if int2==0:
        gcd=q
        break
    else:
        p=q
        q=int2

if gcd!=1:
    stack.append(gcd)
    
for i in range(2,math.ceil(math.sqrt(gcd))+1):
    if gcd%i==0:
        p=gcd//i
        stack.append(p)
        for x in divisor:
            if i%x==0 and x!=1:
                break
        else:
            divisor+=[i]

while len(stack)!=0:
    p=stack.pop()
    for x in divisor:
        if p%x==0 and x!=1:
            break
    else:
        divisor+=[p]


print(len(divisor))
### BUGGY CODE ###

cnt = 0
for i in range(int(input())):
    x = int(input())
    flg = False # なんらかの数で割り切れるかどうか
    if x == 1:
        continue
    if x == 2:
        cnt += 1
        continue
    for k in range(2, x):
        if not(x % k):
            flg = True
            break
    if not flg:
        cnt += 1
print(cnt)


### FIXED CODE ###

import math
cnt = 0
for i in range(int(input())):
    x = int(input())
    flg = False # なんらかの数で割り切れるかどうか
    if x == 1:
        continue
    if x == 2:
        cnt += 1
        continue
    for k in range(2, math.floor(math.sqrt(x))+1):
        if not(x % k):
            flg = True
            break
    if not flg:
        cnt += 1
print(cnt)
### BUGGY CODE ###

def nCr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= numerator[k]
    return result

N = int(input())
A = list(map(int, input().split()))
B = [0]
t = 0
for i in range(N):
    B.append(B[i] + A[i])

C = set(B)
for j in C:
    count = B.count(j)
    if count > 1:
        t += nCr(count,2)

print(int(t))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = {}
t = 0
x = 0
B[0] = 1
for i in A:
    x += i
    t += B.get(x, 0)
    B[x] = B.get(x, 0) + 1

print(t)
### BUGGY CODE ###

count = int(input())
numbers = map(int, input().split(' '))

counter = 0
while True:
  for item in numbers:
    if item % 2 == 1:
      break
  counter += 1
  numbers = [item / 2 for item in numbers]

print(counter)

### FIXED CODE ###

count = int(input())
numbers = [int(num) for num in input().split()]

counter = 0
while True:
  tmp = 0
  for item in numbers:
    tmp += item % 2
  if tmp > 0:
    break
  counter += 1
  numbers = [item / 2 for item in numbers]
print(counter)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [[] for i in range(n)]
for i in range(m):
  s, t = map(int, input().split())
  a[s-1].append(t-1)
dp = [0]*n
count = 0
c = []
for i in range(n-2,-1,-1):
  b = 0
  max_count = 0
  max_dp = 0
  for j in a[i]:
    dp[i] += dp[j] + 1
    b += 1
    if max_dp < dp[j]:
      max_count, max_dp = count, dp[j]
    count += 1
  if b>1:
    c.append(max_count)
  dp[i] /= b
min_dp = dp[0]
for k in c:
  dp = [0]*n
  count = 0
  for i in range(n-2,-1,-1):
    b = 0
    for j in a[i]:
      if count != k or len(a[i]) == 1:
        dp[i] += dp[j] + 1
        b += 1
      count += 1
    dp[i] /= b
  min_dp = min(min_dp,dp[0])
print(min_dp)

### FIXED CODE ###

n, m = map(int, input().split())
a = [[] for i in range(n-1)]
for i in range(m):
  s, t = map(int, input().split())
  a[s-1].append(t-1)
dp = [0]*n
sum_d = [0]*(n-1)
max_d = [0]*(n-1)
b = [0]*n
for i in range(n-2,-1,-1):
  for j in a[i]:
    sum_d[i] += dp[j] + 1
    b[i] += 1
    if max_d[i] < dp[j]+1 and len(a[i]) > 1:
      max_d[i] = dp[j]+1  
  dp[i] = sum_d[i] / b[i]
min_dp = dp[0]
for k in range(n-2):
  if b[k]==1:
    continue
  ddp = [0]*k + [dp[k] - (sum_d[k]-max_d[k])/(b[k]-1)]
  for i in range(k-1,-1,-1):
    ddp[i] = sum([ddp[j] for j in a[i] if j <= k]) / b[i]
  min_dp = min(min_dp,dp[0] - ddp[0])
print(min_dp)
### BUGGY CODE ###

import math

def main(): 

    n = int(input())
    a = [int(input()) for _ in range(n)]

    max_value = max(a)

    for i in range(n):
        if a[i] != max_value:
            print(max_value)
        else:
            t = list(a)
            t.pop(i)

            print(max(t))




if __name__ == "__main__":
    main() 

### FIXED CODE ###


def main(): 

    n = int(input())
    a = [int(input()) for _ in range(n)]

    max_v = 0
    max_sv = 0

    for i in range(n):
        if a[i] > max_v:
            max_sv = max_v
            max_v = a[i]
        elif a[i] > max_sv:
            max_sv = a[i]

    for i in range(n):
        if a[i] != max_v:
            print(max_v)
        else:
            print(max_sv)




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

ans=input()
n=int(input())
for i in range(n):
  t=input()
  if t[0]=="1":
    ans=ans[::-1]
  else:
    if t[2]=="1":
      ans=t[4]+ans
    else:
      ans=ans+t[4]
print(ans)


### FIXED CODE ###

S = input()
Q = int(input())
reverse = False
front = ""
end = S

for _ in range(Q):
    I = input().split()
    if I[0] == "1":
        reverse = not reverse
    else:
        if (I[1] == "1") ^ reverse:
            front =front + I[2]
        else:
            end = end + I[2]


if reverse:
    print(end[::-1]+front)
    #print("".join(list(reversed(end)))+front)
else:
    print(front[::-1]+end)
    #print("".join(list(reversed(front)))+end)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
ans = 0
for r in range(int(N/R)+1):
    for g in range(int(N/G)+1):
        if N-(r*R+g*G) >= 0 and (N-(r*R+g*G))%B == 0:
        #    print(r,g,(N-(r*R+g*G))%B)
            ans += 1
print(ans)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
ans = 0
for r in range(int(N/R)+1):
    for g in range(int((N-r*R)/G)+1):
        if N-(r*R+g*G) >= 0 and (N-(r*R+g*G))%B == 0:
        #    print(r,g,(N-(r*R+g*G))%B)
            ans += 1
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
import heapq
heapq.heapify(a)
for i in range(m):
    b,c=map(int,input().split())
    while b>0:
        if c > a[0]:
            minA = heapq.heappop(a)
            heapq.heappush(a,c)
            b -=1
        else:
            break
print(sum(a))

### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
import heapq
heapq.heapify(a)
BC=[list(map(int,input().split())) for _ in range(m)]
BC.sort(reverse=True,key=lambda x:x[1])
for i in range(m):
    while BC[i][0]>0:
        if BC[i][1] > a[0]:
            minA = heapq.heappop(a)
            heapq.heappush(a,BC[i][1])
            BC[i][0] -=1
        else:
            break
print(sum(a))
### BUGGY CODE ###

import bisect

N = int(input())
A = sorted([int(i) for i in input().split()])
B = sorted([int(i) for i in input().split()])
C = sorted([int(i) for i in input().split()])

cnt = 0
for i in range(N):
    x = bisect.bisect_right(B, A[i])
    for j in B[x:]:
        y = bisect.bisect_right(C, j)
        cnt += len(C[y:])
        
print(cnt)

### FIXED CODE ###

import bisect

n = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

ans = 0
for b in B:
    ans += bisect.bisect_left(A, b) * (n - bisect.bisect_right(C, b))
    
print(ans)
### BUGGY CODE ###

N = int(input())
mod = 998244353
# DP ナップサックぽいやつ
# DP[i][j] := a_0からa_iまでの部分集合で和がjになるものの個数
# 配るDPの方が場合分けがなくて簡潔に書ける 計算量増えるかも
# DP[i-1][j]→DP[i][j]とDP[i][j + a_i ]に配る

aaa = [int(input()) for _ in range(N)]
sum_aaa = sum(aaa)

sum_now = 0
DP = [[0] * (sum_aaa+1) for i in range(N)]
DP2 = [[0] * (sum_aaa+1) for i in range(N)]

a = aaa[0]
DP[0][0] = 2
DP[0][a] = 1

DP2[0][0] = 1
DP2[0][a] = 1

sum_now += a

for i in range(1, N):
	a = aaa[i]
	sum_now += a
	for j in range(sum_now + 1):

		if (j >= a):
			DP[i][j] = DP[i-1][j]*2 + DP[i-1][j-a]
		else:
			DP[i][j] = DP[i-1][j]*2

		while (DP[i][j] > mod):
			DP[i][j] -= mod

		if (j >= a):
			DP2[i][j] = DP2[i-1][j] + DP2[i-1][j-a]
		else:
			DP2[i][j] = DP2[i-1][j]

		while (DP2[i][j] > mod):
			DP2[i][j] -= mod


# print(DP2)
minimum_invalid_length = int((sum_now+1)//2)
num_too_long = sum (DP[N-1][minimum_invalid_length:])
if (sum_aaa %2 == 0):
	num_too_long -= DP2[N-1][int(sum_aaa /2)]
# print(num_too_long)
# print(sum(aaa))
print((3** N - num_too_long * 3) % mod )


### FIXED CODE ###

N = int(input())
mod = 998244353
# DP ナップサックぽいやつ
# DP[i][j] := a_0からa_iまでの部分集合で和がjになるものの個数
# 配るDPの方が場合分けがなくて簡潔に書ける 計算量増えるかも
# DP[i-1][j]→DP[i][j]とDP[i][j + a_i ]に配る

aaa = [int(input()) for _ in range(N)]
sum_aaa = sum(aaa)

sum_now = 0
DP = [[0] * (sum_aaa+1) for i in range(N)]
DP2 = [[0] * (sum_aaa+1) for i in range(N)]

a = aaa[0]
DP[0][0] = 2
DP[0][a] = 1

DP2[0][0] = 1
DP2[0][a] = 1

sum_now += a

for i in range(1, N):
	a = aaa[i]
	sum_now += a
	for j in range(sum_now + 1):

		if (j >= a):
			DP[i][j] = DP[i-1][j]*2 + DP[i-1][j-a]
		else:
			DP[i][j] = DP[i-1][j]*2

		while (DP[i][j] > mod):
			DP[i][j] -= mod

	for j in range(min(sum_now + 1, int(sum_aaa /2)+1)):
		if (j >= a):
			DP2[i][j] = DP2[i-1][j] + DP2[i-1][j-a]
		else:
			DP2[i][j] = DP2[i-1][j]

		while (DP2[i][j] > mod):
			DP2[i][j] -= mod

# print(DP2)
minimum_invalid_length = int((sum_now+1)//2)
num_too_long = sum (DP[N-1][minimum_invalid_length:])
if (sum_aaa %2 == 0):
	num_too_long -= DP2[N-1][int(sum_aaa /2)]
# print(num_too_long)
# print(sum(aaa))
print((3** N - num_too_long * 3) % mod )
### BUGGY CODE ###

import heapq
def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
        
    heapq.heapify(A)
    for i in range(M):
        B, C = map(int, input().split())
        for j in range(B):
            if C < A[0]:
                break
            heapq.heapreplace(A, C)
    
    print(sum(A))


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    N, M = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    operate = []
    for _ in range(M):
        b, c = map(int,input().split())
        operate.append([b,c])
    operate.sort(reverse=True, key=lambda x:x[1])    

    rewrite = [0] * N
    idx = 0
    for b,c in operate:
        for i in range(b):
            rewrite[idx] = c
            idx += 1
            if idx == N:
                break
        if idx == N:
            break
    
    ans = 0
    for i in range(N):
        ans += max(A[i],rewrite[i])
    
    print(ans)

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

from sys import stdin
n = int(stdin.readline().rstrip())
li = [p for p in range(1,n)]
if n == 1:
    print(0)
else:
    print(sum(li))

### FIXED CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
point = n*(n-1)//2
print(point)
### BUGGY CODE ###

def main():
 
    n, k = map(int, input().split())
 
    C = [[0]*(2*k) for _ in range(2*k)]
 
    for i in range(n):
        x, y, c = map(str, input().split())
        x, y = int(x), int(y)
        if c == 'W':
            y += k
        C[y%(2*k)][x%(2*k)] += 1
 
    #print(C)
    s = [[0]*(2*k+1) for _ in range(2*k+1)]
    for i in range(2*k):
        for j in range(2*k):
            s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + C[i][j]
 
    #print(s)
 
    def count(x1, x2, y1, y2):
        return s[y2][x2]-s[y1][x2]-s[y2][x1]+s[y1][x1]
 
    ans = 0
    for i in range(k):
        for j in range(k):
            temp = 0
            temp += count(0, j, 0, i)
            temp += count(j, j+k, i, i+k)
            temp += count(0, j, i+k, 2*k)
            temp += count(j+k, 2*k, 0, i)
            temp += count(j+k, 2*k, i+k, 2*k)
            ans = max(ans, max(temp, n-temp))
    print(ans)
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

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

C = [[0]*(2*k) for _ in range(2*k)]

for i in range(n):
    x, y, c = map(str, input().split())
    x, y = int(x), int(y)
    if c == 'W':
        y += k
    C[y%(2*k)][x%(2*k)] += 1

#print(C)
s = [[0]*(2*k+1) for _ in range(2*k+1)]
for i in range(2*k):
    for j in range(2*k):
        s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + C[i][j]

#print(s)

def count(x1, x2, y1, y2):
    return s[y2][x2]-s[y1][x2]-s[y2][x1]+s[y1][x1]

ans = 0
for i in range(k):
    for j in range(k):
        temp = 0
        temp += count(0, j, 0, i)
        temp += count(j, j+k, i, i+k)
        temp += count(0, j, i+k, 2*k)
        temp += count(j+k, 2*k, 0, i)
        temp += count(j+k, 2*k, i+k, 2*k)
        ans = max(ans, max(temp, n-temp))
print(ans)