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

# coding: utf-8
# Your code here!
n=int(input())
a = [int(i) for i in input().split()]
import sys
sys.setrecursionlimit(10**7)

ko = [0]*4
for i in a:
    ko[i] += 1

memo = [[[-1.0]*(n+1) for i in range(n+1)] for j in range(n+1)]
memo[0][0][0] = 0
"""
#print(dp,ko)
for i in range(n+1):
    for j in range(n+1-i):
        for k in range(ko[3]+1):
            t=i+j+k
#            print(i,j,k)
            if i != 0:
                dp[i][j][k] += (dp[i-1][j][k] + n/t)*i/t
            if j != 0:
                dp[i][j][k] += (dp[i+1][j-1][k] + n/t)*j/t
            if k != 0:
                dp[i][j][k] += (dp[i][j+1][k-1] + n/t)*k/t
        print(dp)
"""
def dfs(i,j,k):
    t=i+j+k
    ans = 0
    if memo[i][j][k] >= -0.5:
        return memo[i][j][k]
    if i != 0:
        ans += (dfs(i-1,j,k) + n/t)*i/t
    if j != 0:
        ans += (dfs(i+1,j-1,k) + n/t)*j/t
    if k != 0:
        ans += (dfs(i,j+1,k-1) + n/t)*k/t
    memo[i][j][k] = ans
    return ans
    
print(dfs(ko[1],ko[2],ko[3]))
#print(memo)


### FIXED CODE ###

# coding: utf-8
# Your code here!
n=int(input())
a = [int(i) for i in input().split()]
import sys
sys.setrecursionlimit(10**7)

ko = [0]*4
for i in a:
    ko[i] += 1

dp = [[[0.0]*(n+1) for i in range(n+1)] for j in range(n+1)]

cc=ko[1]+ko[2]+ko[3]
ccc=ko[2]+ko[3]
for k in range(ko[3]+1):
    for j in range(ccc+1-k):
        for i in range(cc+1-k-j):
            t=i+j+k
#            print(i,j,k)
            if i != 0:
                dp[i][j][k] += (dp[i-1][j][k] + n/t)*i/t
            if j != 0 and i < n:
                dp[i][j][k] += (dp[i+1][j-1][k] + n/t)*j/t
            if k != 0 and j < n:
                dp[i][j][k] += (dp[i][j+1][k-1] + n/t)*k/t
#print(dp)
print(dp[ko[1]][ko[2]][ko[3]])
### BUGGY CODE ###

import time

nk = [int(x) for x in raw_input().strip().split()]
d = []
for i in range(nk[0]):
    d_tmp = raw_input().strip().split()
    d.append([int(d_tmp[0]), int(d_tmp[1]), int(d_tmp[2] == 'B')])

n1 = nk[0]
k1 = nk[1]

check_x = [0] * n1 * 4
check_y = [0] * n1 * 4
for i in range(n1):
    check_x[i * 4] = d[i][0] - k1
    check_x[i * 4 + 1] = d[i][0] - k1 + 1
    check_x[i * 4 + 2] = d[i][0]
    check_x[i * 4 + 3] = d[i][0] + 1
    check_y[i * 4] = d[i][1] - k1
    check_y[i * 4 + 1] = d[i][1] - k1 + 1
    check_y[i * 4 + 2] = d[i][1]
    check_y[i * 4 + 3] = d[i][1] + 1
check_x = list(set(check_x))
check_y = list(set(check_y))

#d = tuple(d)
n = 0
#t = time.clock()
for i in check_x:
    for j in check_y:
        n_tmp = [0, 0]
        for k in range(n1):
            x = (d[k][0] - i) // k1 % 2
            y = (d[k][1] - j) // k1 % 2
#            if x == y:
#                n_tmp[1 - d[k][2]] += 1
#            else:
#                n_tmp[d[k][2]] += 1
            n_tmp[(x == y) ^ d[k][2]] += 1
        if n_tmp[0] > n:
            n = n_tmp[0]
        if n_tmp[1] > n:
            n = n_tmp[1]
#print time.clock() - t
print n


### FIXED CODE ###

import numpy as np

def getBoundary(p, k, k2):
    if p - k + 1 >= 0:
        return [(p - k + 1, p + 1)]
    else:
        return [(0, p + 1), ((p - k + 1) % k2, k2)]

n, k = map(int, input().strip().split())
k2 = k * 2
b = [[0 for i in range(k2 + 1)] for j in range(k2 + 1)]

for i in range(n):
    x_str, y_str, c_str = input().strip().split()
    x = int(x_str) % k2
    y = (int(y_str) + (c_str == 'B') * k) % k2
    for xb, xe in getBoundary(x % k2, k, k2):
        for yb, ye in getBoundary(y % k2, k, k2):
            b[xb][yb] += 1
            b[xb][ye] -= 1
            b[xe][yb] -= 1
            b[xe][ye] += 1
    for xb, xe in getBoundary((x + k) % k2, k, k2):
        for yb, ye in getBoundary((y + k) % k2, k, k2):
            b[xb][yb] += 1
            b[xb][ye] -= 1
            b[xe][yb] -= 1
            b[xe][ye] += 1

arr_b = np.array(b)
for i in range(k2):
    arr_b[i + 1] += arr_b[i]
for j in range(k2):
    arr_b[:, j + 1] += arr_b[:, j]
print(arr_b.max())
### BUGGY CODE ###

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

X = [[0 for j in range(510)] for i in range(510)]
C = [[0 for j in range(510)] for i in range(510)]

LR = []
for i in range(M):
    L, R = map(int, input().split())
    X[L][R] += 1

for i in range(1, N+1):
    for j in range(1, N+1):
        C[i][j] = C[i][j-1]+X[i][j]


for i in range(Q):
    p, q = map(int, input().split())
    sum = 0
    for j in range(p, q+1):
        sum += C[j][q]-C[j][p-1]
    print(sum)


### FIXED CODE ###

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

X = [[0 for j in range(510)] for i in range(510)]
C = [[0 for j in range(510)] for i in range(510)]

LR = []
for i in range(M):
    L, R = map(int, input().split())
    X[L][R] += 1

for i in range(1, N+1):
    for j in range(1, N+1):
        C[i][j] = C[i][j-1]+X[i][j]


for i in range(Q):
    p, q = map(int, input().split())
    sum = 0
    for j in range(p, q+1):
        sum += C[j][q]-C[j][p-1]
    print(sum)
### BUGGY CODE ###

S = input()
n = len(S)
T = [0]*2019
T[0]=1
t = 0
ans = 0
for i in range(n):
    t = (t + (int(S[-i-1]))*(10**i))%2019
    T[t] += 1
for j in T:
    ans +=int(j*(j-1)/2)
print(ans)

### FIXED CODE ###

S = input()
T = [0]*2019
T[0]=1
t = 0
ans = 0
dig = 1
for i in range(len(S)):
    t = (t + (int(S[-i-1]))*dig)%2019
    dig = (dig*10)%2019
    T[t] += 1
for j in T:
    ans +=int(j*(j-1)/2)
print(ans)
### BUGGY CODE ###

import itertools
n,k = map(int,input().split())
p = list(map(int,input().split()))
lstp = []
for i in range(n-k+1):
    lstp.append(p[i:i+k])
l = []
for ls in lstp:
    num = 0
    for j in range(k):
        num  += 0.5*(ls[j]+1)
        l.append(num)
print("{:.10f}".format(max(l)))

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
wa = sum(p[0:k])
next_wa = wa
for i in range(n-k):
    next_wa = next_wa - p[i] + p[i+k]
    if  next_wa > wa:
        wa = next_wa
print(0.5*(wa+k))
### BUGGY CODE ###

S = input()
Q = int(input())
rev = 1
for _ in range(Q):
    lst = input().split() 
    if (lst[0] == '1'):
        rev *= -1
    else:
        if (lst[1] == '1'):
            pos = rev
        else:
            pos = -1 * rev
        if (pos == 1):
            S = lst[2] + S
        else:
            S = S + lst[2]
print(S[::rev])


### FIXED CODE ###

S = input()
Q = int(input())
rev = 1
head = []
tail = []
for _ in range(Q):
    lst = input().split() 
    if (lst[0] == '1'):
        rev *= -1
    else:
        if (lst[1] == '1'):
            pos = rev
        else:
            pos = -1 * rev
        if (pos == 1):
            head.append(lst[2])
        else:
            tail.append(lst[2])
ans = ''.join(head[::-1]) + S + ''.join(tail)
print(ans[::rev])
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0,abs(h[0]-h[1])]
for i in range(2,N):
  s = []
  for j in range(max(0,i-K),i):
    s.append(dp[j]+abs(h[j]-h[i]))
  dp.append(min(s))
print(dp[N-1])

### FIXED CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
DP = [0]
for i in range(1,N):
    a = DP[i-1] + abs(H[i]-H[i-1])
    for j in range(2,min(K,i)+1):
        b = DP[i-j] + abs(H[i]-H[i-j])
        a = min(a,b)
    DP.append(a)
print(DP[N-1])
### BUGGY CODE ###

import sys


def resolve():
    readline = sys.stdin.readline

    N, W = map(int, readline().split())
    lst = [list(map(int, readline().split())) for x in [0] * N]

    # 配るDP
    # dp[i][sum_v]はi個の品物の内でsum_v以上となる最小の重量
    V = N * 10 ** 3 + 1  # 価値の最大値
    inf = 10 ** 10
    dp = [[inf] * V for _ in [0] * (N + 1)]
    dp[0][0] = 0

    for i in range(N):
        for sum_v in range(V):
            weight, value = lst[i]
            if sum_v - value >= 0:
                dp[i + 1][sum_v] = min(dp[i + 1][sum_v],
                                       dp[i][sum_v - value] + weight)
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v])

    ans = 0
    for sum_v in range(V):
        if dp[N][sum_v] <= W:
            ans = sum_v
    print(ans)
    

resolve()


### FIXED CODE ###

import sys


def resolve():
    readline = sys.stdin.readline

    N, W = map(int, readline().split())
    lst = [list(map(int, readline().split())) for x in [0] * N]

    # 配るDP
    # dp[i][sum_v]はi個の品物の内でsum_v以上となる最小の重量
    V = N * 10 ** 3 + 1  # 価値の最大値
    inf = 10 ** 10
    dp = [[inf] * V for _ in [0] * (N + 1)]
    dp[0][0] = 0

    for i in range(N):
        for sum_v in range(V):
            weight, value = lst[i]
            if sum_v - value >= 0:
                dp[i + 1][sum_v] = min(dp[i + 1][sum_v],
                                       dp[i][sum_v - value] + weight)
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v])

    ans = 0
    for sum_v in range(V):
        if dp[N][sum_v] <= W:
            ans = sum_v
    print(ans)
    

resolve()
### BUGGY CODE ###

from collections import deque
n = int(input())
r = range(1, n+1)
p = deque(r)
p.rotate(-1)
print(sum(i%p[i-1] for i in r))

### FIXED CODE ###

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

import itertools

def main():
    N = int(input())
    A = tuple(int(c) for c in input().split(' '))
    l = []
    for i, a in enumerate(A):
        l.append((i+1, a))
    l.sort(key=lambda x: x[1])
    #print(l)
    cnt = 0
    for a, b in itertools.combinations(l, 2):
        if abs(a[0] - b[0]) == a[1] + b[1]:
            cnt += 1
    print(cnt)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#解説を見て実装
from collections import Counter

def main():
    N = int(input())
    A = tuple(int(c) for c in input().split(' '))
    L = [i+a for i, a in enumerate(A)]
    R = [i-a for i, a in enumerate(A)]
    #print(L)
    #print(R)

    #はじめL_t = defaultdict(list)としてiの候補を追加していったが、iとjは重複しないのでチェックが不要
    L_t = Counter(L)
    R_t = Counter(R)
    cnt = 0
    x_candidate = set(L) & set(R)
    for x in x_candidate:
        l_candidate = L_t[x]
        r_candidate = R_t[x]
        cnt += l_candidate * r_candidate

    print(cnt)

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

import math

def main():

    test = int(input())
    inp = input().split(' ')

    p=1;
    for x in inp:
        p = p*int(x)
    
    if(p>10**18):
        print(-1);
    else:
        print(p);

        
        

if __name__ == '__main__':
    main()

### FIXED CODE ###

import math

def main():

    test = int(input())
    inp = input().split(' ')
    inp = sorted(inp)
    p=1;
    for x in inp:
        p = p*int(x)
        if p> 10**18 or p==0:
            break;
    
    if(p>10**18):
        print(-1);
    else:
        print(p);

        
        

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

n = int(input())
s = input()
while True:
  c = 0
  for i in range(len(s)):
    if s[i] == "(":
      c += 1
    else:
      c -= 1
    if c < 0:
      s = "(" + s
      break
  if c > 0:
    s = s + ")"
  if c == 0:
    print(s)
  


### FIXED CODE ###

n = int(input())
s = input()
while True:
  c = 0
  for i in range(len(s)):
    if s[i] == "(":
      c += 1
    else:
      c -= 1
    if c < 0:
      s = "(" + s
      break
  if c > 0:
    s = s + ")"
  if c == 0:
    print(s)
    break
### BUGGY CODE ###

#import sys

#input = sys.stdin.readline

import heapq

def main():
#    h,w,a,b = map(int, input().split())
    a,b=map(int,input().split())
    m=2
    k=1
    c=max(a,b)
    count=1
    sosu=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
    for i in range(len(sosu)):
        if a%sosu[i]==0 and b%sosu[i]==0:
            count+=1
            a//=sosu[i]
            b//=sosu[i]
        elif a%sosu[i]==0:
            a//=sosu[i]
        elif b%sosu[i]==0:
            b//=sosu[i]


    while m < c:
        m = 6 * k +1
        if a % m == 0 and b % m == 0:
            count += 1
            a//=m
            b//=m
        elif a%m==0:
            a//=m
        elif b%m==0:
            b//=m
 #           print(count)
        k += 1
    k = 1
    m = 2
    while m < c:
        m = 6 * k -1
        if a % m == 0 and b % m == 0:
            count += 1
            a//=m
            b//=m
        elif a%m==0:
            a//=m
        elif b%m==0:
            b//=m
        k += 1
    print(count)
#    for i in range(h):
#            print(aaa)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#import sys

#input = sys.stdin.readline

#import heapq
import math
import fractions

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True

def main():
#    h,w,a,b = map(int, input().split())
    a,b=map(int,input().split())
    m=4
    k=1

    count=1
    if a>b:
        a,b=b,a
    sosu=set()
    a = fractions.gcd(a,b)
    if a%2==0:
        sosu.add(2)
        while a%2==0:
            a//=2
    if a%3==0:
        sosu.add(3)
        while a%3==0:
            a//=3
#    print(d)
    c=math.sqrt(a)+1
 #   print(c)
    while m<=c and m!=1:
        if a%m==0:
            sosu.add(m)
            while a%m==0:
                a//=m

        m+=1
#    print(sosu)
    if sosu==set() and a!=1:
        sosu.add(a)
    if sosuhante(a) and a!=1:
        sosu.add(a)
#    print(sosu)
    count+=len(sosu)
    print(count)
#    for i in range(h):
#            print(aaa)

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

import numpy as np

def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=np.array([[inf for i in range(W+1)] for j in range(N+1)])
  dp[0][0]= 0
  #DP
  for i in range(N):
    for w in range(W+1):
      if 0 <= w-weight[i]: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=min(dp[i+1][w-weight[i]]+value[i], dp[i][w])
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
H,N = map(int,input().split())
 
weight=[]
value=[]
for i in range(N):
    n,a=input().split()
    weight.append(int(n))
    value.append(int(a))
MAX = max(weight)
dp = knapsack(N,H+MAX,weight,value)
 
print(int(min(dp[N][H:H+MAX])))

### FIXED CODE ###

def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[inf for i in range(W+1)] for j in range(N+1)]
  dp[0][0]= 0
  #DP
  for i in range(N):
    for w in range(W+1):
      if 0 <= w-weight[i]: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=min(dp[i+1][w-weight[i]]+value[i], dp[i][w])
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
H,N = map(int,input().split())
 
weight=[]
value=[]
for i in range(N):
    n,a=input().split()
    weight.append(int(n))
    value.append(int(a))
MAX = max(weight)
dp = knapsack(N,H+MAX,weight,value)
 
print(min(dp[N][H:H+MAX]))
### BUGGY CODE ###

import numpy as np

H, W = map(int, input().split())

maze_x = [input() for _ in range(H)]
maze_y = [''.join(x) for x in zip(*maze_x)]

def count_light(maze, W, H):
    cnt = [[0]*W for _ in range(H)]
    for hh in range(H):
        lst1 = [i for i in maze[hh].split('#') if i != '']
        lst2 = [i for i in maze[hh].split('.') if i != '']
        
        ww = 0
        k1 = 0
        k2 = 0
        
        while 0 <= ww <= W - 1:
            if maze[hh][ww] == '.':
                ln = len(lst1[k1])
                cnt[hh][ww:ww+ln] = [ln]*ln
                ww += ln
                if len(lst1)==k1:break
                k1 += 1
            else:
                ln = len(lst2[k2])
                cnt[hh][ww:ww+ln] = [0]*ln
                ww += ln
                k2 += 1
    return cnt
cnt = (np.array(count_light(maze_x, W, H)) + np.array(count_light(maze_y, H, W)).T -1)

print(max([max(cnt[i]) for i in range(H)]))


### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())

maze01 = np.array([[int(x=='.') for x in input()] for _ in range(H)]) 

u = np.zeros((H, W), dtype=np.int32)
d = np.zeros((H, W), dtype=np.int32)
r = np.zeros((H, W), dtype=np.int32)
l= np.zeros((H, W), dtype=np.int32)


u[0] = maze01[0]
d[H - 1] = maze01[H - 1]
for hh in range(1,H):
    u[hh] = u[hh-1] + maze01[hh]
    u[hh] *= maze01[hh]
    d[H - hh - 1] = d[H - hh] + maze01[H - hh - 1]
    d[H - hh - 1] *= maze01[H - hh - 1]

l[:, 0] = maze01[:, 0]
r[:, W - 1] = maze01[:, W - 1]
for ww in range(1, W):
    l[:, ww] = l[:, ww -1] + maze01[:, ww]
    l[:, ww] *= maze01[:, ww]
    r[:, W - ww -1] = r[:, W - ww] + maze01[:, W - ww - 1]
    r[:, W - ww -1] *= maze01[:, W - ww - 1]

cnt = r + l + u + d - 3

print(max([max(cnt[i]) for i in range(H)]))
### BUGGY CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(int,input().split()))
heapq.heapify(A)
for _ in range(M):
    B,C=map(int,input().split())
    for _ in range(B):
        a = heapq.heappop(A)
        if C <= a:
            heapq.heappush(A, a)
            break
        else:
            heapq.heappush(A,C)
print(sum(A))


### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(int,input().split()))
heapq.heapify(A)
numbers=[]
for _ in range(M):
    B,C=map(int,input().split())
    numbers.append([C,B])
numbers=sorted(numbers,reverse=True)
for number in numbers:
    B=number[1]
    C=number[0]
    for _ in range(B):
        a = heapq.heappop(A)
        if C <= a:
            heapq.heappush(A, a)
            break
        else:
            heapq.heappush(A,C)
print(sum(A))
### BUGGY CODE ###

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

maxn = 10**18
ans = 1
for k in a:
    ans *= k

if ans > maxn:
    ans = -1

print(ans)


### FIXED CODE ###

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

for k in a:
    if k == 0:
        print(0)
        exit()

maxn = 10**18
ans = 1
for k in a:
    ans *= k
    if ans > maxn:
        ans = -1
        break


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

s=list(map(str,input()))
c=0
while "1" and "0" in s:
    for i in range(1,len(s)):
        if s[i-1] != s[i]:
            del s[i-1]
            del s[i-1]
            c+=2
            break
        else:
            pass
print(c)


### FIXED CODE ###

import collections
s=list(map(str,input()))
c=collections.Counter(s)
print(2*min(c["1"],c["0"]))
### BUGGY CODE ###

n=int(input())
s=[input() for i in range(n)]
cnt=0
ans=[]

for i in s:
    cnt=max(cnt,s.count(i))

for j in s:
    if cnt==s.count(j):
        if j not in ans:
            ans.append(j)

ans=sorted(ans)
for k in ans:
    print(k)

### FIXED CODE ###

import collections as co
n=int(input())
s=[input() for i in range(n)]

x=co.Counter(s)
x=x.most_common()
ans=[]
m=0

for i in x:
    if i[1]<m:
        break
    else:
        ans.append(i[0])
        m=i[1]

ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

s= input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0 for _ in range(lt+1) ]  for _ in range(ls+1)] #dp[i][j] sがi文字目,tがj文字目まででのLCS
for ids in range(1,ls+1):
    for idt in range(1,lt + 1):
        #一致してたら文字を足す
        if s[ids-1] == t[idt-1]:
            dp[ids][idt] =dp[ids-1][idt-1] + 1
        #違っていたら、長い方の文字を採用
        elif s[ids-1] != t[idt-1]:
            if dp[ids][idt-1] >= dp[ids-1][idt]:
                dp[ids][idt] = dp[ids][idt-1]
            else:
                dp[ids][idt] = dp[ids-1][idt]
ans = ''
num=dp[-1][-1]
ids = ls;idt=lt
while num:
    if dp[ids][idt] == dp[ids][idt-1]:
        idt -= 1
    elif dp[ids][idt] == dp[ids-1][idt]:
        ids -=1
    elif dp[ids][idt] ==dp[ids-1][idt-1] + 1:
        ans += s[ids-1]
        num -=1
        idt -= 1
        ids -=1
print(ans[::-1])



### FIXED CODE ###

s= input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0 for _ in range(lt+1) ]  for _ in range(ls+1)] #dp[i][j] sがi文字目,tがj文字目まででのLCS
for ids in range(1,ls+1):
    for idt in range(1,lt + 1):
        #一致してたら文字を足す
        if s[ids-1] == t[idt-1]:
            dp[ids][idt] =dp[ids-1][idt-1] + 1
        #違っていたら、長い方の文字を採用
        elif s[ids-1] != t[idt-1]:
            if dp[ids][idt-1] >= dp[ids-1][idt]:
                dp[ids][idt] = dp[ids][idt-1]
            else:
                dp[ids][idt] = dp[ids-1][idt]
ans = ''
num=dp[-1][-1]
ids = ls;idt=lt
while num:
    if dp[ids][idt] == dp[ids][idt-1]:
        idt -= 1
    elif dp[ids][idt] == dp[ids-1][idt]:
        ids -=1
    elif dp[ids][idt] ==dp[ids-1][idt-1] + 1:
        ans += s[ids-1]
        num -=1
        idt -= 1
        ids -=1
print(ans[::-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc = sorted(bc, key=lambda x:x[1], reverse=True)
for [b,c] in bc:
    if c < a[0]:
        continue
    for i in range(b):
        if c < a[i]:
            break
        a[i] = c
    a.sort()
print(sum(a))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        break
for i in range(n):
    if len(l) <= i or l[i] <= a[i]:
        break
    a[i] = l[i]
print(sum(a))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
nums = []

for i in range(1,n+1):
    nums.append(a.count(i))
    if i != n:
        a.pop(0)

for i in nums:
	print(i)

### FIXED CODE ###

N = int(input())
A = map(int, input().split())
subs = [0] * N

for boss in A:
  subs[boss-1] += 1

for i in subs:
  print(i)
### BUGGY CODE ###

n, h, *t=map(int,open(0).read().split())
a = sorted(t[::2])
b = sorted(t[1::2])
b_high = [i for i in b if all(i >= j for j in a)]
if (h - sum(b_high)) % a[-1] == 0:
  print(len(b_high) + (h - sum(b_high)) // a[-1])
else:
  print(len(b_high) + ((h - sum(b_high)) // a[-1]) + 1)


### FIXED CODE ###

n, h, *t=map(int,open(0).read().split())
a = t[::2]
b = t[1::2]
ma = max(a)
b_high = [i for i in b if i > ma]
if sum(b_high) > h:
  ans = 0
  b_high = sorted(b_high)
  while h > 0:
    h = h - b_high.pop()
    ans += 1
  print(ans)
else:
  if (h - sum(b_high)) % ma == 0:
    print(len(b_high) + (h - sum(b_high)) // ma)
  else:
    print(len(b_high) + ((h - sum(b_high)) // ma) + 1)
### BUGGY CODE ###

n = input()
n = int(n)
y = input()
list = y.split(' ')
nums = []

for i in range(n):
    i = i + 1
    nums.append(i)

for i in nums:
    i = str(i)
    print(list.count(i))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
nums = [0] * n

for i in a:
    nums[i-1] += 1

print("\n".join(map(str, nums)))
### BUGGY CODE ###

#!usr/bin/env python3
import sys

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, b = map(int, input().split())
    bits = sum([1 << (i - 1) for i in map(int, input().split())])
    keys.append([a, bits])

dp = [[INF] * (2 ** N + 10) for _ in range(M + 10)]
dp[0][0] = 0

for i in range(M):
    for j in range(2 ** N):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][j | keys[i][1]] = min(dp[i + 1][j | keys[i][1]], dp[i][j] + keys[i][0])
print(dp[M][2 ** N - 1] if dp[M][2 ** N - 1] != INF else -1)

### FIXED CODE ###

#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, b = map(int, input().split())
    bits = 0
    for i in map(int, input().split()):
        bits = bits | (1 << (i - 1))
    keys.append([a, bits])

dp = [[INF] * (2 ** N + 10) for _ in range(M + 10)]
dp[0][0] = 0

for i in range(M):
    for j in range(2 ** N):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][j | keys[i][1]] = min(dp[i + 1][j | keys[i][1]], dp[i][j] + keys[i][0])
print(dp[M][2 ** N - 1] if dp[M][2 ** N - 1] != INF else -1)