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

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    A.sort()                    # 昇順 O(NlongN)
    BC = list(zip(B, C))
    BC.sort(key=lambda x: x[1], reverse=True)  # 降順 MlogM
    Cs = []
    for b, c in BC:             # M
        Cs.extend([c]*b)

    s = 0
    for i, (a, c) in enumerate(zip(A, Cs)):
        if a >= c:
            s += a
            break
        s += max(a, c)
    if i < len(A)-1:
        for j in range(i+1, len(A)):
            s += A[j]
    print(s)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, A, B, C)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    A.sort()                    # 昇順 O(NlongN)
    BC = list(zip(B, C))
    BC.sort(key=lambda x: x[1])  # 昇順 MlogM

    s = 0
    Cs = []
    for i, a in enumerate(A):
        if len(Cs) == 0:
            if len(BC) == 0:
                s += sum(A[i:])
                break
            b, c = BC.pop(-1)
            Cs.extend([c]*b)
        s += max(Cs.pop(), a)
    print(s)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, A, B, C)


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

N=int(input())
S=input()
import collections
import bisect
table=collections.defaultdict(list)
mod=10**9 +7
for i in range(N):
  table[S[i]].append(i)
ans=0
q=collections.deque()
for i,x in enumerate(S):
  q.append((i,set([x])))
  ans+=1
  while(q):
    id,s=q.popleft()
    for z in table:
      if z in s:
        continue
      else:
        k=bisect.bisect_left(table[z],id)
        if k!= len(table[z]):
          for i in range(k,len(table[z])):
            q.append((table[z][i], s|{z}))
            ans+=1
          ans%=mod               
print(ans)
        
  
  

### FIXED CODE ###

import collections
N = int(input())
S = input()

table = collections.defaultdict(int)
for i in range(N):
    table[S[i]] += 1
ans = 1
mod = 10**9 + 7
alpha = 'abcdefghijklmnopqrstuvwxyz'
for x in alpha:
    ans *= table[x] + 1
    ans %= mod

print((ans-1) % mod)
### BUGGY CODE ###

from sys import stdin
inf = 10**3
n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
point = 0
for i in range(m):
    d = [[inf for i in range(n)]for j in range(n)]
    lin = li[:i]+li[i+1:]
    for j in range(m-1):
        d[lin[j][0]-1][lin[j][1]-1] = 1
        d[lin[j][1]-1][lin[j][0]-1] = 1
    for k in range(n):
        d[k][k] = 0
    lis = warshall_floyd(d)
    for i in lis:
        i.sort()
        if i[-1] == inf:
            point += 1
            break
print(point)

### FIXED CODE ###

from sys import stdin

inf = 10**3
n,m = [int(x) for x in stdin.readline().rstrip().split()]

li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
nu = []

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    #k：中継
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
point = 0
for i in range(m):
    d = [[inf for i in range(n)]for j in range(n)]
    lin = li[:i]+li[i+1:]
    for j in range(m-1):
        d[lin[j][0]-1][lin[j][1]-1] = 1
        d[lin[j][1]-1][lin[j][0]-1] = 1
    for k in range(n):
        d[k][k] = 0
    lis = warshall_floyd(d)
    for i in lis:
        if inf in i:
            point += 1
            break
print(point)
### BUGGY CODE ###

n = int(input())
A = [int(i) for i in input().split()]

a = A[0]
B = A[:]
B.sort()

for i in range(1, n):
    C = [a, A[i]]
    for j in range(2, n):
        C.append(C[j - 2] ^ C[j - 1])
    if C[-2] ^ C[-1] == C[0]:
        C.sort()
        if C == B:
            print('Yes')
            exit()

print('No')

### FIXED CODE ###

n = int(input())
A = [int(i) for i in input().split()]

S = 0

for a in A:
    S ^= a

print('Yes' if S == 0 else 'No')
### BUGGY CODE ###

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

MOD = 1000000007

sum = [[0] * m for _ in range(n)] 

for i, si in enumerate(s):  
  for j, tj in enumerate(t):
    sum[i][j] += sum[i-1][j] if i > 0 else 0
    sum[i][j] %= MOD
    sum[i][j] += sum[i][j-1] if j > 0 else 0
    sum[i][j] %= MOD

    if si == tj:
      sum[i][j] += 1
    else:
      sum[i][j] -= sum[i-1][j-1] if i > 0 and j > 0 else 0
      sum[i][j] %= MOD

    sum[i][j] %= MOD


print((sum[n-1][m-1] + 1) % MOD)

### FIXED CODE ###

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

MOD = 1000000007

dp= [[0] * m for _ in range(n)] 

for i, si in enumerate(s):  
  for j, tj in enumerate(t):
    if i > 0:
      dp[i][j] += dp[i-1][j]
      
    if j > 0:
      dp[i][j] += dp[i][j-1]

    if si == tj:
      dp[i][j] += 1
    elif i > 0 and j > 0:
      dp[i][j] -= dp[i-1][j-1]
    
    dp[i][j] %= MOD

print((dp[n-1][m-1] + 1) % MOD)
### BUGGY CODE ###

import sys

N, K = map(int, input().strip().split(' '))
S = input().strip()
prev = ''
l = 0
lst = []
for s in S:
    if s == prev:
        l += 1
    else:
        lst += [l]
        l = 1
    prev = s
lst += [l]
lst = lst[1:]
# print(lst)

res = 0
flip = S[0] == '1'
for i in range(len(lst)):
    # print(lst[i:i+2*K+flip])
    res = max(res, sum(lst[i:i+2*K+flip]))
    flip ^= 1

#print(N, K)
# print(S)
print(res)


### FIXED CODE ###

import sys

N, K = map(int, input().strip().split(' '))
S = input().strip()
prev = ''
l = 0
lst = []
for s in S:
    if s == prev:
        l += 1
    else:
        lst += [l]
        l = 1
    prev = s
lst += [l]
lst = lst[1:]
# print(lst)

flip = S[0] == '1'
res = sum(lst[0:2*K+flip])
cur = res
# print(cur)
flip ^ - 1
for i in range(1, len(lst)):
    cur -= lst[i-1]
    if not flip:
        cur += sum(lst[i+2*K-1:i+2*K+1])
        res = max(cur, res)
        # print(lst[i+2*K:i+2*K+2])
    # res = max(res, sum(lst[i:i+2*K+flip]))
    # print(cur)
    flip ^= 1

# print(N, K)
# print(S)
print(res)
### BUGGY CODE ###

def solve(string):
    n, m, *a = map(int, string.split())
    ans = [0] * (n + 1)
    ans[0] = ans[1] = 1
    for i in range(2, n + 1):
        if i in a:
            continue
        if i - 2 not in a:
            ans[i] += ans[i - 2]
        if i - 1 not in a:
            ans[i] += ans[i - 1]
    return str(ans[-1] % (10**9 + 7))


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))


### FIXED CODE ###

def solve(string):
    n, m, *a = map(int, string.split())
    ans = [0] * (n + 1)
    for _a in a:
        ans[_a] = -1
    ans[0] = 1
    ans[1] = 1 if ans[1] == 0 else 0
    for i in range(2, n + 1):
        if ans[i] == -1:
            ans[i] = 0
            continue
        ans[i] += ans[i - 2] % 1000000007
        ans[i] += ans[i - 1] % 1000000007
    return str(ans[-1] % 1000000007)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
s = 1
for i in range(n):
    s*=a[i]
if s>10**18: print(-1)
else: print(s)



### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
if(a[0]==0): print(0)
else:
    s = 1
    for i in range(n):
        s*=a[i]
        if s>10**18:
            print(-1)
            break
    else: print(s)
### BUGGY CODE ###

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

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

if N == 1:
  print(N)
  exit()

if A[0] == 1 and A[1] == 1:
  print(0)
  exit()
if A[0] == 1 and A[1] != 1:
  print(1)
  exit()

for i in range(N):
  x = A[i]
  if isPrime(x):
    if i - 1 >= 0 and x == A[i - 1]:
        cnt -= 1
        continue
    if i + 1 < N and x == A[i + 1]:
        cnt -= 1
        continue
    continue
    
  for j in range(min(i + 2, N)):
    if i == j:
      continue
    y = A[j]
    if x % y == 0:
      cnt -= 1
      break
print(cnt)


### FIXED CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
m = A[-1]
B = [0] * m
for a in A:
  B[a - 1] += 1
  if B[a - 1] == 1:
    for j in range(a * 2, m + 1, a):
      B[j - 1] = 2
print(B.count(1))
### BUGGY CODE ###

from collections import deque
N, Q = map(int, input().split())
child = [[i] for i in range(N)]
counter = [0] * N
graph = [deque([]) for _ in range(N + 1)]
for i in range(N - 1):
  a, b =  map(int, input().split())
  graph[a - 1].append(b - 1)
  graph[b - 1].append(a - 1)
  
for i in range(Q):
  p, x = map(int, input().split())
  counter[p - 1] += x 

#print(graph, counter)
# 深さ優先探索
def dfs(v):
    #global time
    #time += 1
    visited[v] = 1
    stack = [v]
    #print(stack, v)
    #arrive_time[v] = time
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if visited[w] == 0:
              visited[w] = 1
              counter[w] += counter[v]
              stack.append(w) 
        else:
            stack.pop()          
    return 0

visited = [0] * N
# 孤立している頂点対策
for i in range(N):
    if visited[i] == 0:
       dfs(i)


#print(counter)
for i in range(N):
  print(counter[i], end = " ")

### FIXED CODE ###

import sys
input = sys.stdin.readline


N,Q=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]
PLUS=[list(map(int,input().split())) for i in range(Q)]

SCORE=[0]*(N+1)
for p,x in PLUS:
    SCORE[p]+=x

ELIST=[[] for i in range(N+1)]

for x,y in EDGE:
    ELIST[x].append(y)
    ELIST[y].append(x)
#print(ELIST)

from collections import deque
Q=deque([1])

USED=[0]*(N+1)
USED[1]=1
#USED = [0, 1, 0, 0, 0] Ex1
#SCORE = [0, 100, 10, 1, 0] Ex1
#ELIST = [[], [2], [1, 3, 4], [2], [2]] Ex1

while Q:
    x=Q.pop()

    for to in ELIST[x]:
        if USED[to]==0:
            USED[to]=1
            SCORE[to]+=SCORE[x]
            Q.append(to)

print(*SCORE[1:])
### BUGGY 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)
p2=p[:x]
q2=q[:y]
memop=x-1
memoq=y-1
sp=sum(p2)
sq=sum(q2)
k=0
flagp=0
flagq=0
while k<c:
    if memop<0:
        flagp=1
    if memoq<0:
        flagq=1
    if flagp*flagq==1:
        break
    elif flagq==1:
        if p2[memop]>=r[k]:
            break
        else:
            sp-=p2[memop]
            sp+=r[k]
            k+=1
            memop-=1
    elif flagp==1:
        if q2[memoq]>=r[k]:
            break
        else:
            sq-=q2[memoq]
            sq+=r[k]
            k+=1
            memoq-=1
    elif p2[memop]>=r[k] and q2[memoq]>=r[k] and flagp+flagq==0:
        break
    elif p2[memop]>q2[memoq]:
        sq-=q2[memoq]
        sq+=r[k]
        k+=1
        memoq-=1
    elif p2[memop]>=q2[memoq]:
        sp-=p2[memop]
        sp+=r[k]
        k+=1
        memop-=1
print(sp+sq)


### 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)
p2=p[:x]
q2=q[:y]
memop=x-1
memoq=y-1
sp=sum(p2)
sq=sum(q2)
k=0
flagp=0
flagq=0
while k<c:
    if memop<0:
        flagp=1
    if memoq<0:
        flagq=1
    if flagp*flagq==1:
        print(sp+sq)
        exit()
    elif flagq==1:
        if p2[memop]>=r[k]:
            print(sp+sq)
            exit()
        else:
            sp-=p2[memop]
            sp+=r[k]
            k+=1
            memop-=1
    elif flagp==1:
        if q2[memoq]>=r[k]:
            print(sp+sq)
            exit()
        else:
            sq-=q2[memoq]
            sq+=r[k]
            k+=1
            memoq-=1
    elif p2[memop]>=r[k] and q2[memoq]>=r[k] and flagp+flagq==0:
        print(sp+sq)
        exit()
    elif p2[memop]>q2[memoq]:
        sq-=q2[memoq]
        sq+=r[k]
        k+=1
        memoq-=1
    elif p2[memop]<=q2[memoq]:
        sp-=p2[memop]
        sp+=r[k]
        k+=1
        memop-=1
print(sp+sq)
### BUGGY CODE ###

import sys
from heapq import heapify, heappop

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    S = input()
    k = int(input())
    n = len(S)

    SS = set()
    for i in range(n):
        ss = S[i]
        SS.add(ss)
        for j in range(i + 1, n):
            ss += S[j]
            SS.add(ss)

    SS = list(SS)
    heapify(SS)
    for _ in range(k):
        res = heappop(SS)
    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
from heapq import heapify, heappop

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    S = input()
    k = int(input())
    n = len(S)

    SS = set()
    for i in range(n):
        ss = S[i]
        SS.add(ss)
        for j in range(i + 1, min(n, i + k)):
            ss += S[j]
            SS.add(ss)

    SS = list(SS)
    heapify(SS)
    for _ in range(k):
        res = heappop(SS)
    print(res)


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

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

ans = 0
for i in range(n):
    a = L[i]
    for j in range(i+1,n):
        b = L[j]
        for k in range(j+1,n):
            c = L[k]
            if a<b+c and b<c+a and c<a+b:
                ans+=1
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
L = list(map(int,input().split()))

#棒の長さa,bを固定して、あとはc<a+bとなるcを2部探索で探せばよい
L.sort()
ans = 0
for i in range(n-2):
    a = L[i]
    for j in range(i+1,n):
        b = L[j]
        tmp = bisect.bisect_left(L,a+b)
        if j<tmp:
            ans+=tmp-j-1
print(ans)
### BUGGY CODE ###

import numpy as np
from sys import stdin

N, M, Q = map(int, input().split())
data = [[0] * (N+1) for _ in range(N+1)]
for i in range(M):
    L, R = map(int, input().split())
    data[L][R] += 1
for i in range(N+1):
    for j in range(N):
        data[i][j+1] += data[i][j]
for i in range(Q):
    p, q = map(int, input().split())
    answer = 0
    for j in range(p, q+1):
        answer += data[j][q] - data[j][p-1]
    print(answer)

### FIXED CODE ###

import numpy as np

N, M, Q = map(int, input().split())
data = [[0] * (N+1) for _ in range(N+1)]

for i in range(M):
    l, r = map(int, input().split())
    data[l][r] += 1

data = np.array(data)
np.cumsum(data, axis=0, out=data)
np.cumsum(data, axis=1, out=data)
data = data.tolist()
#print(data)
for i in range(Q):
    p, q = map(int, input().split())
    p -= 1
    x = data[q][q]
    x -= data[p][q] + data[q][p]
    x += data[p][p]
    print(x)
### BUGGY CODE ###

from collections import deque
import copy
dp = {}

def dfs(N, K, k, have, q):
  if k == K:
    return sum(have)
  else:
    if not ((k, tuple(q)) in dp):
      a = [sum(have)]
      if len(q) > 0:
        tmp_q = copy.copy(q)
        tmp_have = copy.copy(have)
        v = tmp_q.popleft()
        tmp_have.append(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
        tmp_q = copy.copy(q)
        tmp_have = copy.copy(have)
        v = tmp_q.pop()
        tmp_have.append(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
      if len(have) > 0:
        tmp_q = copy.copy(q)
        tmp_have = sorted(copy.copy(have))
        v = tmp_have.pop(0)
        tmp_q.appendleft(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
        tmp_q = copy.copy(q)
        tmp_have = sorted(copy.copy(have))
        v = tmp_have.pop(0)
        tmp_q.append(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
      dp[(k, tuple(q))] = max(a)
    return dp[(k, tuple(q))]


N, K = map(int, input().split())
V = deque(list(map(int, input().split())))
print(dfs(N, K, 0, [], V))




### FIXED CODE ###

N, K = map(int, input().split())
V = list(map(int, input().split()))
M = min(N, K)
ans = 0
for p in range(M+1):
  for q in range(M-p+1):
    left = []
    right = []
    if p > 0:
      left = V[:p]
    if q > 0:
      right = V[-q:]
    have = sorted((left+right).copy())
    if len(have) > 0:
      for i in range(min(len(have),K-p-q+1)):
        if have[i] > 0:
          break
      ans = max(sum(have[i:]),ans)
print(ans)
### BUGGY CODE ###

input_array = [int(i) for i in input().split()]
S = str(input())

N = int(input_array[0])
K = int(input_array[1])

S_array = list(S)

S_count_array = [0]

count = 0
for i in range(len(S_array)):
  if i == 0:
    S_count_array[count] = 1
  else:
    if S_array[i] == S_array[i-1]:
      S_count_array[count] += 1
    else:
      S_count_array.append(1)
      count += 1

max_sum_number = 0
if S_array[0] == "0":
  for i in range(len(S_count_array)):
    if i % 2 == 0:
      sum_number = sum(S_count_array[i:i+(K*2)])
      if max_sum_number < sum_number:
        max_sum_number = sum_number
    else:
      sum_number = sum(S_count_array[i:i+(K*2)+1])
      if max_sum_number < sum_number:
        max_sum_number = sum_number

else:
  for i in range(len(S_count_array)):
    if (i+1) % 2 == 0:
      sum_number = sum(S_count_array[i:i+(K*2)])
      if max_sum_number < sum_number:
        max_sum_number = sum_number
    else:
      sum_number = sum(S_count_array[i:i+(K*2)+1])
      if max_sum_number < sum_number:
        max_sum_number = sum_number

print(max_sum_number)

### FIXED CODE ###

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

l = [0]

for i in range(n-1):
  if s[i] != s[i+1]:
    l.append(i+1)

l.append(n)

ans = 0
for i in range(len(l)-1):
  index = min(i+2*k + int(s[l[i]]=="1"), len(l)-1)
  ans = max(ans, l[index] - l[i])

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

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W = inpl()

white = 0
MAP = [['#']*(W+2)]
for i in range(H):
	li = list(input())
	white += li.count('.')
	MAP.append(['#'] + li + ['#'])
MAP.append(['#']*(W+2))

memo = [[INF for x in range(W+2)] for y in range(H+2)]
q = queue.Queue()
q.put([1,1,1])

def check(x,y,n):
	if memo[y][x] < n or MAP[y][x] == '#':
		return
	elif x==W and y==H:
		print(white-n)
		sys.exit()
	else:
		memo[y][x] = n
		q.put([x-1,y,n+1])
		q.put([x+1,y,n+1])
		q.put([x,y-1,n+1])
		q.put([x,y+1,n+1])


while not q.empty():
	x,y,n = q.get()
	check(x,y,n)

print(-1)


### FIXED CODE ###

import sys
import queue

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


white = 0
	
maze = []

for y in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(li)

if maze[0][0] == '#' or maze[H-1][W-1] == '#':
	print (-1)
	sys.exit()

	
maze[H-1][W-1] =	'g'
	
q = queue.Queue()
q.put([0,0,0])

def check(x,y,n):
	if 0 <= x < W and 0 <= y < H:
		if maze[y][x] == 'g':
			print (white - n - 1)
			sys.exit()
		elif maze[y][x] == '.':
			maze[y][x] = n
			q.put([x-1,y,n+1])
			q.put([x+1,y,n+1])
			q.put([x,y-1,n+1])
			q.put([x,y+1,n+1])
		else:
			return
	else:
		return


while not q.empty():
	x,y,n = q.get()
	check(x,y,n)
	
print(-1)
### BUGGY CODE ###

num = int(input())
val = [int(x) for x in input().split()]
res_val = []
for i in val:
    res_val.append(i-1)
    res_val.append(i)
    res_val.append(i+1)

set_val = set(res_val)

res = 0
for j in set_val:
    if res < res_val.count(j):
        res = res_val.count(j)
print(res)

### FIXED CODE ###

num = int(input())
val = [int(x) for x in input().split()]

numbers = [int(x) for x in range(-1, 100001)]
numbers_dict = dict()

for number in numbers:
    numbers_dict[number] = numbers_dict.get(number, 0) + 1

for i in val:
    numbers_dict[i - 1] += 1
    numbers_dict[i] += 1
    numbers_dict[i + 1] += 1

print(max(numbers_dict.values())-1)
### BUGGY CODE ###

number = list(map(int,input().split()))
line = list(map(int,input().split()))
 
num = number[0]
K = number[1]
dp = [0, abs(line[1] - line[0])]
for i in range(2, num):
  line2 = []
  a = min([(dp[-k] + abs(line[i] - line[i - k])) for k in range(1, min(i + 1 , K + 1))])
  dp += [a]
print(dp[-1])

### FIXED CODE ###

def ans():
    n, k, *h = map(int, open(0).read().split())
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(1, n):
        min_j = max(0, i-k)
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(min_j , i)])
    print(dp[n-1])
 
ans()
### BUGGY CODE ###

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

import collections

c = collections.Counter(A)
values, counts = zip(*c.most_common()[::-1])
counts = list(counts)
cnt = 0
inf = 10 ** 18


for _ in range(inf):
  if len(counts) <= K:
    print(cnt)
    break

  cnt +=  counts[0]  
  counts = counts[1:]
    


### FIXED CODE ###

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

import collections
from itertools import accumulate

c = collections.Counter(A)
_, counts = zip(*c.most_common()[::-1])
counts = list(accumulate(counts))
cnt = 0
inf = 10 ** 18

target = len(counts) - K 
 
if target <= 0:
  print(0)
else:
  print(counts[target-1])
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

INF = 10 ** 18
DP = [INF] * n
DP[0] = 0

for i in range(1, n):
    DP[i] = min(DP[i-j] + abs(H[i] - H[i-j]) for j in range(1, k+1) if i - j >= 0)

print(DP[n-1])


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

INF = 10 ** 18
DP = [INF] * n
DP[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if i + j >= n:
            break
        DP[i+j] = min(DP[i+j], DP[i] + abs(H[i+j] - H[i]))

print(DP[n-1])
### BUGGY CODE ###

from collections import deque
n,m=map(int,input().split())
ab=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  ab[a].append(b)
  ab[b].append(a)
l,ll=deque([1]),deque([])
ans=[-1]*n
while l:
  x=l.popleft()
  ll.append(x)
  for i in ab[x]:
    if i in ll:
      continue
    if i in l:
      continue
    l.append(i)
    ans[i-1]=x
if all(i>=0 for i in ans[1:]):
  print('Yes')
  for i in ans[1:]:
    print(i) 
else:
  print('No')

### FIXED CODE ###

def main():
  from collections import deque
  n,m=map(int,input().split())
  ab=[[] for _ in range(n+1)]
  for _ in range(m):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
  
  l=deque([1])
  ans=[-1]*n
  while l:
    x=l.popleft()
    for i in ab[x]:
      if ans[i-1]==-1:
        ans[i-1]=x
        l.append(i)
  print('Yes')
  for i in ans[1:]:
    print(i) 
    
if __name__=='__main__':
  main()
### BUGGY CODE ###

x = input()
l = len(x)

before = l

for i in range(100000):
    x = x.replace("ST", "", 100000)
    current = len(x)
    #print(x)
    if current == 0 or current == before:
        break
    before = current

print(len(x))


### FIXED CODE ###

s = input()
l = len(s)

num = 0
ans = l
for i in range(l):
    if s[i] == "S":
        num += 1
    else:
        if num == 0:
            continue
        else:
            num -= 1
            ans -= 2

print(ans)