Harryxun/stf_run huggingface dataset:
n,t=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(n)]

dp=[[0]*(t) for i in range(n)]
x=[[0]*(t) for j in range(n)]
s.sort()


p=s[-1]
del(s[-1])


for i in range(n-1):
    for j in range(t):

        if j-s[i][0]>=0:
            dp[i+1][j]=max(dp[i][j],dp[i][j-s[i][0]]+s[i][1])
            if dp[i+1][j]>dp[i][j]:
                x[i+1][j]=str(x[i][j-s[i][0]])+str(i)
            else:
                x[i+1][j]=x[i][j]

        else:
            dp[i+1][j]=dp[i][j]
            x[i+1][j]=x[i][j]
count=0

v=[]
for i in x[n-1][-1]:
    count+=1
    if count==1:
        continue
    v.append(int(i))


ans=p[1]
for i in range(n-1):
    if v.count(i)==1:
        continue

    ans=max(ans,s[i][1])



print(dp[n-1][-1]+ans)



### FIXED CODE ###

n,t=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(n)]

dp=[[0]*(t) for i in range(n+1)]
s.sort()


for i in range(n):
    for j in range(t):
        if j-s[i][0]>=0:
            dp[i+1][j]=max(dp[i][j],dp[i][j-s[i][0]]+s[i][1])

        else:
            dp[i+1][j]=dp[i][j]

ans=0
for i in range(n):
    ans=max(ans,dp[i][t-1]+s[i][1])

print(ans)
import numpy as np

N = input()
print N**3

### FIXED CODE ###

N = input()

print(N**3)
n = int(input())
a = list(map(int, input().split()))

nn = n + max(a)
ml = [0] * nn
pl = [0] * nn

out = 0

for i in range(0, n):
    pl[i+a[i]] += 1
    if(i-a[i]>=0):
        ml[i-a[i]] += 1

for i in range(0, n):
    out += pl[i] * ml[i]

print(out)


### FIXED CODE ###

instr = input()

if instr == 'ABC':
    print('ARC')
else:
    print('ABC')
X, Y, A, B, C = map(int, input().split())
P = sorted(list(map(int, input().split())), reverse=True)
Q = sorted(list(map(int, input().split())), reverse=True)
R = sorted(list(map(int, input().split())), reverse=True)

red = sorted(P[:X])
gre = sorted(Q[:Y])
ans = sum(red) + sum(gre) 
j, k = 0, 0

for i in range(min(X+Y),C):
    if(red[j] <= gre[k]):
        if R[i] > red[j] :
            ans = ans - red[j] + R[i]
            j += 1
        else:
            break
    else:
        if R[i] > gre[k] :
            ans = ans - gre[k] + R[i]
            k += 1
        else:
            break
print(ans)

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
P = sorted(list(map(int, input().split())), reverse=True)
Q = sorted(list(map(int, input().split())), reverse=True)
R = sorted(list(map(int, input().split())), reverse=True)

red = sorted(P[:X])
gre = sorted(Q[:Y])
m = min((X+Y),C)
n = R[:m]
red.extend(gre)
red.extend(n)
red = sorted(red, reverse=True)

print(sum(red[:X+Y]))
N, K = map(int, input().split(" "))
towns = list(map(lambda x: int(x)-1, input().split(" ")))
assert len(towns) == N

# print(towns)

# score = {0: 0}
# current = 0
# move = 0
# while 1:
#   next_town = towns[current]
#   move += 1
#   # print(f"move {current} to {next_town}")
#   if score.get(next_town) is not None:
#     # print(f"find loop!")
#     loop_move = move - score.get(next_town)
#     loop_town = next_town
#     until_loop = score.get(next_town)
#     # print(f"loop start town : ", loop_town)
#     # print(f"cost to start to loop town : ", until_loop)
#     # print(f"loop length : ", loop_move)
#     break
#   score[next_town] = move
#   current = next_town

# if K < until_loop:
#   result = 0
#   for k in range(K):
#     result = towns[result]
# else:
#   result = loop_town
#   for k in range((K - until_loop) % loop_move):
#     result = towns[result]
# print(result + 1)

visited = set([])
current = 0
while 1:
  if K == 0:
    break
  current = towns[current]
  K -= 1
  if current in visited:
    L = 0
    tcurrent = current
    while 1:
      tcurrent = towns[tcurrent]
      L += 1
      if tcurrent == current:
        break
    break
  visited.add(current)

K = K % L
print(K)
for _ in range(K):
  current = towns[current]
print(current + 1)


### FIXED CODE ###

N, K = map(int, input().split(" "))
towns = list(map(lambda x: int(x)-1, input().split(" ")))
assert len(towns) == N

# print(towns)

score = {0: 0}
current = 0
move = 0
while 1:
  next_town = towns[current]
  move += 1
  # print(f"move {current} to {next_town}")
  if score.get(next_town) is not None:
    # print(f"find loop!")
    loop_move = move - score.get(next_town)
    loop_town = next_town
    until_loop = score.get(next_town)
    # print(f"loop start town : ", loop_town)
    # print(f"cost to start to loop town : ", until_loop)
    # print(f"loop length : ", loop_move)
    break
  score[next_town] = move
  current = next_town

if K < until_loop:
  result = 0
  for k in range(K):
    result = towns[result]
else:
  result = loop_town
  for k in range((K - until_loop) % loop_move):
    result = towns[result]
print(result + 1)
import math
a,b,c,d,e,f = map(int,input().split())
water_nodo = 100 /(100 + e)
water_max = f*water_nodo
a_max = math.ceil(water_max / (100*a))
b_max = math.ceil(water_max / (100*b))
water_gaps = []
for i in range(a_max):
  for j in range(b_max):
    water_gap = water_max - 100*a*i - 100*b*j
    if water_gap >= 0:
      water_gaps.append(water_gap)
sorted_water = sorted(water_gaps)
max_water = water_max - sorted_water[0]
sugar_max = max_water*e/100
c_max = math.ceil(sugar_max / c)
d_max = math.ceil(sugar_max / d)
sugar_gaps = []
for k in range(c_max):
  for l in range(d_max):
    sugar_gap = sugar_max - c*k - d*l
    if sugar_gap >= 0:
      sugar_gaps.append(sugar_gap)
sorted_sugar = sorted(sugar_gaps)
max_sugar = sugar_max - sorted_sugar[0]
print(str(int(max_water + max_sugar)) + " " + str(int(max_sugar)))

### FIXED CODE ###

import math
a,b,c,d,e,f = map(int,input().split())
max_nodo = e/(e+100)
answer = {}
for i in range(31):
  for j in range(31):
    water = 100*a*i + 100*b*j
    max_sugar = water*e/100
    sugar_range = int(math.ceil(max_sugar/c))
    if water >= f:
      break
    for k in range(sugar_range):
      for l in range(sugar_range):
        sugar = c*k + d*l
        total = water + sugar
        nodo = sugar / total
        if total > f:
          break
        if sugar > max_sugar:
          break
        answer[nodo] = [total,sugar]
ans = max(answer.items(),key = lambda x:x[0])[1]

#print(answer)
print(str(ans[0]) + " " + str(ans[1]))
a = list(map(int, input().split()))
if a[0] == 1:
  a[0] = 1
  return a[1]
else: 
  return a[0]*(a[0] - 1)
if a[1] == 1:
  a[1] = 1
  return a[1] 
else: 
  return a[1]*(a[1] - 1)
print(a[0]*a[1])

### FIXED CODE ###

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


def a1():
    if a[0] == 1 or a[0] == 0:
        a[0] = 0
        return a[0]
    else:
        return a[0] * (a[0] - 1) / 2


def b1():
    if a[1] == 1 or a[1] == 0:
        a[1] = 0
        return a[1]
    else:
        return a[1] * (a[1] - 1) / 2


print(int(a1() + b1()))
# -*- coding: utf-8 -*-

word = list(map(str, input()))

while True:
    ad_word = list(map(str, input()))
    if not ad_word:
        break
    else:
        word.append(ad_word)

while ' ' in word:
    word.remove(' ')

while '.' in word:
    word.remove('.')

char = {}
for i in range(ord('a'), ord('z') + 1):
    char[chr(i)] = 0

for j in range(len(word)):
    char[str(word[j]).lower()] += 1

for k in range(ord('a'), ord('z') + 1):
    print('{0} : {1}'.format(chr(k), char[chr(k)]))


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

word = sys.stdin.read().lower()
for i in range(ord('a'), ord('z') + 1):
    print('{0} : {1}'.format(chr(i), word.count(chr(i))))
import sys
input = sys.stdin.readlines()

N = int(input[0])
T_N = list(map(int, input[1].split()))
M = int(input[2])
P_M = [None] * M
P_X = [None] * M
for PX in input[3:]:
    P_M, X_M = map(int, PX.split())

sumT = sum(T_N)
for idx1 in range(M):
    print(sumT - T_N[P_M[idx1] - 1] + X_M[idx1])


### FIXED CODE ###

import sys
in1 = sys.stdin.readlines()

#in1 = ['5','7 2 3 8 5','3','4 2','1 7','4 13']

N = int(in1[0])
T_N = list(map(int, in1[1].split()))
M = int(in1[2])
P_M = [None] * M
X_M = [None] * M
idx1 = 0
for PX in in1[3:]:
    P_M[idx1], X_M[idx1] = map(int, PX.split())
    idx1 += 1

sumT = sum(T_N)
for idx1 in range(M):
    print(sumT - T_N[P_M[idx1] - 1] + X_M[idx1])
n = int(input())
data = input().split()
import math
sum = 0
for i in range(n):
    sum = sum + int(data[I])
average = sum / n
a = 0
for i in range(n):
    a = a + (int(data[i]) - average)**2
print('{}'.format(math.sqrt(a/n)))



### FIXED CODE ###

while True:
    n = int(input())
    if n == 0:
        break
    data = input().split()
    import math
    sum = 0
    for i in range(n):
        sum = sum + int(data[i])
    average = sum / n
    a = 0
    for i in range(n):
        a = a + (int(data[i]) - average)**2
    print('{}'.format(math.sqrt(a/n)))
n, k = map(int, input())
print(k * ((k - 1) ** (n - 1)))

### FIXED CODE ###

n, k = map(int, input().split())
print(k * ((k - 1) ** (n - 1)))
n, b, c = map(int, input().split(""))
ans = 0
for i in range(n + 1):
    if b <= sum(list(map(int, list(str(i))))) <= c:
        ans += i
print(ans)


### FIXED CODE ###

n, b, c = map(int, input().split())
ans = 0
for i in range(n + 1):
    if b <= sum(list(map(int, list(str(i))))) <= c:
        ans += i
print(ans)
x = input()

print(x*x)

### FIXED CODE ###

x = int(input())
print(x**2)
A,B,C = map(int,input().split())
if A + 2B <= C:
  print("Yes")
else:
  print("No")
  

### FIXED CODE ###

A,B,C = map(int,input().split())
if A + B >= C:
  print("Yes")
else:
  print("No")
from itertools import combinations
 
N, M, X = list(map(int,input().split()))
A = []
for i in range(N):
  A.append(list(map(int,input().split())))
sum = []
subsets=[]
for i in range(len(A) + 1):
    for c in combinations(A, i):
        subsets.append(list(c))
 
for i in subsets:
  tmp = [0]*(M+1)
  if len(i) == 1:
    sum.append(i[0])
  elif len(i) == 0:
    sum.append([0]*(M+1))
  else:
    for j in i:
      tmp = list(map(lambda a,b: a + b, tmp,j))
    sum.append(tmp)
    
min_price = 101010101010101010101010
 
for i in sum:
  t = 0
  for j in range(len(i)):
    if j==0:
      pass
    elif X > i[j]:
      t = 1
      break
  if t == 0
    min_price = min(min_price, i[0])
 
if min_price == 101010101010101010101010:
  print(-1)
else:
  print(min_price) 

### FIXED CODE ###

from itertools import combinations
 
N, M, X = list(map(int,input().split()))
A = []
for i in range(N):
  A.append(list(map(int,input().split())))
sum = []
subsets=[]
for i in range(len(A) + 1):
    for c in combinations(A, i):
        subsets.append(list(c))
 
for i in subsets:
  tmp = [0]*(M+1)
  if len(i) == 1:
    sum.append(i[0])
  elif len(i) == 0:
    sum.append([0]*(M+1))
  else:
    for j in i:
      tmp = list(map(lambda a,b: a + b, tmp,j))
    sum.append(tmp)
    
min_price = 10000000000
 
for i in sum:
  t = 0
  for j in range(len(i)):
    if j==0:
      pass
    elif X > i[j]:
      t = 1
      break
  if t == 0:
    min_price = min(min_price, i[0])
 
if min_price == 10000000000:
  print(-1)
else:
  print(min_price)
def createFacArr(n, mod):
    '''
    二項係数計算用の配列の作成

    Parameters
    n : int
        配列のサイズ
    mod : int
        あまり

    Returns
    fac : list
        階乗のリスト
    finv : list
        modの逆元のリスト
    ivn : list
    '''
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, n):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
    return fac, finv

def comb(n ,k, mod, fac, finv):
    '''
    二項係数の計算

    Parameters
    n : int
        元集合
    k : int
        元集合から選択する数
    mod : int
        あまり
    fac : list
        階乗のリスト
    finv : list
        逆元のリスト
    
    Returns
    c : int
        nCkの組み合わせの数
    '''
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod
MOD = 10 ** 9 + 7
fac, finv =  createFacArr(10**6+1000, MOD)

r1, c1, r2, c2 = map(int, input().split())

ans = 0
for r in range(r1,r2+1):
    ans += comb(r+c2+1,c2, MOD, fac, finv)-comb(r+c1, c1-1,MOD, fac, finv)
    ans %= MOD
print(ans)


### FIXED CODE ###

def createFacArr(n, mod):
    '''
    二項係数計算用の配列の作成

    Parameters
    n : int
        配列のサイズ
    mod : int
        あまり

    Returns
    fac : list
        階乗のリスト
    finv : list
        modの逆元のリスト
    ivn : list
    '''
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, n):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
    return fac, finv

def comb(n ,k, mod, fac, finv):
    '''
    二項係数の計算

    Parameters
    n : int
        元集合
    k : int
        元集合から選択する数
    mod : int
        あまり
    fac : list
        階乗のリスト
    finv : list
        逆元のリスト
    
    Returns
    c : int
        nCkの組み合わせの数
    '''
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod
MOD = 10 ** 9 + 7
fac, finv =  createFacArr(10**7, MOD)

r1, c1, r2, c2 = map(int, input().split())

ans = 0
for r in range(r1,r2+1):
    ans += comb(r+c2+1,c2, MOD, fac, finv)-comb(r+c1, c1-1,MOD, fac, finv)
    ans %= MOD
print(ans)
import math
denom = int(1e9+7)

def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p


def combi2(n,k,p,f,pow_fun):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=fact_mod[n]
  b=fact_mod[k]
  c=fact_mod[n-k]
  return (a*pow_fun[b]*pow_fun[c])%p


N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort(reverse = True)

fact_mod = [1]
current = 1
for i in range(1,N+1):
    current = (current * i) % denom
    fact_mod.append(current)

pow_fun = [0]*(denom+1)
for i in fact_mod:
    pow_fun[i]=power_func(i,denom-2,denom)

max_tot = 0
min_tot = 0
for i in range(N-K+1):
    max_tot += (A[i] * combi2(N-i-1, K-1, denom, fact_mod,pow_fun)) % denom
    min_tot += (A[N-i-1] * combi2(N-i-1, K-1, denom, fact_mod,pow_fun)) % denom
    
print((max_tot - min_tot)%denom)

### FIXED CODE ###

import math
denom = int(1e9+7)

def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p


def combi2(n,k,p,f,pow_fun):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=fact_mod[n]
  b=fact_mod[k]
  c=fact_mod[n-k]
  return (a*pow_fun[b]*pow_fun[c])%p


N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort(reverse = True)

fact_mod = [1]
current = 1
for i in range(1,N+1):
    current = (current * i) % denom
    fact_mod.append(current)

pow_fun = {}
for i in fact_mod:
    pow_fun[i]=power_func(i,denom-2,denom)

max_tot = 0
min_tot = 0
for i in range(N-K+1):
    max_tot += (A[i] * combi2(N-i-1, K-1, denom, fact_mod,pow_fun)) % denom
    min_tot += (A[N-i-1] * combi2(N-i-1, K-1, denom, fact_mod,pow_fun)) % denom
    
print((max_tot - min_tot)%denom)
N = int(input())
*H, = map(int, input().split())
dp  = [-1]*N

def dfs(n):#足場nまでにたどり着くための最小コスト
    
    if n==0:
        return 0
    if n-1==0:
        return abs(H[n]-H[n-1])
    if dp[n]!=-1:
        return dp[n]
    ans = min(abs(H[n]-H[n-1])+dfs(n-1), abs(H[n]-H[n-2])+dfs(n-2))
    dp[n] = ans
    return ans

print(dfs(N-1))

### FIXED CODE ###

N = int(input())
*h, = map(int, input().split())

dp = [0] * N

for i in range(1, N, 1):
        if i==1:
                dp[i]=abs(h[i]-h[i-1])
        else:
                dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))

print(dp[N-1])
x=input()
count=0
x_count=0
judge=[]
string=["k","e","y","e","n","c","e"]
for i in x:
    if(i==string[count] and count<=6):
        judge.append(i)
        count=count+1

for i in judge:        
    if(i==string[x_count]):
        o=True
        x_count=x_count+1
    else:
        x_count=x_count+1
        o=False
        break

if(o==True):
    print("YES")
else:
    print("NO")


### FIXED CODE ###

S = input()
KEYENCE = "keyence"
 
 
isKeyence = False
for i in range(len(S)):
    for j in range(i, len(S)):
        s = S[:i] + S[j:]
        if s == KEYENCE:
            isKeyence = True
if isKeyence:
    print("YES")
else:
    print("NO")
A = int(input())
print(180*(n-2))

### FIXED CODE ###

n = int(input())
print(180*(n-2))
n, k = map(int, input().split())
a = list(map(int, input().split()))

d = {}
for i in range(1, n + 1):
    d[i] = a[i - 1]

did = set()
route = [1]

now = 1
for i in range(k):
    now = d[now]
    route.append(now)
    if now in did:
        break
    did.add(now)

for i in range(len(route)):
    if route[i] == route[-1]:
        roop = route[i:-1]
        break

print(roop[(k - i) % len(roop)])

### FIXED CODE ###

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

d = {}
for i in range(1, n + 1):
    d[i] = a[i - 1]

did = set()
route = [1]

now = 1
for i in range(k):
    now = d[now]
    route.append(now)
    if now in did:
        break
    did.add(now)

if k < 10 ** 6:
    now = 1
    for i in range(k):
        now = d[now]

    print(now)

else:
    for i in range(len(route)):
        if route[i] == route[-1]:
            roop = route[i:-1]
            break

    print(roop[(k - i) % len(roop)])
A, B, K = map(int, input().split())
N = min(A, B)
list_gcd = [] 

for i in range(1, N):
  if A % i == 0 and B % i == 0:
    list_gcd.append(i)
    
if N == 1:
  Y = max(A,B)
  if Y == 1:
    list_gcd.append(1)
  else:
    for i in range(1, Y):
      if Y % i == 0:
        list_gcd.append(i)
    
print(list_gcd[K-1])

### FIXED CODE ###

A, B, K = map(int, input().split())
N = min(A, B)
list_gcd = [] 

for i in range(1, N+1):
  if A % i == 0 and B % i == 0:
    list_gcd.append(i)
    
if N == 1:
  Y = max(A,B)
  if Y == 1:
    list_gcd.append(1)
  else:
    for i in range(1, Y):
      if Y % i == 0:
        list_gcd.append(i)

print(list_gcd[-K])
O = list(input())
E = list(input())
s = ''
while O or E:
    if len(E) >= len(O):
        s = E.pop() + s
    else:
        s = O.pop() + s
print(s)


### FIXED CODE ###

a, b, c = map(int, input().split())
if b - a == c - b:
    print('YES')
else:
    print('NO')
x,a,b=map(int,input().split())
if b in range(a):
  print('delicious')
elif bin range(a,x+a+1):
  print('safe')
else:
  print('dangerous')

### FIXED CODE ###

x,a,b=map(int,input().split())
if b in range(a+1):
  print('delicious')
elif b in range(a,x+a+1):
  print('safe')
elif b>a+x:
  print('dangerous')
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys



def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


def main():
    n = I()


    def ok(last, c):
        last_plus = last + c
        if 'agc' in last_plus:
            return 0
        for i in range(len(last_plus)-1):
            tmp = list(last_plus)
            tmp[i], tmp[i+1] = tmp[i+1], tmp[i]
            if 'agc' in ''.join(tmp):
                return 0
        return 1



    D = [defaultdict(int) for _ in range(n+1)]
    D[0][''] = 1


    for i in range(n):
        for k, v in D[i].items():
            for c in 'acgt':
                if ok(k, c):
                    D[i+1][(k + c)[-3:]] += v
                    D[i + 1][(k + c)[-3:]] %= mod
    return sum(D[n].values()) % mod





print(main())






main()

### FIXED CODE ###

from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys



def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


def main():
    n = I()


    def ok(last, c):
        last_plus = last + c
        if 'agc' in last_plus:
            return 0
        for i in range(len(last_plus)-1):
            tmp = list(last_plus)
            tmp[i], tmp[i+1] = tmp[i+1], tmp[i]
            if 'agc' in ''.join(tmp):
                return 0
        return 1



    D = [defaultdict(int) for _ in range(n+1)]
    D[0][''] = 1


    for i in range(n):
        for k, v in D[i].items():
            for c in 'acgt':
                if ok(k, c):
                    D[i+1][(k + c)[-3:]] += v
                    D[i + 1][(k + c)[-3:]] %= mod
    return sum(D[n].values()) % mod





print(main())
import numpy as np

n = int(input())
l = sorted(list(map(int, input().split())))
nl = np.array(l)

cnt = 0

for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        cnt += sum(nl[j+1:] < a + b)

print(cnt)

### FIXED CODE ###

from bisect import *

n = int(input())
l = sorted(list(map(int, input().split())))

cnt = 0

for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        lower = max(j+1, bisect_right(l, b-a))
        upper = bisect_left(l, a+b)
        cnt += max(0, upper-lower)

print(cnt)
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        A = [list(map(int, input().split())) for _ in range(N)]

        already_p = set()
        days = 0
        done = set()
        while True:
            for i, a in enumerate(A):
                if len(a) == 0:
                    done.add(i + 1)
                    continue
                if i + 1 not in already_p:
                    if a[0] not in already_p:
                        if A[a[0] - 1][0] == i + 1:
                            already_p.add(i + 1)
                            already_p.add(a[0])
                            A[a[0] - 1] = A[a[0] - 1][1:]
                            A[i] = a[1:]

            if len(done) == N:
                break

            if len(already_p) == 0:
                print(-1)
                exit()

            already_p = set()
            days += 1

        print(days)


if __name__ == '__main__':
    AtCoder().main()

### FIXED CODE ###

import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        S = input().rstrip()
        T = input().rstrip()

        ans = 0
        for i, s in enumerate(S):
            if s == T[i]:
                ans += 1
        print(ans)


if __name__ == '__main__':
    AtCoder().main()
N = int(input())
S = input()
 
le=N
 
ans = 0
for i in range(le-1):
  if S[i]=="#" and S[i+1]==".":
    ans += 1
    S = S[:i+1] + "#" + S[i+2:]
  
if 2*ans < N:
  print(ans)
 
else:
  print(le-ans)

### FIXED CODE ###

li = list(map(int, input().split()))
A = li[0]
B = li[1]
C = li[2]
 
if A < C < B or A > C > B:
  print("Yes")
  
else:
  print("No")
n,m = map(int,input().split())
a = [map(int,input().split())]
print(max(n-sum(a)),-1)


### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
print(max(n-sum(a),-1))