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

from collections import deque
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    al = []
    al.append(deque([]))
    for _ in range(n):
        row = list(map(int, input().split()))
        al.append(deque(row))

    # print(al)

    day = 0
    cnt = 0
    max_cnt = n*(n-1)//2
    while True:
        day += 1
        # print('-----',day)
        # print(al)
        # already_fights = [False]*(n+1)
        already_fights = set()
        update_flag = False
        for i in range(1,n+1):
            al_i = al[i]
            if not al_i or i in already_fights: continue
            i_next_rival = al_i[0]

            al_rival_i = al[i_next_rival]
            if not al_rival_i or i_next_rival in already_fights: continue
            i_next_rival_rival = al_rival_i[0]

            if i_next_rival_rival == i:
                al[i].popleft()
                al[i_next_rival].popleft()
                already_fights.add(i)
                already_fights.add(i_next_rival)
                # already_fights[i] = True
                # already_fights[i_next_rival] = True
                cnt += 1
                update_flag = True
            else:
                continue
        # print(al)

        if not update_flag:
            print(-1)
            exit()

        if cnt == max_cnt:
            break

    print(day)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    al = []
    al.append(deque([]))
    for _ in range(n):
        row = list(map(int, input().split()))
        al.append(deque(row))

    # print(al)

    day = 0
    cnt = 0
    max_cnt = n*(n-1)//2
    check_il = [i for i in range(1,n+1)]
    while True:
        next_check_il = check_il[:]
        check_il = []
        day += 1
        already_fights = set()
        update_flag = False
        for i in next_check_il:
            al_i = al[i]
            if not al_i or i in already_fights: continue
            i_next_rival = al_i[0]

            al_rival_i = al[i_next_rival]
            if not al_rival_i or i_next_rival in already_fights: continue
            i_next_rival_rival = al_rival_i[0]

            if i_next_rival_rival == i:
                al[i].popleft()
                al[i_next_rival].popleft()
                already_fights.add(i)
                already_fights.add(i_next_rival)
                check_il.append(i)
                check_il.append(i_next_rival)
                cnt += 1
                update_flag = True
            else:
                continue

        if not update_flag:
            print(-1)
            exit()

        if cnt == max_cnt:
            break

    print(day)


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

from collections import Counter
n = int(input())
a = list(input().split())
c = Counter(a)
c = list(c.items())
x = []
y = []
for i in range(len(c)):
    x.append(c[i][0])
    y.append(c[i][1])
ans = 0
for i in range(len(c)):
    ans += y[i] * (y[i] - 1) // 2
for i in range(n):
    print(ans - (y[x.index(a[i])] - 1))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0] * (n + 1)
for i in range(n):
    b[a[i]] += 1
ans = 0
for i in range(len(b)):
    ans += b[i] * (b[i]-1) // 2
for i in range(n):
    print(ans - (b[a[i]] - 1))
### BUGGY CODE ###

import collections

N = int(input())
fact = 1
mod = 10**9 + 7

for i in range(1,N+1):
    fact *= i

s = 0
R = fact
I = fact

soinsu = []
while s==0:
    for i in range(2,R+1):
        if I%i==0:
            I=I//i
            if I==1:
                s=1
            soinsu.append(i)
            break

dic = collections.Counter(soinsu)

ans = 1
for v in dic.values():
    ans *= v + 1
    ans %= mod


print(ans)


### FIXED CODE ###

N = int(input())
fact = 1
mod = 10**9 + 7

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

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


for i in range(1,N+1):
    fact *= i

s = 0
R = primes(N)
#print(R)
I = fact

soinsu = []
tmp = 1
cnt = 1
ans = 1
while s==0:
    for i in R:

        if I%i==0:
            I=I//i
            if I==1:
                s=1
#            soinsu.append(i)
            if i == tmp:
                cnt += 1
            else:
                ans *= (cnt + 1)
                ans %= mod
                cnt  = 1
                tmp = i
            break

#dic = collections.Counter(soinsu)
# ans = 1
# for v in dic.values():
#     ans *= v + 1
#     ans %= mod


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

S = input()
Q = int(input())
direction = True
for _ in range(Q):
    line = input()
    if line[0] == '1':
        direction = not direction
    else:
        if (direction and line[2] == '1') or (not direction and line[2] == '2'):
            S = line[4] + S
        else:
            S = S + line[4]
print(S if direction else S[::-1])


### FIXED CODE ###

from collections import deque
S = input()
q = deque()
for s in list(S):
    q.append(s)
Q = int(input())
direction = True
for _ in range(Q):
    line = input()
    if line[0] == '1':
        direction = not direction
    else:
        if (direction and line[2] == '1') or (not direction and line[2] == '2'):
            q.appendleft(line[4])
        else:
            q.append(line[4])
print("".join(q) if direction else "".join(reversed(q)))
### BUGGY CODE ###

N, K = map(int, input().split())
X = []
Y = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
Xs = sorted(X)
Ys = sorted(Y)
ans = float('inf')
for left in range(N - 1):
    for right in range(left + 1, N):
        for down in range(N - 1):
            for up in range(down + 1, N):
                count = 0
                for i in range(N):
                    if Xs[left] <= X[i] <= Xs[right] and Ys[down] <= Y[i] <= Ys[up]:
                            count += 1
                if count >= K:
                    ans = min(ans, (Xs[right] - Xs[left]) * (Ys[up] - Ys[down]))
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
X = []
Y = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
Xs = sorted(X)
Ys = sorted(Y)
ans = float('inf')
for left in range(N - 1):
    for right in range(left + 1, N):
        for down in range(N - 1):
            for up in range(down + 1, N):
                count = 0
                for i in range(N):
                    if Xs[left] <= X[i] <= Xs[right] and Ys[down] <= Y[i] <= Ys[up]:
                            count += 1
                if count >= K:
                    ans = min(ans, (Xs[right] - Xs[left]) * (Ys[up] - Ys[down]))
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    print(a[i:].count(i+1))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
for i in range(n-1):
    ans[a[i]-1] += 1
for i in range(n):
    print(ans[i])
### BUGGY CODE ###

N,W=map(int,input().split())
Wlist=[]
Vlist=[]
for i in range(N):
  w,v=map(int,input().split())
  Wlist+=[w]
  Vlist+=[v]
dp=[[0 for p in range(W+1)] for i in range(N)]
dp[0][Wlist[0]]=Vlist[0]
for i in range(1,N):
  wi=Wlist[i]
  for j in range(W):
    if j+wi<=W:
      dp[i][j+wi]=max(dp[i-1][j]+Vlist[i],dp[i][j+wi])
    dp[i][j]=max(dp[i-1][j],dp[i][j])
print(max(dp[N-1]))

### FIXED CODE ###

N,W=map(int,input().split())
Wlist=[]
Vlist=[]
for i in range(N):
  w,v=map(int,input().split())
  Wlist+=[w]
  Vlist+=[v]
dp=[[0 for p in range(W+1)] for i in range(N)]
for i in range(W+1):
  if i>=Wlist[0]:
    dp[0][i]=Vlist[0]
for i in range(1,N):
  wi=Wlist[i]
  for j in range(W+1):
    if j-wi>=0:
      dp[i][j]=max(dp[i-1][j-wi]+Vlist[i],dp[i-1][j])
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j])
print(max(dp[N-1]))
### BUGGY CODE ###

n = int(input())
x = map(int, input().split())
a_list = list(x)
# n = 5
# a_list = [1,1,2,2]

# r_list = []
# for i in range(n+1):
#     r_list.append(a_list.count(i))


r_list = map(a_list.count, range(n+1))
r_list = list(r_list)
r_list2 = map(str, r_list[1:])
r_list2 = list(r_list2)

ans = "\n".join(r_list2)

print(ans)

### FIXED CODE ###

import collections
n = int(input())
x = map(int, input().split())
a_list = list(x)

# n = 5
# a_list = [1,1,3,3]

r_list = collections.Counter(a_list)
y = []
for i in range(1,(n+1)):
    if (i in r_list):
        y.append(r_list[i])
    else:
        y.append(0)

r_list2 = map(str, y)
r_list2 = list(r_list2)
ans = "\n".join(r_list2)
print(ans)

# r_list = map(a_list.count, range(n+1))
#r_list = list(r_list_v)
### BUGGY CODE ###

import itertools
N=int(input())
S=input()
ans=0
L=dict()
R=dict()
for seq in itertools.product([0,1],repeat=N):
    T0=""
    T1=""
    T2=""
    T3=""
    for i in range(N):
        if seq[i]==0:
            T0+=S[i]
            T2+=S[-i-1]
        else:
            T1+=S[i]
            T3+=S[-i-1]
    a0=len(T0)
    a1=len(T1)
    a2=len(T2)
    a3=len(T3)
    L[(T0,T1)]=L.get((T0,T1),0)+1
    R[(T2,T3)]=R.get((T2,T3),0)+1
for tup in L:
    ans+=L[tup]*R.get(tup,0)
print(ans)


### FIXED CODE ###

import itertools
import bisect
N=int(input())
S=input()
ans=0
L=dict()
R=dict()
for seq in itertools.product([0,1],repeat=N):
    T0=""
    T1=""
    T2=""
    T3=""
    for i in range(N):
        if seq[i]==0:
            T0+=S[i]
            T2+=S[-i-1]
        else:
            T1+=S[i]
            T3+=S[-i-1]
    a0=len(T0)
    a1=len(T1)
    a2=len(T2)
    a3=len(T3)
    if (T0,T1) in L:
        L[(T0,T1)]+=1
    else:
        L[(T0,T1)]=1
    if (T2,T3) in R:
        R[(T2,T3)]+=1
    else:
        R[(T2,T3)]=1
for tup in L:
    if tup in R:
        ans+=L[tup]*R[tup]
print(ans)
### BUGGY CODE ###

from itertools import product as prod

n, m = [int(x) for x in input().split()]

gr = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    gr[a].append((b, c))
    gr[b].append((a, c))

def dist(i, j, gr=gr):
    tmp_d = float("inf")
    if i == j:
        return 0
    for (node, d) in gr[i]:
        if node == j:
            tmp_d = d
    gr_cp = [[(n, d) for (n, d) in g if n != i] for g in gr]
    routes = [d + dist(n, j, gr=gr_cp) for (n, d) in gr_cp[i]]

    return min(routes + [tmp_d])

ans = 0
for i in range(n):
    for (j, d) in gr[i]:
        if dist(i, j) < d:
            ans += 1

print(ans // 2)


### FIXED CODE ###

import copy
from itertools import product as prod

n, m = [int(x) for x in input().split()]

wait = [[float("inf") for _ in range(n)] for _ in range(n)]
for i in range(n):
    wait[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    wait[a-1][b-1] = c
    wait[b-1][a-1] = c

dist = copy.deepcopy(wait)
for k, i, j in prod(range(n), range(n), range(n)):
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    dist[j][i] = min(dist[j][i], dist[j][k] + dist[k][i])

ans = 0
for i, j in prod(range(n), range(n)):
    if not wait[i][j] == float("inf") and dist[i][j] < wait[i][j]:
        ans += 1

print(ans // 2)
### BUGGY CODE ###

n,k = map(int,input().split())
p = [0] + list(map(int,input().split()))
c = [0] + list(map(int,input().split()))
ans = max(c[1:])
t = 0
for i in range(1,n+1):
    # print(ans)
    j = p[i]
    temp = c[i]
    cnt = 1
    ans = max(ans,temp)
    tempans = 0
    while i!=j:
        
        temp += c[j]
        j = p[j]
        cnt += 1
        # if i==5:
        #     print(j,c[j],temp)
    t = cnt
    tt = ans
    # if i==8:
    #     print(temp,t)
    if t < k:
        if temp > 0:
            # print(k,t,i)
            tempans += temp*(k//t - 1)
            tt = tempans
            j = p[i]
            for l in range(k-(k//t - 1)*t):
                tempans += c[j]
                j = p[j]
                tt = max(tt,tempans)
            ans = max(ans,tt)
            # print(ans)
        else:
            j = p[i]
            for l in range(k):
                tempans += c[j]
                j = p[j]
                tt = max(tt,tempans)
            ans = max(ans,tt)
            # print(ans)
    else:
        j = p[i]
        for l in range(k):
            tempans += c[j]
            j = p[j]
            tt = max(tt,tempans)
        ans = max(ans,tt)
        # print(ans)
    # if ans == 29779631210:
    #     print(i,ans,t,temp)
    #     exit()
print(ans)


### FIXED CODE ###

n,k = map(int,input().split())
p = [0] + list(map(int,input().split()))
c = [0] + list(map(int,input().split()))
ans = max(c[1:])
t = 0
for i in range(1,n+1):
    # print(ans)
    j = p[i]
    temp = c[i]
    cnt = 1
    ans = max(ans,temp)
    tempans = 0
    while i!=j:
        
        temp += c[j]
        j = p[j]
        cnt += 1
        # if i==5:
        #     print(j,c[j],temp)
    t = cnt
    tt = ans
    # if i==8:
    #     print(temp,t)
    if t < k:
        if temp > 0:
            # print(k,t,i)
            tempans += temp*(k//t - 1)
            tt = tempans
            j = p[i]
            for l in range(k-(k//t - 1)*t):
                tempans += c[j]
                j = p[j]
                tt = max(tt,tempans)
            ans = max(ans,tt)
            # print(ans)
        else:
            j = p[i]
            for l in range(t):
                tempans += c[j]
                j = p[j]
                tt = max(tt,tempans)
            ans = max(ans,tt)
            # print(ans)
    else:
        j = p[i]
        for l in range(k):
            tempans += c[j]
            j = p[j]
            tt = max(tt,tempans)
        ans = max(ans,tt)
        # print(ans)
    # if ans == 29779631210:
    #     print(i,ans,t,temp)
    #     exit()
print(ans)
### BUGGY CODE ###

n = input()
li = list(map(int, input().split()))
a = 1
if 0 in li:
    print(0)
    quit()
else:
    for x in li:
        a *= x
    if a > 10**18:
        print(-1)
        quit()
    print(a)

### FIXED CODE ###

n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    print(0)
    quit()
for x in ls:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)
### BUGGY CODE ###

from bisect import bisect_right
n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
ans = 0
#print(A)
#print(B)
#print(C)
for a in A:
    num1 = bisect_right(B, a)
    for i in range(num1,n):
        num2 = bisect_right(C,B[i])
        ans += n - num2
        #print(a,B[i],C[num2])


print(ans)

### FIXED CODE ###

from bisect import bisect_left,bisect_right
n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
ans = 0
#print(A)
#print(B)
#print(C)
for b in B:
    num1 = bisect_left(A,b)
    num2 = bisect_right(C,b)
    #print(num1,b,num2)
    ans += num1*(n-num2)

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

from functools import lru_cache

s = input()
s_len = len(s)
n = 2019
n_len = len(str(n))
result = 0


@lru_cache(maxsize=128)
def is_multiple(x):
    return x % n == 0


for i in range(s_len - n_len):
    for j in range(i + n_len, s_len + 1):
        m = int(s[i:j])
        if is_multiple(m):
            result += 1
print(result)

### FIXED CODE ###

s = input()
s_len = len(s)
n = 2019
mod_list = [0] * n
mod_list[0] = 1

p = 1
d = 0
for t in reversed(s):
    d += int(t) * p
    m = d % n
    mod_list[m] += 1
    p *= 10
    p %= 2019

result = sum(i * (i - 1) // 2 for i in mod_list)
print(result)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split(" ")))
cnt = 0 
for i in range(0,n):
    for j in range(i+1,n):
        if i == j:
            continue
        for k in range(j+1,n):
            if i == k and j == k:
                continue
            a = l[i]
            b = l[j]
            c = l[k]
            if a < b + c and b < a + c and c < a + b:
                cnt+=1
print(cnt)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split(" ")))
l.sort()
cnt = 0 
import bisect
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        target = a + b 
  #      print("#",a,b)
        f1 = bisect.bisect_left(l,target,j+1,n)
        cnt+= f1 - 1- j
   #     print("cnt: ",cnt)
print(cnt)
### BUGGY CODE ###

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

### FIXED CODE ###

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

a, b, x = map(int, input().split())

for cnt in range(a, a + x):
    if cnt % x == 0 :
        s = cnt
    else:
        continue
        
t = 0
        
for count in range(s, b + 1, x):
    if count % x == 0:
        t += 1
    else:
        continue
        
print(t)

### FIXED CODE ###

a,b,x=map(int,input().split())
print(b//x-(a-1)//x)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = list(input())
for _ in range(Q):
    l, r = map(int, input().split())
    line = S[l-1:r]
    count = 0
    for i in range(r-l):
        if line[i] == 'A' and line[i+1] == 'C':
            count += 1
    print(count)


### FIXED CODE ###

N, Q = map(int, input().split())
S = list(input())
holder = set()
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        holder.add(i+1)

# 累積和でどうぞ
prefix = [0 for _ in range(N+1)]
for i in range(1, N+1):
    if i-1 in holder:
        prefix[i] = prefix[i-1] + 1
    else:
        prefix[i] = prefix[i-1]

for _ in range(Q):
    l, r = map(int, input().split())
    print(prefix[r] - prefix[l])
### BUGGY CODE ###

N = int(input())
S = list(input())

counts = []
for i in range(N):
    count = 0
    for j in range(i):
        if S[j] != "E":
            count += 1
    for j in range(i+1, N):
        if S[j] != "W":
            count += 1
    counts.append(count)

print(min(counts))

### FIXED CODE ###

N = int(input())
S = list(input())

sum_W = [0]
for i in range(1, N):
    if S[i-1] == "W":
        sum_W.append(sum_W[i-1]+1)
    else:
        sum_W.append(sum_W[i-1])

sum_E = [S[1:].count("E")]
for i in range(0, N-1):
    if S[i+1] == "E":
        sum_E.append(sum_E[i]-1)
    else:
        sum_E.append(sum_E[i])

counts = []
for i in range(N):
    count = 0
    counts.append(sum_W[i]+sum_E[i])

print(min(counts))
### BUGGY CODE ###

K = int(input())

n = 1
x = 7


if K % 2 == 0:
  print( -1 )
  exit( 0 )
#

while 1:
  if x % K == 0:
    print( n )
    break
  x = (x % K) * 10 + 7
  n += 1
#


### FIXED CODE ###

K = int(input())

n = 1
x = 7


if (K % 2 == 0)or(K % 5 == 0):
  print( -1 )
  exit( 0 )
#

while 1:
  if x % K == 0:
    print( n )
    break
  x = (x * 10 + 7) % K
  n += 1
#
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
sum = 1
for i in range(n):
    sum = sum * a[i]
if sum > 10**18:
    print('-1')
else:
    print(sum)



### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
sum = 1
if 0 in a:
    sum = 0
    print(sum)
    exit()
for i in range(n):
    if sum == 0:
        break
    sum = sum * a[i]
    if sum > 10**18:
        sum = -1
        break
print(sum)
### BUGGY CODE ###

def qsort(a):
    if len(a) in (0,1):
        return a
    else:
        p = a[-1]
        l=[x for x in a[:-1] if x >=p]
        r=[x for x in a[:-1] if x <p]
        return qsort(l) + [p] + qsort(r)

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

def main():
    n,m=get_num()
    card = get_num()
    for i in range(m):
        b,c=get_num()
        card+=[c]*b
    card=qsort(card)
    print(sum(card[:n]))

if __name__=='__main__':
    main()

### FIXED CODE ###

import heapq as hq

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

def main():
    n,m = get_num()
    card = get_num()
    card_sum=sum(card)
    hq.heapify(card)
    d_set=[]
    d=[]
    for i in range(m):
        b,c=get_num()
        hq.heappush(d_set,(-c,b))
    for i in range(m):
        if len(d) ==n:
            break
        cnt = hq.heappop(d_set)
        for i in range(cnt[1]):
            d.append(-cnt[0])
            if len(d)==n:
                break
    for i in range(len(d)):
        c_min=hq.heappop(card)
        d_max=d[i]
        if c_min>=d_max:
            break
        else:
            card_sum += (d_max-c_min)
    print(card_sum)
main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

R, C, K = map(int, input().split())

items = dict()

for _ in range(K):
    r, c, v = map(int, input().split())
    items[(r-1,c-1)] = v

dp = [0] * 4 * R * C

if (0,0) in items:
    dp[1] = items[(0,0)]

def ind(i,j,k):
    return 4 * C * i + 4 * j + k

for row in range(R):
    for col in range(C):
        for pick in range(4):
            curr = dp[ind(row,col,pick)]
            #Go Right
            if col + 1 < C:
                dp[ind(row,col+1,pick)] = max(curr, dp[ind(row,col+1,pick)])
                if (row, col+1) in items and pick < 3:
                    dp[ind(row,col+1,pick+1)] = max(curr + items[(row,col+1)], dp[ind(row,col+1,pick+1)])
            #Go Down
            if row + 1 < R:
                dp[ind(row+1,col,0)] = max(curr, dp[ind(row+1,col,0)])
                if (row + 1, col) in items:
                    dp[ind(row+1,col,1)] = max(curr + items[(row+1,col)], dp[ind(row+1,col,1)])
                    

print(max(dp))
            


### FIXED CODE ###

import sys
input = sys.stdin.readline

R, C, K = map(int, input().split())

items = [0] * R * C

for _ in range(K):
    r, c, v = map(int, input().split())
    items[C * (r-1) + c-1] = v

dp = [0] * 4 * R * C

dp[1] = items[0]

def ind(i,j,k):
    return 4 * C * i + 4 * j + k

for row in range(R):
    for col in range(C):
        for pick in range(4):
            curr = dp[ind(row,col,pick)]
            #Go Right
            if col + 1 < C:
                dp[ind(row,col+1,pick)] = max(curr, dp[ind(row,col+1,pick)])
                if pick < 3:
                    dp[ind(row,col+1,pick+1)] = max(curr + items[C * row + col+1], dp[ind(row,col+1,pick+1)])
            #Go Down
            if row + 1 < R:
                dp[ind(row+1,col,0)] = max(curr, dp[ind(row+1,col,0)])
                dp[ind(row+1,col,1)] = max(curr + items[C * (row+1) + col], dp[ind(row+1,col,1)])
                    

print(max(dp))
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype='uint64')

for i in range(m):
    b, c = map(int, input().split())
    a = np.append(a, np.full(b, c, dtype='uint64'))

print(np.sum(np.sort(a)[::-1][:n]))


### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n, m = nm()

a = sorted(nl())

pos = 0

changer = []

for i in range(m):
    b, c = nm()
    changer.append((c, b))

changer = sorted(changer)[::-1]


for i in range(m):

    c = changer[i]
    for j in range(c[1]):
        while pos < n:
            if a[pos] < c[0]:
                a[pos] = c[0]
                break
            pos += 1
    if pos >= n:
        break

print(sum(a))
### BUGGY CODE ###

n,m = (int(i) for i in input().split()) 
a = [int(i) for i in input().split()]
a.sort(reverse=True)
for i in range(m):
    down = a[0]
    a.remove(down)
    a.append(down//2)
    a.sort(reverse=True)
    
print(sum(a))

### FIXED CODE ###

n,m = (int(i) for i in input().split()) 
a = [int(i) for i in input().split()]
b = []

a.sort(reverse=True)

for i in range(m):
    if i == 0:
        down = a[0]
        a.remove(down)
        b.append(down//2)
    else:
        if a != [] and a[0] >= b[0]:
            down = a[0]
            a.remove(down)
        else:
            down = b[0]
            b.remove(down)
        b.append(down//2)
    
print(sum(a)+sum(b))