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

N,M = map(int,input().split())
li = []
for m in range(M):
  li.append(input().split())

ac = 0
wa = 0

for n in range(N + 1):
  if n == 0:
    continue

  for index, i in enumerate(li):
    if int(i[0]) == n and i[1] == 'AC':
      ac += 1
      for indexs, x in enumerate(li):
        if indexs >= index:
          break
        if int(x[0]) == n and x[1] == 'WA':
          wa += 1
      break

print('{0} {1}'.format(ac, wa))

### FIXED CODE ###

from collections import defaultdict
d = defaultdict(int)

N,M = map(int,input().split())
li = []
for m in range(M):
  x,y = input().split()
  li.append([int(x), y])

sets = set()

ac = 0
wa = 0

for i in li:
  if i[1] == 'AC':
    if i[0] not in sets:
      sets.add(i[0])
      ac += 1
      wa += d[i[0]]

  else:
    if i[0] not in sets:
      d[i[0]] += 1

print('{} {}'.format(ac, wa))
### BUGGY CODE ###

N,M,Q=map(int,input().split())
Town=[[int(i) for i in input().split()] for i in range(M)]
Town.sort(key=lambda x:x[0])

def BS_left(x,L,s):
  L_copy=L[:]
  left=0
  if L[s-1]<x:
    return s-1
  else:
    while s>2:
      if L_copy[s//2]<x:
        L_copy=L_copy[s//2:s]
        left+=s//2
        s=s-s//2
      else:
        L_copy=L_copy[0:s//2+1]
        s=s//2+1
    if L[left]>=x:
      return left-1
    else:
      return left

def BS_right(x,L,s):
  L_copy=L[:]
  right=s-1
  if L[0]>x:
    return 0
  else:
    while s>2:
      if L_copy[s//2]<=x:
        L_copy=L_copy[s//2:s]
        s=s-s//2
      else:
        L_copy=L_copy[0:s//2+1]
        right+=-s//2+1
        s=s//2+1
    if L[right]<=x:
      return right+1
    else:
      return right

ans=[0]*Q
for i in range(Q):
  p,q=map(int,input().split())
  TownL=list(zip(*Town))[0]
  a=BS_left(p,TownL,M)+1
  b=BS_right(q,TownL,M)
  newTown=Town[a:b]
  if b-a==0:
    print(0)
  else:
    newTown.sort(key=lambda x:x[1])
    TownR=list(zip(*newTown))[1]
    c=BS_right(q,TownR,b-a)
    if c==1 and TownR[0]>q:
      print(0)
    else:
      print(c)


### FIXED CODE ###

N,M,Q=map(int,input().split())
Train=[[int(i) for i in input().split()] for i in range(M)]
Map=[[0]*(N+1) for i in range(N+1)]
for i in Train:
  x,y=i[0],i[1]
  Map[y][x]+=1
for a in range(1,N+1):
  for b in range(1,N+1):
    if b<=N-1:
      Map[a][b+1]=Map[a][b]+Map[a][b+1]
    if a>=2:
      Map[a][b]=Map[a-1][b]+Map[a][b]
for i in range(Q):
  p,q=map(int,input().split())
  print(Map[q][q]-Map[q][p-1]-Map[p-1][q]+Map[p-1][p-1])
### BUGGY CODE ###

# 部下の人数を返す
def get_subordinates(my_number):
    counter = 0
    for i, employee in enumerate(params1):
        if employee == my_number:
            counter += 1
    return counter

param_n = int(input())
params1 = list(map(lambda x: int(x), input().split(' ')))

for i in range(param_n):
    print(get_subordinates(i + 1))

### FIXED CODE ###

param_n = int(input())
params1 = list(map(lambda x: int(x), input().split(' ')))

result = [0 for i in range(param_n)]

for employee in params1:
    result[employee - 1] += 1

for num in result:
    print(num)
### BUGGY CODE ###

def L(i):
  if i == 0:
    return 2
  if i == 1:
    return 1
  return L(i - 1) + L(i - 2)

print(L(int(input())))

### FIXED CODE ###

n = int(input())

if n == 1:
  print(1)
else:
  a, b = 2, 1
  for i in range(n - 1):
    a, b = b, a + b
  print(b)
### BUGGY CODE ###

import sys

def main():
    N,*S = map(int, open(0).read().split())
    S = sorted(S)

    g = [S.pop(-1)]

    for _ in range(N):
        lg = len(g)
        for p in g[:lg]:
            for i in range(len(S)-1,-1,-1):
                s = S[i]
                if p > s:
                    g.append(s)
                    del S[i]
                    break
            else:
                print('No')
                sys.exit()
        g.sort(reverse=True)
    print('Yes')

if __name__=='__main__':
    main()

### FIXED CODE ###

## 他の方と処理内容がほぼ同じなのに何でTLEになるか分からないので、他の方のコードでテスト
N = int(input())
a = list(map(int,input().split(' ')))
a.sort()
    

fathers = [a.pop()]
for _ in range(N):
    sons = list()
    b = list()
    
    for father in fathers:
        while a:
            x = a.pop()
            if father > x:
                sons.append(x)
                break
            else:
                b.append(x)
                
    a = a + b[::-1]
    fathers.extend(sons)
    fathers.sort(reverse = True)
    
    
    
if len(fathers) == 2**N:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n,m = map(int,input().split())
h = [0] + list(map(int,input().split()))
a,b = [], []
for i in range(m):
    road = list(map(int,input().split()))
    a.append(road[0])
    b.append(road[1])

ans = 0

for i in range(1,n+1):
    max_hight = 0
    j = 0
    while i in a[j:]:
        index = j + a[j:].index(i)
        hight = h[b[index]]
        max_hight = max(max_hight, hight)
        j = index + 1
    j = 0
    while i in b[j:]:
        index = j + b[j:].index(i)
        hight = h[a[index]]
        max_hight = max(max_hight, hight)
        j = index + 1
    if h[i] > max_hight:
        ans += 1

print(ans)
    

### FIXED CODE ###

n,m = map(int,input().split())
h = [None] + list(map(int,input().split()))
road = [[] for _ in range(n+1)]
count = 0
for _ in range(m):
    a,b = map(int,input().split())
    road[a].append(b)
    road[b].append(a)
for i in range(1,n+1):
    max_hight = 0
    for j in road[i]:
        max_hight = max(max_hight, h[j])
    if h[i]>max_hight:
        count += 1

print(count)
### BUGGY CODE ###

# DP
def main():
    from builtins import max

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

    dp = [-1] * (W + 1)
    dp[0] = 0
    max_w = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(min(max_w, W - w), -1, -1):
            dpj = dp[j]
            if dpj != -1:
                jw = j + w
                if dpj + v > dp[jw]:
                    dp[jw] = dpj + v
                if jw > max_w:
                    max_w = jw
    print(max(dp))


main()


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

import re
pattern = r"AC"
N, Q = map(int, input().split(" "))
T = input()

for i in range(Q):
    start, end = map(int, input().split(" "))
    print(len(re.findall(pattern, T[start-1:end])))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
acList = [0 for n in range(N+1)]
for i in range(N):
    if("AC" == S[i:i+2]):
        acList[i+1] += acList[i] + 1
    else:
        acList[i+1] += acList[i]
for q in range(Q):
    left, right = map(int, input().split())
    print (acList[right-1] - acList[left-1])
### BUGGY CODE ###

import heapq

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]



checking=[(0,s)]

while checking:

    cost,checktown=heapq.heappop(checking)
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>cost+i[1]:
            YEN[i[0]]=cost+i[1]
            heapq.heappush(checking,(cost+i[1],i[0]))

checking=[(0,t)]

while checking:

    cost,checktown=heapq.heappop(checking)
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>cost+i[2]:
            SNOOK[i[0]]=cost+i[2]
            heapq.heappush(checking,(cost+i[2],i[0]))



MONEY=[None]*(n+1)

for i in range(1,n+1):
    MONEY[i]=YEN[i]+SNOOK[i]


for i in range(1,n+1):
    print(10**15-min(MONEY[i:]))


### FIXED CODE ###

import heapq

n,m,s,t=map(int,input().split())
TRAIN=[None]*m

for i in range(m):
    TRAIN[i]=list(map(int,input().split()))


YEN=[10**16]*(n+1)#sから国iまで行くときの最小円
SNOOK=[10**16]*(n+1)#国iからtまで行くときの最小スヌーク
YEN[s]=0
SNOOK[t]=0


TRAINMAP=[[] for i in range(n+1)]

for i in range(m):
    TRAINMAP[TRAIN[i][0]]+=[(TRAIN[i][1],TRAIN[i][2],TRAIN[i][3])]
    TRAINMAP[TRAIN[i][1]]+=[(TRAIN[i][0],TRAIN[i][2],TRAIN[i][3])]



checking=[(0,s)]

while checking:

    cost,checktown=heapq.heappop(checking)
    
    for i in TRAINMAP[checktown]:
        if YEN[i[0]]>cost+i[1]:
            YEN[i[0]]=cost+i[1]
            heapq.heappush(checking,(cost+i[1],i[0]))

checking=[(0,t)]

while checking:

    cost,checktown=heapq.heappop(checking)
   
    for i in TRAINMAP[checktown]:
        if SNOOK[i[0]]>cost+i[2]:
            SNOOK[i[0]]=cost+i[2]
            heapq.heappush(checking,(cost+i[2],i[0]))



MONEY=[10**16]*(n+1)
MONEY[n]=YEN[n]+SNOOK[n]

for i in range(n-1,0,-1):
    if YEN[i]+SNOOK[i]<MONEY[i+1]:
        MONEY[i]=YEN[i]+SNOOK[i]
    else:
        MONEY[i]=MONEY[i+1]


for i in range(1,n+1):
    print(10**15-MONEY[i])
### BUGGY CODE ###

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

num_r, num_g, num_b = S.count('R'), S.count('G'), S.count('B')
max_ans = num_r * num_g * num_b
count_not_ans = 0
S = list(S)

for i in range(N-2):
    for j in range(i+1, N-1):
        k = 2 * j - i
        if (0 <= k <= N-1) and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            count_not_ans += 1

print(max_ans - count_not_ans)


### FIXED CODE ###

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

num_r, num_g = S.count('R'), S.count('G')
num_b = N - num_r - num_g
max_ans = num_r * num_g * num_b
count_not_ans = 0
S = list(S)

for i in range(N):
    for j in range(i+1, N):
        k = 2 * j - i
        if (0 <= k <= N-1) and len(set([S[i], S[j], S[k]])) == 3:
            count_not_ans += 1

print(max_ans - count_not_ans)
### BUGGY CODE ###

def main():
    from bisect import bisect_left as bl
    from bisect import bisect_right as br

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

    inf = 10**18+1

    ok = -inf
    ng = inf
    start_0 = bl(a, 0)
    start_1 = bl(a, 1)

    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        cnt = 0
        for i in a[:start_0]:
            if mid % i == 0:
                cnt += n - br(a, mid//i)
            else:
                cnt += n - br(a, mid//i + 0.5)
        for i in a[start_1:]:
            if mid % i == 0:
                cnt += bl(a, mid//i)
            else:
                cnt += bl(a, mid//i + 0.5)
        if mid > 0:
            cnt += n * (start_1 - start_0)
        cnt -= len([None for i in a if i*i < mid])
        if cnt//2 < k:
            ok = mid
        else:
            ng = mid
    print(ok)


main()

### FIXED CODE ###

def main():
    from bisect import bisect_left as bl

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

    inf = 10**18+1

    ok = -inf
    ng = inf
    start_0 = bl(a, 0)
    start_1 = bl(a, 1)

    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        cnt = 0
        if mid >= 0:
            now = 0
            if start_0 > 0:
                for i in a[start_0-1::-1]:
                    while now < n:
                        if i*a[now] >= mid:
                            now += 1
                        else:
                            break
                    cnt += n - now
            now = n
            for i in a[start_1:]:
                while now > 0:
                    if i*a[now-1] >= mid:
                        now -= 1
                    else:
                        break
                cnt += now
        else:
            now = 0
            for i in a[:start_0]:
                while now < n:
                    if i*a[now] >= mid:
                        now += 1
                    else:
                        break
                cnt += n - now
            now = n
            for i in a[n-1:start_1-1:-1]:
                while now > 0:
                    if i*a[now-1] >= mid:
                        now -= 1
                    else:
                        break
                cnt += now
        if mid > 0:
            cnt += n * (start_1 - start_0)
        cnt -= len([None for i in a if i*i < mid])
        if cnt//2 < k:
            ok = mid
        else:
            ng = mid
    print(ok)


main()
### BUGGY CODE ###

# https://atcoder.jp/contests/abc112/tasks/abc112_d

n, m = map(int, input().split())
ans = 1
i = 1
while i <= (m / n):
    if m % i == 0 and m // i >= n:
        ans = max(ans, i)
    i += 1
print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc112/tasks/abc112_d

n, m = map(int, input().split())
if n == 1:
    ans = m
else:
    ans = 1
    i = 1
    limit = m / n
    while i <= limit:
        if m % i == 0 and m // i >= n:
            ans = max(ans, i)
        i += 1
print(ans)
### BUGGY CODE ###

from itertools import combinations

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

com = list(combinations(p,k))
ans = list(map(sum,com))
print(min(ans))

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
p.sort()
ans = 0

for i in range(k):
    ans += p[i]
    i += 1

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

L = input()
N = len(L)
MOD = 10 ** 9 + 7
bits = [1, 2]
acc = [1, 3]
for _ in range(N):
    nex = bits[-1] * 3 % MOD
    bits.append(nex)
    acc.append((acc[-1] + nex) % MOD)
ans = acc[N-1]
cnt = 1
for i, b in enumerate(L):
    if i == 0:
        continue
    now = N-i-1
    if b == '1':
        ans += acc[now] * pow(2, cnt) % MOD
        cnt += 1
    ans %= MOD
ans += pow(2, cnt)
ans %= MOD
print(ans)


### FIXED CODE ###

import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
L = input()
N = len(L)
MOD = 10 ** 9 + 7
bits = [1, 2]
acc = [1, 3]
for _ in range(N):
    nex = bits[-1] * 3 % MOD
    bits.append(nex)
    acc.append((acc[-1] + nex) % MOD)
ans = acc[N-1]
cnt = 1
for i, b in enumerate(L):
    if i == 0:
        continue
    now = N-i-1
    if b == '1':
        ans += acc[now] * pow(2, cnt, MOD) % MOD
        cnt += 1
    ans %= MOD
ans += pow(2, cnt, MOD)
ans %= MOD
print(ans)
### BUGGY CODE ###

d,a=[],0
for i in range(0,int(input())):
  d.append("".join(sorted(input().rstrip('\n'))))
for i in list(set(d)):
  n=d.count(i)
  a+=(n-1)*n
print(int(a/2))

### FIXED CODE ###

from collections import *
print(int(sum(([(i-1)*i/2 for i in Counter(["".join(sorted(input()))for i in range(int(input()))]).values()]))))
### BUGGY CODE ###

S = input()
#dp[i][four] =: i + 1番目まで見たとき,照合したケツがfourとなるものの総数
dp = [[0 for _ in range(4)] for _ in range(len(S)+1 )]
dp[0][0] = 1
mod = 10**9 + 7
for i in range(len(S)):
    if S[i] == '?':
        dp[i+1][1] += dp[i][0] 
        dp[i+1][1] %= mod
        dp[i+1][2] += dp[i][1] 
        dp[i+1][2] %= mod
        dp[i+1][3] += dp[i][2] 
        dp[i+1][3] %= mod
    if S[i] == 'A':
        dp[i+1][1] += dp[i][0] 
        dp[i+1][1] %= mod
    if S[i] == 'B':
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] %= mod
    if S[i] == 'C':
        dp[i+1][3] += dp[i][2]
        dp[i+1][3] %= mod
    for f in range(4):
        if S[i] != '?':
            dp[i+1][f] += dp[i][f]
        else:
            dp[i+1][f] += dp[i][f] * 3
print(dp[len(S)][3]%mod)


### FIXED CODE ###

S = input()
#dp[i][four] =: i + 1番目まで見たとき,照合したケツがfourとなるものの総数
dp = [[0 for _ in range(4)] for _ in range(len(S)+1 )]
dp[0][0] = 1
mod = 10**9 + 7
for i in range(len(S)):
    if S[i] == '?':
        dp[i+1][1] += dp[i][0] 
        dp[i+1][1] %= mod
        dp[i+1][2] += dp[i][1] 
        dp[i+1][2] %= mod
        dp[i+1][3] += dp[i][2] 
        dp[i+1][3] %= mod
    if S[i] == 'A':
        dp[i+1][1] += dp[i][0] 
        dp[i+1][1] %= mod
    if S[i] == 'B':
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] %= mod
    if S[i] == 'C':
        dp[i+1][3] += dp[i][2]
        dp[i+1][3] %= mod
    for f in range(4):
        if S[i] != '?':
            dp[i+1][f] += dp[i][f]
        else:
            dp[i+1][f] += dp[i][f] * 3
        dp[i+1][f] %= mod
print(dp[len(S)][3]%mod)
### BUGGY CODE ###

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

def main():
  r, g, b, n = input_list()
  ans = 0
  for x in range(n//r+1):
    for y in range(n//g+1):
      rr = r*x
      gg = g*y
      if rr + gg > n:
        continue
      bb = (n - rr - gg)
      if bb % b != 0:
        continue
      ans += 1
  print(ans)

main()

### FIXED CODE ###

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

def main():
  r, g, b, n = input_list()
  ans = 0
  for x in range(n//r+1):
    for y in range(n//g+1):
      rr = r*x
      gg = g*y
      if rr + gg > n:
        continue
      bb = (n - rr - gg)
      if bb % b != 0:
        continue
      ans += 1
  print(ans)

main()
### BUGGY CODE ###

n,k,q = map(int,input().split())
a = [int(input()) for _ in range(q)]

for i in range(n):
    if a.count(i+1) > q-k:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k,q = map(int,input().split())
p_lis = [k-q] * n

for i in range(q):
    x = int(input())
    p_lis[x-1] += 1
for j in p_lis:
    if j > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for x in range(Q):
    a, b = map(int, input().split())
    s = S[a-1:b]

    a = ''
    ret = 0
    for b in s:
        if a == 'A' and b == 'C':
            ret += 1
        a = b
    print(ret)

### FIXED CODE ###

from itertools import accumulate

N, Q = map(int, input().split())
S = input()
lst = [0]
idx = 0
for x in range(len(S) - 1):
    if S[x] == 'A' and S[x + 1] == 'C':
        lst.append(1)
    else:
        lst.append(0)

lst2 = list(accumulate(lst))
for x in range(Q):
    a, b = map(int, input().split())
    print(lst2[b-1] - lst2[a-1])
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, Counter, deque
    from copy import copy

    n = int(readline())

    edge = defaultdict(list)
    count = Counter()

    for x in range(1, n + 1):
        a = list(map(int, readline().split()))
        for j in range(n - 2):
            y = a[j]
            z = a[j + 1]
            uf, us = min(x, y), max(x, y)
            vf, vs = min(x, z), max(x, z)
            edge[(uf, us)].append((vf, vs))
            count[(uf, us)] += 0
            count[(vf, vs)] += 1

    ans = 0
    rem = n * (n - 1) // 2
    que = deque()
    for key, val in count.items():
        if val == 0:
            que.append(key)
    que_tomorrow = deque()

    while rem:
        ans += 1
        if not que:
            print(-1)
            return
        while que:
            cur_match = que.popleft()
            for nx_match in edge[cur_match]:
                count[nx_match] -= 1
                if count[nx_match] == 0:
                    que_tomorrow.append(nx_match)
            rem -= 1
        que = copy(que_tomorrow)
        que_tomorrow.clear()

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def calc_id(x, y):
        return min(x, y) * 10007 + max(x, y)

    from collections import defaultdict, Counter, deque
    from copy import copy

    n = int(readline())

    edge = defaultdict(list)
    count = Counter()

    for x in range(1, n + 1):
        a = list(map(int, readline().split()))
        count[calc_id(x, a[0])] += 0
        for j in range(n - 2):
            y = a[j]
            z = a[j + 1]
            u_id = calc_id(x, y)
            v_id = calc_id(x, z)
            edge[u_id].append(v_id)
            count[v_id] += 1

    ans = 0
    rem = n * (n - 1) // 2
    que = deque()
    for key, val in count.items():
        if val == 0:
            que.append(key)
    que_tomorrow = deque()

    while rem:
        ans += 1
        if not que:
            print(-1)
            return
        while que:
            cur_match = que.popleft()
            for nx_match in edge[cur_match]:
                count[nx_match] -= 1
                if count[nx_match] == 0:
                    que_tomorrow.append(nx_match)
            rem -= 1
        que = copy(que_tomorrow)
        que_tomorrow.clear()

    print(ans)


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

h,n=map(int,input().split())
M=[]
maxA=0
for i in range(n):
    a,b=map(int,input().split())
    M.append([a,b])
    maxA=max(maxA,a)

dp=[-1]*(h+maxA+5)
dp[0]=0
for i in range(1,h+maxA+5):
    for m in range(n):
        hp=M[m][0]
        mp=M[m][1]
        if i>=hp and dp[i-hp]!=-1: #体力より多い かつ 前の参照が存在しているとき
            if dp[i]==-1: #まだ更新されてないとき
                dp[i]=dp[i-hp]+mp
            else: #既に値があるとき
                dp[i]=(min(dp[i],dp[i-hp]+mp))

chk=h
while dp[chk]==-1:
    chk+=1
ans=dp[chk]
for i in range(chk+1,h+maxA+5):
    if dp[i]!=-1:
        ans=min(ans,dp[i])
print(ans)

### FIXED CODE ###

h,n=map(int,input().split())
M=[]
maxA=0
for i in range(n):
    a,b=map(int,input().split())
    M.append([a,b])
    maxA=max(maxA,a)

dp=[-1]*(h+maxA+5)
dp[0]=0
for i in range(1,h+maxA+5):
    for m in range(n):
        hp=M[m][0]
        mp=M[m][1]
        if i>=hp and dp[i-hp]!=-1: #体力より多い かつ 前の参照が存在しているとき
            if dp[i]==-1: #まだ更新されてないとき
                dp[i]=dp[i-hp]+mp
            else: #既に値があるとき
                dp[i]=(min(dp[i],dp[i-hp]+mp))

chk=h
while dp[chk]==-1:
    chk+=1
ans=dp[chk]
for i in range(chk+1,h+maxA+5):
    if dp[i]!=-1:
        ans=min(ans,dp[i])
print(ans)
### BUGGY CODE ###

from sys import stdin
n, m = map(int, input().split())
card = sorted(list(map(int, input().split())))

for i in range(m):
    b, c = map(int, stdin.readline().split())
    card = sorted(list(map(lambda x:max(x,c), card[:b])) + card[b:])
print(sum(card))

### FIXED CODE ###

from heapq import heappop, heappush

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

ans = []
for b, c in sorted([list(map(int, input().split()))for i in range(m)], key=lambda x:-x[1]):
        for i in range(b):
                if len(a)==0: break
                ans.append(max(c,  heappop(a)))
while len(a): ans.append(heappop(a))
print(sum(ans))
### BUGGY CODE ###

from collections import deque

N = int(input())
A = [int(input()) for _ in range(N)]

l = deque()

for a in A:
    if len(l) == 0:
        l.append(a)
    else:
        tmp_deque = deque()
        while len(l) > 0:
            num = l.popleft()
            if num >= a:
                tmp_deque.append(num)
            else:
                break
        tmp_deque.append(a)
        l.extendleft(tmp_deque)
        

print(len(l))


### FIXED CODE ###

from collections import deque

def replace(l, a, max_idx, min_idx):
    if max_idx == min_idx:
        l[max_idx] = a
        return

    center = (max_idx + min_idx)//2
    if l[center] >= a:
        return replace(l, a, max_idx, center+1)
    else:
        return replace(l, a, center, min_idx)


N = int(input())
A = [int(input()) for _ in range(N)]


l = []

for a in A:
    if len(l) == 0:
        l.append(a)
    elif l[-1] >= a:
        l.append(a)
    else:
        replace(l, a, len(l)-1, 0)

print(len(l))
### BUGGY CODE ###

S=input()
q=int(input())
RV=0
for i in range(q):
    IN=input()
    if IN=="1":
        RV+=1
    else:
        t,f,c=IN.split()
        if RV%2==0:
            if f=="1":
                S=c+S                
            else:
                S=S+c
        else:
            if f=="1":
                S=S+c
            else:
                S=c+S
if RV%2==0:
    print(S)
else:
    S=S[::-1]
    print(S)

### FIXED CODE ###

S=input()
q=int(input())
RV=0
A="A"
for i in range(q):
    IN=input()
    if IN=="1":
        RV+=1
    else:
        t,f,c=IN.split()
        if RV%2==0:
            if f=="1":
                A=c+A               
            else:
                A=A+c
        else:
            if f=="1":
                A=A+c
            else:
                A=c+A
if RV%2==0:
    for i in range(len(A)):
        if A[i]=="A":
            print(A[:i]+S+A[i+1:])
else:
    A=A[::-1]
    for i in range(len(A)):
        if A[i]=="A":
            print(A[:i]+S[::-1]+A[i+1:])