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

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
# dp[i][j][k] i番目まで見て和がjとなる総数
# k=0がL,Rが決まっていない、k=1がLだけ決定、k=2がLとRが決定
dp = [[[0] * 3 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(S+1):
        zero = dp[i][j][0]
        one = dp[i][j][1]
        two = dp[i][j][2]
        dp[i+1][j][0] += zero
        dp[i+1][j][1] += zero + one
        dp[i+1][j][2] += zero + one + two
        if a + j <= S:
            dp[i+1][j+a][1] = zero + one
            dp[i+1][j+a][2] = zero + one

answer = dp[N][S][2] % MOD
print(answer)
# 11


### FIXED CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
dp = [0] * (S+1)
answer = 0
for a in A:
    dp[0] += 1 # Lの数は１個ずつ加わる
    prev = dp.copy()
    for i in range(S-a+1):
        dp[i+a] += prev[i]
    answer += dp[-1] # その位置Rとした時

print(answer % MOD)
# 26
### BUGGY CODE ###

N, M = list(map(int, input().split()))
sigma = list(map(int, input().split()))
gokans = []

for i in range(M):
    pair = tuple(map(int, input().split()))
    gokans.append(pair)

def connected(i, j, paths):
    if [pair for pair in paths if i in pair] and [pair for pair in paths if j in pair]:
        chain_i = [pair for pair in paths if i in pair]
        chain_j = [pair for pair in paths if j in pair]
        for pair in set(chain_i + chain_j):
            paths.remove(pair)
        narabi_i = set([couple[0] for couple in chain_i] + [couple[1] for couple in chain_i])
        narabi_j = set([couple[0] for couple in chain_j] + [couple[1] for couple in chain_j])
        if narabi_i & narabi_j != set():
            return True
        new_chain_i = [0]
        new_chain_j = [1]
        while new_chain_i or new_chain_j:
            new_chain_i = []
            new_chain_j = []
            for pair in chain_i:
                new_chain_i += [couple for couple in paths if set(couple) & set(pair) != set()]
            for pair in chain_j:
                new_chain_j += [couple for couple in paths if set(couple) & set(pair) != set()]
            for pair in set(new_chain_i + new_chain_j):
                paths.remove(pair)
            chain_i += new_chain_i
            chain_j += new_chain_j
            narabi_i = set([couple[0] for couple in new_chain_i] + [couple[1] for couple in new_chain_i])
            narabi_j = set([couple[0] for couple in new_chain_j] + [couple[1] for couple in new_chain_j])
            if narabi_i & narabi_j != set():
                return True
        return False
    else:
        return False

count = 0
for i in range(1, N+1):
    if i != sigma[i-1]:
        gokans1 = gokans.copy()
        if connected(i, sigma[i-1], gokans1):
            count += 1
    else:
        count += 1
print(count)

### FIXED CODE ###

n,m = map(int, input().split())
p = list(map(int, input().split()))

par = [i for i in range(n)]
#rootの計算量は、parが最初の状態に近いほど値は小さくて、高々O(n)
def root(x):
	tmp = par[x]
	if tmp == x:
		return x
	else:
		a = root(tmp)
		par[x] = a
		return a

def merge(x, y):
	x = root(x)
	y = root(y)
	if x != y:
		par[x] = y
		return

for i in range(m):
	x, y = map(int, input().split())
	merge(x-1, y-1)
	#print(par)

ans = 0

for i in range(n):
	if p[i]-1 == i:
		ans += 1
	elif root(p[i]-1) == root(i):
		ans += 1
print(ans)
### BUGGY CODE ###

import random
import sys
import time
import copy

input = sys.stdin.readline

def main():
    d = int(input())
    c = list(map(int, input().split()))
    s = []
    for _ in range(d):
        s.append(list(map(int, input().split())))
    
    start_time = time.time()
    beamwidth = 5
    suff = 0
    # while True:
    #     elapsed_time = time.time() - start_time
    #     if elapsed_time >= 1.8:
    #         break
        
    # ここから
    topk = [{"last": [0 for _ in range(26)], "score": 0, "ans": []} for _ in range(beamwidth)]
    for i in range(d):
        # print(i)
        # print(*topk, sep='\n')
        # 各候補に対して top-k を生成
        nnnnn = []  # top-k * top-k 
        for bi in range(beamwidth):
            last = topk[bi]["last"]
            tmpsufss = []
            for con in range(26):
                tmpsufss.sort(key=lambda x: -x["score"])
                ttttt = topk[bi]["score"] + s[i][con]
                minus = 0
                for j in range(26):
                    if con == j:
                        continue
                    minus -= (i - last[j]) * c[j]
                ttttt += minus

                if len(tmpsufss) < beamwidth:
                    tmpsufss.append({
                        "last": copy.deepcopy(last),
                        "score": ttttt,
                        "ans": copy.deepcopy(topk[bi]["ans"])
                    })
                    tmpsufss[-1]["last"][con] = i
                    tmpsufss[-1]["ans"].append(con)
                else:
                    if tmpsufss[-1]["score"] < ttttt:
                        tmpsufss.pop()
                        tmpsufss.append({
                            "last": copy.deepcopy(last),
                            "score": ttttt,
                            "ans": copy.deepcopy(topk[bi]["ans"])
                        })
                        tmpsufss[-1]["last"][con] = i
                        tmpsufss[-1]["ans"].append(con)
            nnnnn.extend(tmpsufss)

        nnnnn.sort(key=lambda x: -x["score"])
        topk = nnnnn[:beamwidth]
        

    print(*[a + 1 for a in topk[0]["ans"]])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import random
import sys
import time

input = sys.stdin.readline

def main():
    # start_time = time.time()
    # while True:
    #     elapsed_time = time.time() - start_time
    #     if elapsed_time >= 2.0:
    #         print(elapsed_time)
    #         return 0
    d = int(input())
    c = list(map(int, input().split()))
    s = []
    for _ in range(d):
        s.append(list(map(int, input().split())))
    for _ in range(d):
        print(1)

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

N,K=map(int,input().split())
H=list(map(int,input().split()))
INF=10**10
dp=[INF for _ in range(N)]
dp[0]=0
for i in range(N):
    for k in range(1,K+1):
        if i+k<N:
            dp[i+k] = min(dp[i+k],dp[i]+abs(H[i+k]-H[i]))
print(dp[N-1])

### FIXED CODE ###

N,K=map(int,input().split())
# numpyを使うと早い操作も単純だから
import numpy as np
H=np.array(list(map(int,input().split())))
INF=10**10
dp=np.array([INF for _ in range(N)])
dp[0]=0
for i in range(N):
    dp[i:i+K+1] = np.minimum(dp[i:i+K+1],dp[i]+np.abs(H[i:i+K+1]-H[i]))
print(dp[N-1])
### BUGGY CODE ###

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

s=0
c=0
while c+A<N:
    c=c+A+B
    s=s+A

if c>=N:
    print(s)
else:
    print(s+N-c)

### FIXED CODE ###

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

c=(A+B)*(N//(A+B))
s=A*(N//(A+B))

if c+A<=N:
    print(s+A)
else:
    print(s+N-c)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
cnt=0
for i in a:
  if b==[] or min(b)>=i:
    cnt+=1
    b.append(i)
  else:
    b.append(i)
print(cnt)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=2*10**5
cnt=0
for i in a:
  if b>=i:
    cnt+=1
    b=i

print(cnt)
### BUGGY CODE ###

N = int(input())
lis = []
for i in range(N):
  A = int(input())
  if A in lis:
    lis.remove(A)
  else:
    lis.append(A)
print(len(lis))

### FIXED CODE ###

N = int(input())
dic = {}
for i in range(N):
  A = int(input())
  if A not in dic:
    dic[A]=1
  else:
    dic[A]^=1
print(sum(dic.values()))
### BUGGY CODE ###

N, X, Y = map(int, input().split())
l = []
for i in range(1, N):
    for j in range(i+1, N+1):
        s = j -i
        if 0 < i < X and Y <= j:
            ss = j - i - (Y - X) + 1
            l.append(ss)
        elif 0 < i < X and X < j < Y:
            ss = X - i + 1 + Y - j
            l.append(min(s, ss))
        elif 0 < i < X and i < j<= X:
            l.append(s)
        elif Y > i >= X and Y >= j > i:
            ss = i - X + 1 + Y - j
            l.append(min(s, ss))
        elif Y > i >= X and Y < j:
            ss = j - Y + 1 + i -X
            l.append(min(s, ss))
        elif i >= Y and j > Y:
            l.append(s)
for i in range(1, N):
    print(l.count(i))

### FIXED CODE ###

N, X, Y = map(int, input().split())
l = [0] * (N-1)
for i in range(1, N):
    for j in range(i+1, N+1):
        s = j -i
        if 0 < i < Y:
            ss = abs(j - Y) + abs(X - i) + 1 
            l[min(s, ss)-1] += 1
        elif i >= Y:
            l[s-1] += 1
for i in range(N-1):
    print(l[i])
### BUGGY CODE ###

def main():
    N = int(input())
    P = [int(x) for x in input().split()]
    count = 0
    for i in range(N):
        k = True
        for j in range(i):
            if P[i] > P[j]:
                k = False
                break
        if k:
            count += 1
    print(count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    P = [int(x) for x in input().split()]
    count = 1
    num = P[0]
    for i in range(1, N):
        if num >= P[i]:
            count += 1
            num = P[i]
    print(count)


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

n = int(input())
a = list(map(int, input().split()))
b = [j+1 for i in range(n) for j in range(n) if a[j] == (i+1)]

#for i in range(n)
print(*b)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
#b = [j+1 for i in range(n) for j in range(n) if a[j] == (i+1)]
c = [0]*n
for i in range(n):
    c[a[i]-1] = i+1

print(*c)
### BUGGY CODE ###

import re
import sys
s = sys.stdin.readlines()
N, Q = map(int, s[0].split())
S = s[1]
acl = [0]*len(S)
ac_iter = re.finditer("AC", S)
for a in ac_iter:
    acl[a.span()[0]] = 1
for i in s[2:]:
    a, b = map(int, i.split())
    minus = 1 if acl[b-1] == 1 else 0
    print(sum(acl[a-1:b]) - minus)

### FIXED CODE ###

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

acl = [0]*(N+1)

for i in range(N):
    acl[i+1] = acl[i] + (1 if S[i:i+2] == "AC" else 0)

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

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

    d = MyDict()

    for _ in range(n):
        cmd, value = stdinput().split()
        if cmd == 'insert':
            d.insert(value)
        elif cmd == 'find':
            if d.find(value):
                print('yes')
            else:
                print('no')


class MyDict():
    def __init__(self):
        self.stacks = {
            'A': [],
            'C': [],
            'G': [],
            'T': []
        }
    
    def insert(self, value):
        st = self.stacks[value[0]]
        st.append(value[1:])
        self.stacks[value[0]] = sorted(st)
    
    def find(self, value):
        st = self.stacks[value[0]]
        return binary_search(st, len(st), value[1:])

def binary_search(S, n, t):
    left = 0
    right = n - 1
    while left <= right:
        mid = (left + right) // 2
        if S[mid] == t:
            return True
        elif S[mid] > t:
            right = mid - 1
        else:
            left = mid + 1
    
    return False

def stdinput():
    from sys import stdin
    return stdin.readline().strip()

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')


### FIXED CODE ###

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

    st = [None] * (4**12)

    for _ in range(n):
        cmd, value = stdinput().split()
        if cmd == 'insert':
            st[get_hash(value)] = 1
        elif cmd == 'find':
            if st[get_hash(value)] == 1:
                print('yes')
            else:
                print('no')

CODES = {'A' : 1, 'C' : 2, 'G' : 3, 'T' : 4}
def get_hash(s):
    base = 1
    h = 0
    for c in s:
        code = CODES[c]
        h += code * base
        base *= 4
    return h

def stdinput():
    from sys import stdin
    return stdin.readline().strip()

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')
### BUGGY CODE ###

import sys
N, M = map(int, input().split())

G = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    G[u-1].append(v-1)

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


par = [i for i in range(3*N)]
par2 = [-1 for i in range(3*N)]
rank = [0 for i in range(3*N)]

def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

def same(x, y):
    return find(x) == find(y)

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

ans = 0
start = [S-1]
frag = 1
g = -1
while frag:
    frag = 0
    ans += 1
    g += 1
    g %= 3
    l = len(start)
    for i in range(l):
        s = start.pop(0)
        if par2[s + g * N] == 1:
            continue
        par2[s + g * N] == 1
        for j in range(len(G[s])):
            start.append(G[s][j])
            if g == 2:
                if same(s + 2 * N, G[s][j]):
                    continue
                else:
                    frag = 1
                    unite(s + 2 * N, G[s][j])

            else:
                if same(s + g * N, G[s][j] + (g+1) * N):
                    continue
                else:
                    frag = 1
                unite(s+ g * N, G[s][j] + (g+1) * N)

        if same(S-1, T-1) and par[S-1] != -1:
            print(ans//3)
            sys.exit()
print(-1)

### FIXED CODE ###

import sys
import heapq
N, M = map(int, input().split())

G = [[] for i in range(3*N)]
for i in range(M):
    u, v = map(int, input().split())
    G[u-1].append([v-1 + N, 1])
    G[u-1 + N].append([v-1 + 2*N, 1])
    G[u-1 + 2*N].append([v-1, 1])

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

INF = 10**10
d = [INF for i in range(3*N)]

que = []
d[S-1] = 0
heapq.heappush(que, [0, S-1])

while not(len(que) == 0):
    q = heapq.heappop(que)
    ver = q[1]
    dis = q[0]
    
    if d[ver] < dis:
        continue

    for i in range(len(G[ver])):
        e = G[ver][i]
        if d[e[0]] > d[ver] + e[1]:
            d[e[0]] = d[ver] + e[1]
            heapq.heappush(que, [d[e[0]], e[0]])

if d[T-1] == INF:
    print(-1)
else:
    print(d[T-1]//3)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
m = max(A)
for i in range(N):
  if m == A[i]:
    B = A.pop(i)
    print(max(A))
    A.insert(i,B)
  else:
    print(m)

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
B = list(A)
B.sort()
m1 = B[N-1]
m2 = B[N-2]
#a = A.count(m1)
for i in range(N):
  if A[i] == m1:
    print(m2)
  else:
    print(m1)
### BUGGY CODE ###

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

dp=[float('inf')]*N
dp[0]=0
dp[1]=abs(H[1]-H[0])

for n in range(2,N):
    if n-K>0:
        s=n-K
    else:
        s=0
    l=[]
    for i in range(s,n):
        l.append(dp[i]+abs(H[n]-H[i]))
    dp[n]=min(l)

print(dp[N-1])

### FIXED CODE ###

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

dp=[float('inf')]*N
dp[0]=0
dp[1]=abs(H[1]-H[0])

for n in range(2,N):
    if n-K>0:
        dp[n]=min([(dp[i]+abs(H[n]-H[i]))for i in range(n-K,n)])
    else:
        dp[n]=min([dp[i]+abs(H[n]-H[i])for i in range(0,n)])

print(dp[N-1])
### BUGGY CODE ###

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    B = []
    ans = 10**9

    for i, a in enumerate(A):
        B.append(a - i - 1)

    for b in set(B):
        tmp = 0
        for i, a in enumerate(A):
            tmp += abs(a - i - b - 1)
        ans = min(ans, tmp)

    print(ans)


### FIXED CODE ###

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    B = []
    ans = 0
 
    for i, a in enumerate(A):
        B.append(a - i - 1)

    B.sort()

    b = B[len(B)//2]
    for i, a in enumerate(A):
        ans += abs(a - b - i - 1)

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

#200322D
N = int(input())
A = list(map(int,input().split()))
count = []

AllCount = 0
for i in range(N):
    icount = 0   
    for j in range(N):
        if A[i] == A[j]:
            icount += 1
            AllCount += 1
    count.append(icount)
            
for i in range(N):            
    print(int((AllCount-N)/2-count[i] + 1))

### FIXED CODE ###

#200322D
from collections import Counter

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

c = Counter(A)
#print(c)
#print(c[1])
#print(c[A[0]])
L = len(c)
#print(L)

def nCm(x):
    return x * (x - 1) / 2

c_list = list(c.keys())

All = 0
for i in range(L):
    All += nCm(c[c_list[i]])

for i in range(N):
    Ans = All - (c[A[i]]) + 1
    print(int(Ans))
### BUGGY CODE ###

n = int(input())
g = int(input())
for _ in range(n-1):
    t = int(input())
    r = max(t, g)
    l = min(t, g)
    i = 1
    while True:
        if (r*i) % l == 0:
            g = r * i
            break
        i += 1
print(g)


### FIXED CODE ###

from fractions import gcd
def lcm(a, b):
    return a * b // gcd(a, b)

n = int(input())
g = int(input())
for _ in range(n-1):
    t = int(input())
    g = lcm(g, t)
print(g)
### BUGGY CODE ###



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

Rcnt = 0
Gcnt = 0

excep = 0

for i in range(len(S)):
    if S[i] == 'R':
        Rcnt += 1
    elif S[i] == 'G':
        Gcnt += 1
    for j in range(1, len(S)):
        # if i+j+j < len(S) and S[i] != S[i+j]:
        if i+j+j < len(S) and S[i] != S[i+j] and S[i] != S[i+j+j] and S[i+j] != S[i+j+j]:
            excep += 1

RGBcalc = Rcnt * Gcnt * (N - Rcnt - Gcnt)

print(RGBcalc - excep)

### FIXED CODE ###



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

Rcnt = 0
Gcnt = 0

excep = 0

for i in range(len(S)):
    if S[i] == 'R':
        Rcnt += 1
    elif S[i] == 'G':
        Gcnt += 1
    for j in range(1, len(S)):
        if i+j+j < len(S) and S[i] != S[i+j]:
            if S[i] != S[i+j+j] and S[i+j] != S[i+j+j]:
                excep += 1
        elif i+j+j >= len(S):
            break

print(Rcnt * Gcnt * (N - Rcnt - Gcnt) - excep)
### BUGGY CODE ###

N = int(input())
a = []
if N == 0:
    a = ["0"]
while N != 0:
    a.append(str(N % 2))
    N = -(N - N % 2) 
print("".join(list(reversed(a))))

### FIXED CODE ###

N = int(input())
a = []
if N == 0:
    a = ["0"]
while N != 0:
    a.append(str(N % 2)) # N mod 2
    N = -(N - N % 2) // 2 # (N − (N mod 2)) // 2
print("".join(list(reversed(a))))
### BUGGY CODE ###

import itertools

(N, M) = map(int, raw_input().split())
cakes = [map(int, raw_input().split()) for i in xrange(N)]
C = itertools.combinations(cakes, M)

i = 0
value = 0
for cake_set in C:
  x = 0
  y = 0
  z = 0
  for j in xrange(M):
    x += cake_set[j][0]
    y += cake_set[j][1]
    z += cake_set[j][2]
  v = abs(x) + abs(y) + abs(z)
  if i == 0 or value < v:
    value = v
  i += 1
  
print value

### FIXED CODE ###

import numpy as np

(N, M) = map(int, raw_input().split())
cakes = [map(int, raw_input().split()) for i in xrange(N)]
cakes_p = np.array(sorted(cakes, key=lambda x: sum(x))[::-1])
cakes_nx = np.array(sorted(cakes, key=lambda x: sum(x) - 2 * x[0])[::-1])
cakes_ny = np.array(sorted(cakes, key=lambda x: sum(x) - 2 * x[1])[::-1])
cakes_nz = np.array(sorted(cakes, key=lambda x: sum(x) - 2 * x[2])[::-1])
cakes_list = [cakes_p, cakes_nx, cakes_ny, cakes_nz, cakes_p[::-1], cakes_nx[::-1], cakes_ny[::-1], cakes_nz[::-1]]
value = max([sum(map(abs,sum(cake[:M]))) for cake in cakes_list]) if M != 0 else 0

print value
### BUGGY CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 998244353
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

def main():
    N, M, K = map(int, input().split())

    fact = [1]
    for i in range(1, N+3):
        fact.append(fact[-1] * i % MOD)
    def rev(x):
        return pow(x, MOD-2, MOD)
    def cmb(i, k):
        if(i < k): return 0
        return fact[i] * rev(fact[k]) * rev(fact[i-k]) % MOD

    def count(m, k):
        combo = cmb(N-1, k)
        col = m * pow(m-1, N-k-1, MOD)
        val = (combo*col)%MOD
        return val

    cnt = 0
    for k in range(0, K+1):
        addval = count(M, k)
        cnt += addval
        if MOD < cnt:
	        cnt %= MOD

    print(cnt)
if __name__=='__main__':
    main()


### FIXED CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 998244353
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

def main():
    N, M, K = map(int, input().split())

    fact = [1]
    for i in range(1, N+3):
        fact.append(fact[-1] * i % MOD)
    def rev(x):
        return pow(x, MOD-2, MOD)
    def cmb(i, k):
        if(i < k): return 0
        return fact[i] * rev(fact[k]) * rev(fact[i-k]) % MOD

    def count(m, k):
        combo = cmb(N-1, k)
        col = m * pow(m-1, N-k-1, MOD)
        val = (combo*col)%MOD
        return val

    cnt = 0
    for k in range(0, K+1):
        addval = count(M, k)
        cnt += addval
        cnt %= MOD

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

# ひとまず毎回ソートするバージョン
# Python 3, pypy ともにTLE
import bisect

n, m = list(map(int, input().split() ))
values = list(map(int, input().split() ))
values.sort()

for i in range(m):
	max_card, num = list(map(int, input().split() ))

	num_small = bisect.bisect(values, num)
	num_to_change = min(max_card, num_small)

	# sort
	# values = values[num_to_change:num_small] + [num]*num_to_change + values[num_small:]
	del  values[:num_to_change]
	values[num_small - num_to_change : num_small - num_to_change] = [num]*num_to_change

print (sum(values))

### FIXED CODE ###

from operator import itemgetter
n, m = list(map(int, input().split() ))
values = list(map(int, input().split() ))
values.sort()

card_change = [list(map(int, input().split() )) for _ in range(m)]
card_change.sort(key = itemgetter(1))
# 変更後の数をkeyとしてソート

# X枚書き換えるとして、Xを全探索する方針で書いてみる
now = sum(values)
ans = sum(values)
idx = m - 1
for x in range(n):
	now -= values[x]

	card_change[idx][0] -= 1 # 変更可能枚数
	now += card_change[idx][1] # 変更後の値

	if now > ans:
		ans = now

	if card_change[idx][0] == 0:
		idx -= 1
		if idx < 0:
			break

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

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

ans = 1
for i in num:
  ans *= i
  if ans > 1000000000000000000:
    ans = -1
  
if ans > 1000000000000000000:
  ans = -1
print(ans)

### FIXED CODE ###

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

num.sort()

ans = 1
for i in num:
  ans *= i
  if ans > 1000000000000000000:
    print(-1)
    exit()
  
if ans > 1000000000000000000:
  ans = -1
print(ans)