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


def knapsack1(N,W,H,max_W):
    #print(W,H,max_W)
    #print(H[1][0],H[1][1])
    DP = [[0]*(max_w+1) for i in range(N+1)]
    #print(DP[0][0],DP[0][1])
    for i in range(N):
        for j in range(max_w+1):
            if j-H[i][0] >= 0:
                DP[i+1][j] = chmax(DP[i+1][j],DP[i][j-H[i][0]]+H[i][1])
            else:
                DP[i+1][j] = chmax(DP[i+1][j],DP[i][j])
        #print(DP)
    #print(DP)
    return DP 

def chmax(a,b):
    if a > b:
        return a
    else:
        return b

if __name__ == '__main__':
    N,W = map(int,input().split())
    H = [[0]*2 for i in range(N)]
    max_w = 0
    for i in range(N):   
        lst = list(map(int,input().split()))
        H[i] = lst
        max_w += lst[0]
    ans = knapsack1(N,W,H,max_w)
    finlst = []
    finans = 0
    for i in range(N+1):
        #print(ans[i][W])
        maxr = max(ans[i][:W+1])
        if maxr > finans:
            finans = maxr
    print(finans)
    #print(lstx)
    #print(max(ans[-1]))
    

### FIXED CODE ###


def knapsack1(N,W,weight,value):
    inf = float("inf")
    DP = [[-inf]*(W+1) for i in range(N+1)]
    for i in range(W+1): DP[0][i]=0

    for i in range(N):
        for j in range(W+1):
            if j-weight[i] >= 0:
                DP[i+1][j] = chmax(DP[i][j],DP[i][j-weight[i]]+value[i])
            else:
                DP[i+1][j] = chmax(DP[i+1][j],DP[i][j])
    return DP[N][W] 

def chmax(a,b):
    if a > b:
        return a
    else:
        return b

if __name__ == '__main__':
    N,W = map(int,input().split())
    weight = [0]*N
    value = [0]*N
    #print(weight,value)
    for i in range(N):   
        lst = list(map(int,input().split()))
        #print(lst)
        weight[i] = lst[0]
        value[i] = lst[1]
        #max_w += lst[0]
    #print(weight,value)
    ans = knapsack1(N,W,weight,value)
    print(ans)
    #print(max(max(ans)))
    #print(max(ans[-1]))
### BUGGY CODE ###

N=int(input())
a=[int(input())-1 for i in range(N)]

i=0
cnt=1
while a[i]!=0:
    if a[i]==1:
        print(cnt)
        exit()
    if a[i]==i:
        print(-1)
        exit()
    cnt+=1
    i=a[i]
print(-1)


### FIXED CODE ###

N = int(input())

a =[0]

for i in range(N):
    a.append(int(input()))


f =[0]*(N+1)

i=1
c = 0
while f[i]==0:
    f[i]=1
    i = a[i]
    c +=1
    if i ==2:
        break
if f[i]==1:
    print(-1)
else:
    print(c)
### BUGGY CODE ###

#input
S = input()
Q = int(input())
P = []
for i in range(Q):
    P.append(list(map(str, input().split())))

#output
for i in range(Q):
    if len(P[i]) == 1:
        S = S[-1::-1]
    else:
        v = P[i][2]
        if int(P[i][1]) == 1:
            T = v + S
            S = T
        else:
            T = S + v
            S = T
                        
print(S)

### FIXED CODE ###

#input
S = input()
Q = int(input())
P = [[]] * Q
for i in range(Q):
    P[i] = list(map(str, input().split()))

#output
flip = 0
cap = ""
tail = ""

for i in range(Q):
    if int(P[i][0]) == 1:
        flip += 1
    else:
        n = int(P[i][1])
        v = P[i][2]
        if flip % 2 == 0:
            if n == 1:
                cap = v + cap
            else:
                tail = tail + v
        else:
            if n == 1:
                tail = tail + v
            else:
                cap = v + cap

answer = ""
if flip % 2 == 0:
    answer = cap + S + tail
else:
    answer = tail[-1::-1] + S[-1::-1] + cap[-1::-1]

print(answer)
### BUGGY CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    a,f=sorted(a[:n]),sorted(a[n:])[::-1]
    ok=10**12
    ng=-1
    while 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()

### 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()
### BUGGY CODE ###

S = input()
size = len(S)
mod = 10**9+7

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

for i in range(size):
  cn = dp[i][0]
  a = dp[i][1]
  b = dp[i][2]
  c = dp[i][3]
  if(S[i] == 'A'):
    dp[i+1][0] += cn
    dp[i+1][1] += (a+cn)
    dp[i+1][2] += b
    dp[i+1][3] += c
  elif(S[i] == 'B'):
    dp[i+1][0] += cn
    dp[i+1][1] += a
    dp[i+1][2] += (b+a)
    dp[i+1][3] += c
  elif(S[i] == 'C'):
    dp[i+1][0] += cn
    dp[i+1][1] += a
    dp[i+1][2] += b
    dp[i+1][3] += (c+b)
  else:
    dp[i+1][0] += (3*cn)
    dp[i+1][1] += (3*a+cn)
    dp[i+1][2] += (3*b+a)
    dp[i+1][3] += (3*c+b)
  #for j in range(3):
    #dp[i+1][j] = (dp[i+1][j])

print(dp[size][3]%mod)

    
    

### FIXED CODE ###

S = input()
size = len(S)
mod = 10**9+7

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

for i in range(size):
  cn = dp[i][0]%mod
  a = dp[i][1]%mod
  b = dp[i][2]%mod
  c = dp[i][3]%mod
  if(S[i] == 'A'):
    dp[i+1][0] += cn
    dp[i+1][1] += (a+cn)
    dp[i+1][2] += b
    dp[i+1][3] += c
  elif(S[i] == 'B'):
    dp[i+1][0] += cn
    dp[i+1][1] += a
    dp[i+1][2] += (b+a)
    dp[i+1][3] += c
  elif(S[i] == 'C'):
    dp[i+1][0] += cn
    dp[i+1][1] += a
    dp[i+1][2] += b
    dp[i+1][3] += (c+b)
  else:
    dp[i+1][0] += (3*cn)
    dp[i+1][1] += (3*a+cn)
    dp[i+1][2] += (3*b+a)
    dp[i+1][3] += (3*c+b)

print(dp[size][3]%mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

K, S = map(int, input().split())

cnt = 0
for i in range(K+1):
    for j in range(K+1):
        k = S - i - j
        if k < 0 or k > K:
            continue
        if i+j+k == S:
            cnt += 1
print(cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline

K, S = map(int, input().split())

cnt = 0
for i in range(K+1):
    for j in range(K+1):
        k = S - i - j
        if k >= 0 and k <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

mod = 10 ** 9 + 7
N = int(input())
A = list(map(lambda x: int(x) % mod, input().split(" ")))

ans = sum(A[i] * A[j] for i in range(0,N-1) for j in range(i+1,N))

print(ans % mod)


### FIXED CODE ###

mod = 1000000007
N = int(input())
A = list(map(lambda x: int(x) % mod, input().split(" ")))

"""
累積話を計算しておく: O(N)
"""
_sum = 0
for i in range(N):
    _sum += A[i]
    _sum %= mod

"""
1重ループ内で下記を行う: O(N)

- 端のブロックを累積和から崩す（減算）
- 端のブロックと累積和をかける
- modをとる
"""
ans = 0
for i in range(N):
    # 累積和の端のブロックを崩す
    _sum -= A[i]

    ans += A[i] * _sum
    ans %= mod

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

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_D
#?°´??????????????¢????¨????
import re

def cal_puddle(puddle_list):
    depth = 0
    score = 0
    for symbol in puddle_list:
        if symbol == "\\":
            score += depth + 0.5
            depth += 1
        if symbol == "/":
            depth -= 1
            score += depth + 0.5
        if symbol == "_":
            score += depth
            
    return int(score)

def get_puddle_index(diagram_list):

    depth = 0
    for i, symbol in enumerate(diagram_list):
        if symbol == "\\":
            depth += 1
        elif symbol == "/":
            depth = depth - 1

        if depth == 0:
            return i

    return False

def cal(diagram):
    puddle_areas = []
    diagram_list = []

    puddle_list = []
    i = 0
    while i < len(diagram):
        if diagram[i] == "\\":
            puddle_end = get_puddle_index(diagram[i:])
            if puddle_end:
                puddle_list.append(diagram[i: i + puddle_end + 1])
                i = i + puddle_end
        i += 1

    for puddle in puddle_list:
        puddle_areas.append(cal_puddle(puddle))
        
    return puddle_areas

        
if __name__ == "__main__":
    a = input()
    result = cal(a)
    print(sum(result))
    print(str(len(result)) + "".join([" " + str(a) for a in result]))

### FIXED CODE ###

def cal_puddle(puddle):
    depth = 0
    score = 0
    for s in puddle:
        if s == "\\":
            score += depth + 0.5
            depth += 1
        elif s == "/":
            depth -= 1
            score += depth + 0.5
        elif s == "_":
            score += depth

        if depth == 0:
            return int(score)
    return int(score)

def get_puddles(diagram):
    hight = 0
    top_list = []
    in_puddle = True
    for index, s in enumerate(diagram + "\\"):
        if s == "/":
            in_puddle = True
            hight += 1
        if s == "\\":
            if in_puddle:
                in_puddle = False
                top_list.append([hight, index])
            hight -= 1

    puddles = []
    prev_hight = 0
    hight_list = [h for h, i in top_list]
    i = 0
    while i < len(top_list) - 1:
        cur_top = top_list[i]
        next_tops = list(filter(lambda top:cur_top[0] <= top[0], top_list[i + 1:]))
        #print(next_tops)
        if next_tops:
            next_top = next_tops[0]
            puddles.append((cur_top[1], next_top[1]))
            i = top_list.index(next_top)
        else:
            cur_top[0] -= 1
            cur_top[1] += diagram[cur_top[1] + 1:].index("\\") + 1
    #print(hight_list)
    #print(top_list)
    #print(puddles)
    return puddles

def main():
    diagram = input()
    result = []
    for s,e in get_puddles(diagram):
        result.append(cal_puddle(diagram[s:e]))
    print(sum(result))
    print(str(len(result)) + "".join([" " + str(i) for i in result]))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(n):
    ans *= i + 1
print(ans % (10**9 + 7))

### FIXED CODE ###

ans=1
n=int(input())
for i in range(1,n+1):
    ans*=i
    ans=ans%(10**9+7)
print(ans)
### BUGGY CODE ###

import bisect
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

for i in range(m):
    x = a.pop()
    x = x // 2
    bisect.insort(a, x)



print(sum(map(int, a)))


### FIXED CODE ###

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

heap = []
for i in a:
    heapq.heappush(heap, -i)


for i in range(m):
    x = - heapq.heappop(heap)
    x = x / 2
    heapq.heappush(heap, - x)



print(sum(map(lambda n: int (-n), heap)))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
i = 0
while i < N-1:
  j = A[i]+i+1
  while j <N:
    ans += 1 if j-i == A[i]+A[j] else 0
    j += 1
  i += 1
print(ans)


### FIXED CODE ###

from bisect import bisect, bisect_left

N = int(input())
A = list(map(int, input().split()))
I = [0]*N
J = [0]*N
i = 0
while i < N:
  I[i] = A[i]+i
  J[i] = i-A[i]
  i += 1
I.sort()
ans = 0
for j in J:
  ans += bisect(I, j)-bisect_left(I, j)
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    A = input().split()
    ans = []
    if n % 2 == 0:
        for i in range(0, n - 1, 2):
            ans.append(A[i])
            ans = [A[i + 1]] + ans
    else:
        for i in range(0, n - 1, 2):
            ans.append(A[i + 1])
            ans = [A[i]] + ans
        ans = [A[-1]] + ans
    print(' '.join(ans))


main()


### FIXED CODE ###

def main():
    n = int(input())
    A = input().split()
    B = [0] * n
    k = n % 2
    l = n // 2
    if k == 0:
        l -= 1
    r = l + 1
    for i in range(n):
        if i % 2 != k:
            B[l] = A[i]
            l -= 1
        else:
            B[r] = A[i]
            r += 1
    print(' '.join(B))


main()
### BUGGY CODE ###

def main():
  s=list(input())
  q=int(input())
  ok=1
  for i in range(q):
    query=list(input().split())
    if query[0]=='1':
      ok=(ok+1)%2
    else:
      f,c=query[1],query[2]
      if ok:
        if f=='1':
          s=[c]+s
        else:
          s+=[c]
      else:
        if f=='1':
          s=s+[c]
        else:
          s=[c]+s
  if ok:
    print(''.join(s))
  else:
    print(''.join(s[::-1]))
if __name__=='__main__':
  main()

### FIXED CODE ###

from collections import deque
def main():
  s=deque(list(input()))
  q=int(input())
  ok=1
  for i in range(q):
    query=list(input().split())
    if query[0]=='1':
      ok=(ok+1)%2
    else:
      f,c=query[1],query[2]
      if ok:
        if f=='1':
          s.appendleft(c)
        else:
          s.append(c)
      else:
        if f=='1':
          s.append(c)
        else:
          s.appendleft(c)
  s=list(s)
  if ok:
    print(''.join(s))
  else:
    print(''.join(s[::-1]))
if __name__=='__main__':
  main()
### 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)

def isOk(x):
    cost = 0
    for a, f in zip(A,F):
        eatable = x//f
        if eatable >= a:
            continue
        cost += a - eatable
    if cost <= k:
        return True
    return False

left = -1
right = A[-1] * F[0]
while left+1 < right:
    # mid = int(left + (right-left)//2)
    mid = (left+right)//2
    if isOk(mid):
        right = mid
    else:
        left = mid
print(right)

### FIXED CODE ###

import numpy as np
i8 = np.int64
i4 = np.int32


def solve(A, F, K):
    min_ = 0
    max_ = 10 ** 12
    while min_ < max_:
        mid = (min_ + max_) // 2
        count = A - mid // F
        sum_ = count[count > 0].sum()
        if sum_ <= K:
            max_ = mid
        else:
            min_ = mid + 1
    return min_

def main():
    stdin = open('/dev/stdin', 'rb')
    pin = np.fromstring(stdin.read(), i8, sep=' ')
    N, K = pin[:2]
    A = pin[2: N + 2]
    F = pin[N + 2: 2 * N + 2]
    A = np.sort(A)[::-1]
    F.sort()
    ans = solve(A, F, K)
    print(ans)

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

N,K,Q=map(int,input().split())
A=[]
score=[K]*N
for i in range(0,Q):
    A.append(int(input())-1)
        
for j in range(0,N):
    score[j]=score[j]-(Q-A.count(j))
    if(score[j]>0):
        print("Yes")
    else:
        print("No")
    

### FIXED CODE ###

N,K,Q=map(int,input().split())
A=[0]*N
score=[K]*N
for i in range(0,Q):
    a=int(input())
    A[a-1]+=1
        
for j in range(0,N):
    score[j]=score[j]-(Q-A[j])
    if(score[j]>0):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

#!/usr/bin/env python3

S = str(input())
Q = int(input())
# print(S, Q)

S_copy = S
is_reverse = False
for i in range(Q):
    query = list(input().split())
    # print(query)
    if int(query[0]) == 1:
        # print("reverse")
        # Sを反転
        # S_copy = S_copy[::-1]
        is_reverse = not is_reverse
    else:
        if int(query[1]) == 1:
            # Sの先頭にC_iを追加
            # print("prepend C_i")
            if is_reverse:
                S_copy = S_copy + query[2]
            else:
                S_copy = query[2] + S_copy
        else:
            # Sの末尾にC_iを追加
            # print("append C_i")
            if is_reverse:
                S_copy = query[2] + S_copy
            else:
                S_copy = S_copy + query[2]

if is_reverse:
    print(S_copy[::-1])
else:
    print(S_copy)


### FIXED CODE ###

#!/usr/bin/env python3

from collections import deque

S = str(input())
Q = int(input())
# print(S, Q)

is_reverse = False

d = deque()
d.append(S)
# print(d)

for i in range(Q):
    query = list(input().split())
    # print(query)
    if int(query[0]) == 1:
        # print("reverse")
        # Sを反転
        is_reverse = not is_reverse
    else:
        if int(query[1]) == 1:
            # Sの先頭にC_iを追加
            if is_reverse:
                d.append(query[2])
            else:
                d.appendleft(query[2])
        else:
            # Sの末尾にC_iを追加
            if is_reverse:
                d.appendleft(query[2])
            else:
                d.append(query[2])

if is_reverse:
    print("".join(d)[::-1])
else:
    print("".join(d))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    c = [[int(i)-1 for i in input().split()] for j in range(N)]
    from collections import defaultdict
    edge = defaultdict(set)
    deg = defaultdict(int)
    for i, A in enumerate(c):
        for j in range(N-2):
            if i < A[j]:
                if i < A[j+1]:
                    edge[(i, A[j])].add((i, A[j+1]))
                    deg[(i, A[j+1])] += 1
                else:
                    edge[(i, A[j])].add((A[j+1], i))
                    deg[(A[j+1], i)] += 1
            else:
                if i < A[j+1]:
                    edge[(A[j], i)].add((i, A[j+1]))
                    deg[(i, A[j+1])] += 1
                else:
                    edge[(A[j], i)].add((A[j+1], i))
                    deg[(A[j+1], i)] += 1

    from collections import deque
    que = deque()
    dist = defaultdict(int)
    for i in range(N):
        for j in range(i+1, N):
            if deg[(i, j)] == 0:
                que.append((i, j))  # root
                dist[(i, j)] = 1
    while que:
        u = que.popleft()
        for v in edge[u]:
            deg[v] -= 1
            dist[v] = max(dist[v], dist[u] + 1)
            if deg[v] == 0:
                que.append(v)

    if any(deg.values()):
        # 閉路検出
        print(-1)
    else:
        print(max(dist.values()))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    c = [[int(i) for i in input().split()] for j in range(N)]
    from collections import defaultdict
    edge = defaultdict(set)
    deg = defaultdict(int)
    for i, A in enumerate(c, start=1):
        for j in range(N-2):
            if i < A[j]:
                if i < A[j+1]:
                    edge[i*N+A[j]].add(i*N+A[j+1])
                    deg[i*N+A[j+1]] += 1
                else:
                    edge[i*N+A[j]].add(A[j+1]*N+i)
                    deg[A[j+1]*N+i] += 1
            else:
                if i < A[j+1]:
                    edge[A[j]*N+i].add(i*N+A[j+1])
                    deg[i*N+A[j+1]] += 1
                else:
                    edge[A[j]*N+i].add(A[j+1]*N+i)
                    deg[A[j+1]*N+i] += 1
    from collections import deque
    que = deque()
    dist = defaultdict(int)
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            # print(i, j, i*N+j)
            if deg[i*N+j] == 0:
                que.append(i*N+j)  # root
                dist[i*N+j] = 1
    while que:
        u = que.popleft()
        for v in edge[u]:
            deg[v] -= 1
            dist[v] = max(dist[v], dist[u] + 1)
            if deg[v] == 0:
                que.append(v)

    if any(deg.values()):
        # 閉路検出
        print(-1)
    else:
        print(max(dist.values()))


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

A, B, C=map(int, input().split())
K=int(input())
i=0
while i<K:
  if B<A:
    B*=2
    i+=1
  elif C<B:
    C*=2
    i+=1
    
if A<B<C:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

A, B, C=map(int, input().split())
K=int(input())
i=0
while i<K:
  if B<=A:
    B*=2
  elif C<=B:
    C*=2
  i+=1
    
if A<B<C:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

n = input()
data = map(int, input().split(" "))

ans = 1

over=False
zero=False
for num in data:
    ans*=num
    if(ans>1000000000000000000):
        over=True
    if(num == 0):
        zero=True

if ans>1000000000000000000:
    over=True

if zero:
    print("0")
elif over:
    print("-1")
else:
    print(ans)

### FIXED CODE ###

import sys
n = input()
data = list(map(int, sys.stdin.readline().split()))

ans = 1

over=False
zero=False

if 0 in data:
    zero=True

for num in data:
    ans*=num
    if(ans>1000000000000000000):
        over=True
        break

if ans>1000000000000000000:
    over=True

if zero:
    print("0")
elif over:
    print("-1")
else:
    print(ans)
### BUGGY CODE ###

from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        prev = now
# print(edges)
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
for V in vs:
    if used[V]: continue
    used[V] = 1
    q = deque([V])
    while len(q) > 0:
        v = q.popleft()
        for u in edges[v]: 
            if used[u] <= used[v]:
                q.append(u)
                used[u] = max(used[u], used[v] + 1)

print(max(used))

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
edges_r = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        edges_r[now].append(prev)
        prev = now
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
# for V in vs:
#     if used[V]: continue
#     used[V] = 1
#     q = deque([V])
#     while len(q) > 0:
#         v = q.popleft()
#         for u in edges[v]: 
#             if used[u] <= used[v]:
#                 q.append(u)
#                 used[u] = max(used[u], used[v] + 1)

for V in vs:
    if used[V]:continue
    used[V] = 1
    mx = 1
    for b in edges_r[V]:
        mx = max(mx, used[b]+1)
    used[V] = mx
# print(used)
print(max(used))
### BUGGY CODE ###

import math

a,b,n = map(int, input().split())
l = []
for i in range(n + 1):
  c = math.floor(a * i / b) - a * math.floor(i / b)
  l.append(c)
print(max(l))

### FIXED CODE ###

from math import floor

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

if n < b:
  c = floor(a * n / b) - a * floor(n / b)
else:
  c = floor(a * (b - 1) / b) - a * floor((b - 1) / b)
print(c)
### BUGGY CODE ###

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

count = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                count += 1
print(count)

### FIXED CODE ###

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

count = 0
for x in range(k+1):
    for y in range(k+1):
        if -1<s-x-y<k+1:
            count += 1
print(count)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
    b, c = map(int, input().split())
    a += [c] * b
print(sum(sorted(a, reverse=True)[:n]))

### FIXED CODE ###

from operator import itemgetter
import bisect

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
bc = sorted([list(map(int, input().split())) for i in range(m)], key=itemgetter(1), reverse=True)
bi = [bisect.bisect_left(a, bc[i][1]) for i in range(m)]
ans = 0
did = 0
for i in range(m):
    if bi[i] - did <= 0:
        continue
    if bi[i] - did > bc[i][0]:
        ans += bc[i][0] * bc[i][1]
        did += bc[i][0]
    else:
        ans += (bi[i] - did) * bc[i][1]
        did += (bi[i] - did)
print(sum(a[did:]) + ans)