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

N = int(input())
balls = []
for i in range(2 * N):
    c, a = input().split()
    balls += [(c, int(a))]

# numB[i][b]: 初期状態において、i番目の玉より右にある、1～bが書かれた黒玉の数
numB = [[0] * (N + 1) for i in range(2 * N)]
numW = [[0] * (N + 1) for i in range(2 * N)]
for i in reversed(range(1, 2 * N)):
    c, a = balls[i]
    numB[i - 1] = numB[i].copy()
    numW[i - 1] = numW[i].copy()
    if c == 'B':
        for b in range(a, N + 1):
            numB[i - 1][b] += 1
    else:
        for w in range(a, N + 1):
            numW[i - 1][w] += 1

# costB[b][w]: 黒玉1～b、白玉1～wのうち、初期状態において、黒玉[b+1]より右にある玉の数
costB = [[0] * (N + 1) for i in range(N + 1)]
costW = [[0] * (N + 1) for i in range(N + 1)]
for i in reversed(range(2 * N)):
    c, a = balls[i]
    if c == 'B':
        cost = numB[i][a - 1]
        for w in range(N + 1):
            costB[a - 1][w] = cost + numW[i][w]
    else:
        cost = numW[i][a - 1]
        for b in range(N + 1):
            costW[b][a - 1] = cost + numB[i][b]

dp = [[float('inf')] * (N + 1) for i in range(N + 1)]
dp[0][0] = 0
for b in range(N + 1):
    for w in range(N + 1):
        if b > 0:
            dp[b][w] = min(dp[b][w], dp[b - 1][w] + costB[b - 1][w])
        if w > 0:
            dp[b][w] = min(dp[b][w], dp[b][w - 1] + costW[b][w - 1])

print(dp[N][N])


### FIXED CODE ###

N = int(input())
balls = []
for i in range(2 * N):
    c, a = input().split()
    balls += [(c, int(a))]

# numB[i][b]: 初期状態において、i番目の玉より右にある、1～bが書かれた黒玉の数
numB = [[0] * (N + 1) for i in range(2 * N)]
numW = [[0] * (N + 1) for i in range(2 * N)]
for i in reversed(range(1, 2 * N)):
    c, a = balls[i]
    numB[i - 1] = list(numB[i])
    numW[i - 1] = list(numW[i])
    if c == 'B':
        for b in range(a, N + 1):
            numB[i - 1][b] += 1
    else:
        for w in range(a, N + 1):
            numW[i - 1][w] += 1

# costB[b][w]: 黒玉1～b、白玉1～wのうち、初期状態において、黒玉[b+1]より右にある玉の数
costB = [[0] * (N + 1) for i in range(N + 1)]
costW = [[0] * (N + 1) for i in range(N + 1)]
for i in reversed(range(2 * N)):
    c, a = balls[i]
    if c == 'B':
        cost = numB[i][a - 1]
        for w in range(N + 1):
            costB[a - 1][w] = cost + numW[i][w]
    else:
        cost = numW[i][a - 1]
        for b in range(N + 1):
            costW[b][a - 1] = cost + numB[i][b]

dp = [[float('inf')] * (N + 1) for i in range(N + 1)]
dp[0][0] = 0
for b in range(N + 1):
    for w in range(N + 1):
        if b > 0:
            dp[b][w] = min(dp[b][w], dp[b - 1][w] + costB[b - 1][w])
        if w > 0:
            dp[b][w] = min(dp[b][w], dp[b][w - 1] + costW[b][w - 1])

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

def main():
    n, m = map(int, input().split())
    st = [list(map(int, input().split())) for _ in range(m)]

    g = [[] for _ in range(n)]

    for s, t in st:
        s -= 1
        t -= 1
        g[s].append(t)

    deg = [len(x) for x in g]

    dp = [0] * n

    for u in range(n-1)[::-1]:
        now = 0
        for v in g[u]:
            now += dp[v]

        now /= deg[u]
        now += 1
        dp[u] = now

    ans = dp[0]

    for u in range(n-1):
        if deg[u] == 1:
            continue

        d = g[u][0]
        for v in g[u]:
            if dp[d] < dp[v]:
                d = v

        dp2 = [0] * n
        for x in range(n - 1)[::-1]:
            now = 0
            for y in g[x]:
                if x == u and y == d:
                    continue
                now += dp2[y]

            if x == u:
                now /= deg[x] - 1
            else:
                now /= deg[x]

            now += 1
            dp2[x] = now

        ans = min(ans, dp2[0])

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    st = [list(map(int, input().split())) for _ in range(m)]

    g = [[] for _ in range(n)]

    for s, t in st:
        s -= 1
        t -= 1
        g[s].append(t)

    deg = [len(x) for x in g]

    dp = [0] * n

    for u in range(n-1)[::-1]:
        now = 0
        for v in g[u]:
            now += dp[v]

        now /= deg[u]
        now += 1
        dp[u] = now

    ans = dp[0]

    for u in range(n-1):
        if deg[u] == 1:
            continue

        d = g[u][0]
        for v in g[u]:
            if dp[d] < dp[v]:
                d = v

        dp2 = [0] * n
        for x in range(n - 1)[::-1]:
            now = 0
            for y in g[x]:
                if x == u and y == d:
                    continue
                now += dp2[y]

            if x == u:
                now /= deg[x] - 1
            else:
                now /= deg[x]

            now += 1
            dp2[x] = now

        ans = min(ans, dp2[0])

    print(ans)


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

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

dp = [1000000000] * N
dp[0] = 0

for i in range(N - 1):
    for j in range(1, K + 1):
        if i + j < N:
            if dp[i + j] > abs(h[i + j] - h[i]) + dp[i]:
                dp[i + j] = abs(h[i + j] - h[i]) + dp[i]
        else:
            break

print(dp[N - 1])

### FIXED CODE ###

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

dp = [1000000000] * N
dp[0] = 0

for i in range(N - 1):
    for j in range(1, K + 1):
        if i + j < N:
            if dp[i + j] > abs(h[i + j] - h[i]) + dp[i]:
                dp[i + j] = abs(h[i + j] - h[i]) + dp[i]
        else:
            break

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

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

dp = [[0 for j in range(w + 1)] for i in range(2)]

for i, (wi, vi) in enumerate(x):
    dp_pre = dp[1 - i % 2]
    dp_cur = dp[i % 2]
    for j in range(1, wi):
        dp_cur[j] = dp_pre[j]
    for j in range(wi, w + 1):
        dp_cur[j] = max(dp_pre[j], dp_pre[j - wi] + vi)
print(max(dp_cur))


### FIXED CODE ###

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

dp = [[0 for j in range(w + 1)] for i in range(2)]

for i, (wi, vi) in enumerate(x):
    dp_pre = dp[1 - i % 2]
    dp_cur = dp[i % 2]
    for j in range(1, wi):
        dp_cur[j] = dp_pre[j]
    for j in range(wi, w + 1):
        dp_cur[j] = max(dp_pre[j], dp_pre[j - wi] + vi)
print(max(dp_cur))
### BUGGY CODE ###

import bisect

Q=int(input())

b=0
a=[]
min=0
tmp=0
j=0
for i in range(Q):
    que=list(map(int,input().split()))
    if que[0]==1:
        j+=1
        b+=que[2]
        a.insert(  bisect.bisect_left(a,que[1]), que[1] )

        p= bisect.bisect_left(a,tmp)
        q= bisect.bisect_right(a,tmp)
        if p>j-p:
            min+=abs(que[1]-tmp)-abs(a[p-1]-tmp) 
            tmp=a[p-1]
        elif p==j-p:
            min+=abs(que[1]-tmp)
            tmp=a[p-1]
        elif q<j-q:
            min+=abs(que[1]-tmp)-abs(a[q]-tmp) 
            tmp=a[q]
        else:

            min+=abs(que[1]-tmp)

    elif que[0]==2:
        print(tmp,min+b)

### FIXED CODE ###

import bisect
import heapq 

Q=int(input())

que=list(map(int,input().split()))
b=que[2]
l,r=[-que[1]],[que[1]]
heapq.heapify(l)
heapq.heapify(r)
a=0
tmp=que[1]
j=1
for i in range(Q-1):
    que=list(map(int,input().split()))
    if que[0]==1:
        j+=1
        b+=que[2]
        q1=que[1]
        if j%2==0:
            if q1<-l[0]:
                heapq.heappushpop(l,-q1)
            else:
                heapq.heappushpop(r,q1)

        else:
            if q1<-l[0]:
                heapq.heappush(l,-q1)
                heapq.heappush(r,-l[0])
            else:
                heapq.heappush(r,q1)
                heapq.heappush(l,-r[0])
        

        if -l[0]!=r[0]: a+=abs(tmp-q1)
        else: a+=abs(tmp-q1)-abs(-l[0]-tmp)
        tmp=-l[0]

    elif que[0]==2:
        print(tmp,a+b)
### BUGGY CODE ###

N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N)]
for i, (ai, bi) in enumerate(ab):
    graph[ai - 1].append(bi)
    graph[bi - 1].append(ai)

# print("#", graph)

parent = [None] * N
from collections import deque
q = deque([(1, None)])
while len(q) > 0:
    src, prev = q.popleft()
    for dst in graph[src - 1]:
        if dst == prev: continue
        parent[dst - 1] = src
        q.append((dst, src))

# print("#", parent)

cnttab = [0] * N
for j, (pj, xj) in enumerate(px):
    cnttab[pj - 1] += xj

# print("#", cnttab)
    
ans = [0] * N
for i in range(N):
    pos = i + 1
    while pos != None:
        # print("##", pos)
        ans[i] += cnttab[pos - 1]
        pos = parent[pos - 1]

print(' '.join(map(str, ans)))

### FIXED CODE ###

N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N)]
for ai, bi in ab:
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

parent = [None] * N
parent[0] = 0

score = [0] * N
for pi, xi in px:
    score[pi - 1] += xi

ans = [None] * N

from collections import deque

q = deque([(0, 0)])
while len(q) > 0:
    src, score_tmp = q.popleft()
    score_tmp += score[src]
    ans[src] = score_tmp
    for dst in graph[src]:
        if ans[dst] != None: continue
        q.append((dst, score_tmp))

print(' '.join(map(str, ans)))
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
m=0
l=0
for i in range(n-k+1):
  if sum(p[i:i+k])>m:
    m=sum(p[i:i+k])
    l=(m+k)/2
print(l)
    


### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
a=[0]*n
a[0]=p[0]
for i in range(n-1):
  a[i+1]=a[i]+p[i+1]
m=a[k-1]
for j in range(n-k):
  if a[j+k]-a[j]>m:
    m=a[j+k]-a[j]
print((m+k)/2)
### BUGGY CODE ###

n=int(input())
l=[int(i) for i in input().split()]
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if l[i]+l[j]>l[k] and l[i]+l[k]>l[j] and l[k]+l[j]>l[i]:
        ans+=1
print(ans)
      
        
        


### FIXED CODE ###

n=int(input())
l=[int(i) for i in input().split()]
l.sort()
ans=0
ans1=0
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+ans1,n):
      ans1=0
      if l[i]+l[j]>l[-1]:
        ans+=n-j-1
        break
      elif l[i]+l[j]<=l[k] :
        ans+=k-j-1
        ans1+=k-j-1
        break
      
      
print(ans)
### BUGGY CODE ###

s = raw_input()
while True:
    t = s.replace("ST", "")
    if len(t) == len(s):
        break
    s = t
print len(s.replace("ST", ""))


### FIXED CODE ###

s = raw_input()
c = len(s)
l = 0
was_es = True
for i in xrange(len(s)):
    if s[i] == "S":
        if was_es == True:
            l += 1
        was_es = True
    else:
        if l > 0:
            l -= 1
            c -= 2
print c
### BUGGY CODE ###

N = int(input())
A_list = [0]
A_list.extend(list(map(int, input().split())))
A_list.append(0)
previous_val = 0
dif = []
for i in A_list[1:]:
    dif.append(previous_val - i)
    previous_val = i

for idx, val in enumerate(dif):
    if idx < len(dif)-1:
        tmp1 = dif[idx]
        tmp2 = dif[idx + 1]
        dif[idx] = 0
        dif[idx + 1] = 0
        print(sum(map(abs, dif)) + abs(tmp1 + tmp2))
        dif[idx] = tmp1
        dif[idx + 1] = tmp2


### FIXED CODE ###

N = int(input())
A_list = [0]
A_list.extend(list(map(int, input().split())))
A_list.append(0)
previous_val = 0
S = 0
for i in A_list[1:]:
    S += abs(previous_val - i)
    previous_val = i

for idx, val in enumerate(A_list):
    if idx == 0 or idx == (len(A_list) - 1):
        continue
    else:
        new_dif = abs(A_list[idx - 1] - A_list[idx + 1])
        old_dif = abs(A_list[idx - 1] - A_list[idx]) + abs(A_list[idx] - A_list[idx + 1])
        print(S + new_dif - old_dif)
### BUGGY CODE ###

import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = []
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo.append(list(s_arr[start:j+1].sum(axis=0)))
            start=j+1
    kouryo.append(list(s_arr[start:].sum(axis=0)))

    kouryo = np.array(kouryo)
    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        if np.any(kouryo[:, j]>k): cnt += 10**9
        if cnt >= 10**9: break
        wa = wa + kouryo[:, j]
        if np.any(wa>k):
            cnt += 1
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)

### FIXED CODE ###

import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = np.array([[0 for _ in range(w)]])
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo = np.concatenate((kouryo, s_arr[start:j+1].sum(axis=0, keepdims=True)), axis=0)
            start=j+1
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)

    if cnt > ans: continue
    if np.any(kouryo>k): continue

    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        wa += kouryo[:, j]
        if np.max(wa)>k:
            cnt += 1
            if cnt > ans: break
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

import functools
import operator

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

ans = 1

ans = functools.reduce(operator.mul, N)

#for i in range(len(N)):
#    ans *= N[i]

if ans > 10**18:
    print('-1')
else:
    print(ans)

### FIXED CODE ###

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

ans = 1

if 0 in N:
    ans = 0
else:
    for i in range(len(N)):
        ans *= N[i]
        if ans > 10**18:
            break

if ans > 10**18:
    print('-1')
else:
    print(ans)
### BUGGY CODE ###

import math
H,N = map(int,input().split())
A = [int(x) for x in input().split()]

count = 0
sum2 = []
for i in range(2 ** N):
        sum1 = []
        for j in range(len(A)):
            if ( i >> j) & 1 == 1:
                sum1.append(A[j])

        sum2.append(sum(sum1))

if sum2.count(H) == 0:
    print("No")
else :
    print("Yes")


### FIXED CODE ###

import math
H,N = map(int,input().split())
A = [int(x) for x in input().split()]

count = 0
sum2 = []
'''for i in range(2 ** N):
        sum1 = []
        for j in range(len(A)):
            if ( i >> j) & 1 == 1:
                sum1.append(A[j])
        if sum(sum1) == H:
            count = 1
            print("Yes")
            break
'''
if sum(A) >= H:
    print("Yes")

else:
    print("No")
### BUGGY CODE ###

n, a, b = map(int, input().split())
h = [int(input()) for i in range(n)]

left = 0
right = 10**10
mid = (left + right) // 2
while right - left > 1:
    mid = (left + right) // 2
    count = 0
    for i in range(n):
        if h[i] - mid * b > 0:
            if (h[i] - mid * b) % (a - b) == 0:
                count += (h[i] - mid * b) // (a - b)
            else:
                count += (h[i] - mid * b) // (a - b) + 1
    if mid - count >= 0:
        right = mid
    else:
        left = mid
print(right)

### FIXED CODE ###

n, a, b = map(int, input().split())
h = [int(input()) for i in range(n)]

left = 0
right = 10**10
mid = (left + right) // 2
while right - left > 1:
    mid = (left + right) // 2
    count = 0
    for i in range(n):
        if h[i] - mid * b > 0:
            if (h[i] - mid * b) % (a - b) == 0:
                count += (h[i] - mid * b) // (a - b)
            else:
                count += (h[i] - mid * b) // (a - b) + 1
    if mid - count >= 0:
        right = mid
    else:
        left = mid
print(right)
### BUGGY CODE ###

import numpy as np
from itertools import product

def main():
    H,W,K = map(int, input().split())
    S = np.array(([list(map(int,list(input()))) for _ in range(H)])).T

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = np.array([0]*len(M))
            for s in S:
                D[:] += [sum(s[i] for i in m) for m in M]
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    D[:] = [sum(s[i] for i in m) for m in M]
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()

### FIXED CODE ###


def main():
    from itertools import product
    import numpy as np

    H,W,K = map(int, input().split())
    S = (np.array([list(map(int,list(input()))) for _ in range(H)]).T).tolist()

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()
### BUGGY CODE ###

N=int(input())
A=[int(input()) for _ in range(N)]
ans=0
for i in set(A):
    if A.count(i)%2==1:
        ans+=1
print(ans)

### FIXED CODE ###

N=int(input())

from collections import defaultdict
d = defaultdict(int)

for _ in range(N):
    d[int(input())] += 1

ans=0
for i in d.values():
    if i%2==1:
        ans+=1

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

def main():
    import heapq
    n,m = map(int,input().split())
    a = list(map(int,input().split()))
    h = []
    for i in range(n):
        heapq.heappush(h,a[i])
    for i in range(m):
        b,c = map(int,input().split())
        while h[0]<c and b>0:
            b = b-1
            heapq.heappop(h)
            heapq.heappush(h,c)
    print(sum(h))
        


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import bisect
    n,m = map(int,input().split())
    a = list(map(int,input().split()))
    cnt = {}
    for i in range(n):
        if a[i] not in cnt.keys():
            cnt[a[i]] = 1
        else:
            cnt[a[i]] += 1
    for _ in range(m):
        b,c = map(int,input().split())
        if c not in cnt.keys():
            cnt[c] = b
        else:
            cnt[c] += b
    sumed = 0
    s = 0
    for key in sorted(cnt.keys(),reverse=True):
        if n-sumed-cnt[key]>0:
            sumed += cnt[key]
            s += key*cnt[key]
        else:
            s+=key*(n-sumed)
            break
    print(s)


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

from collections import defaultdict
from itertools import count


def main():
    n = int(input())
    A, B = map(int, input().split())
    for _ in range(n - 1):
        t, a = map(int, input().split())
        for n in count(1):
            if n * t >= A and n * a >= B:
                A, B = n * t, n * a
                break
    print(A + B)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
from decimal import Decimal


def main():
    N = int(input())
    t, a = 1, 1
    for _ in range(N):
        _t, _a = map(int, input().split())
        n = Decimal(max(math.ceil(t / _t), math.ceil(a / _a)))
        t, a = _t * n, _a * n

    print(t + a)

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

from collections import deque
h, w, k = map(int, input().split())
y1, x1, y2, x2 = map(int, input().split())
c = []
for _ in range(h):
    c.append(input())
q = deque([(x1-1, y1-1)])
dxdy = [(-1,0), (0,-1), (0,1), (1,0)]
dist = [[100000]*w for _ in range(h)]
dist[y1-1][x1-1] = 0
while q:
    x, y = q.popleft()
    for ddx, ddy in dxdy:
        for i in range(1, k+1):
            dx = ddx*i
            dy = ddy*i
            if not (0<=x+dx<w and 0<=y+dy<h):
                break
            if c[y+dy][x+dx]=='@' or dist[y+dy][x+dx]<=dist[y][x]:
                break
            if x+dx==x2-1 and y+dy==y2-1:
                print(dist[y][x]+1)
                exit(0)
            dist[y+dy][x+dx] = dist[y][x]+1
            q.append((x+dx, y+dy))
print(-1)

### FIXED CODE ###

from collections import deque
h, w, k = map(int, input().split())
y1, x1, y2, x2 = map(int, input().split())
c = []
for _ in range(h):
    c.append(input())
q = deque([(x1-1, y1-1)])
dxdy = [(-1,0), (0,-1), (0,1), (1,0)]
dist = [[1000000]*w for _ in range(h)]
dist[y1-1][x1-1] = 0
while q:
    x, y = q.popleft()
    for ddx, ddy in dxdy:
        for i in range(1, k+1):
            dx = ddx*i
            dy = ddy*i
            if not (0<=x+dx<w and 0<=y+dy<h):
                break
            if c[y+dy][x+dx]=='@' or dist[y+dy][x+dx]<=dist[y][x]:
                break
            if x+dx==x2-1 and y+dy==y2-1:
                print(dist[y][x]+1)
                exit(0)
            if dist[y+dy][x+dx]>dist[y][x]+1:
                dist[y+dy][x+dx] = dist[y][x]+1
                q.append((x+dx, y+dy))
print(-1)
### BUGGY CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

res = 0
for i in range(10 **8):
  res += 1
  
  
print(res)

### FIXED CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

number_dict = {}
for h in range(H):
    for w in range(W):
        number_dict[A[h][w]] = (w+1, h+1)
        
        
number = [0 for _ in range(H*W+1)]
for i in range(H*W):
    now = H * W - i
    
    if now + D > H * W:
        pass
    
    else:
        number[now] = number[now + D] + abs(number_dict[now+D][0] - number_dict[now][0]) + abs(number_dict[now+D][1] - number_dict[now][1])
       

for i in range(Q):
    res = number[LR[i][0]] - number[LR[i][1]]
            
    print(res)
### BUGGY CODE ###

import sys
X = list(sys.stdin.readline().strip())
N = len(X)

def solve():
    cnt = 0
    i = 0
    while True:
        while i < N and X[i] != 'S':
            i += 1
        j = i
        while j < N and X[j] != 'T':
            j += 1
        if j >= N:
            return N - 2*cnt
        cnt += 1
        X[i] = ' '
        X[j] = ' '
        i += 1
        j += 1

print(solve())

### FIXED CODE ###

X = list(input())
N = len(X)
NHALF = N // 2

def solve():
    nt, ns = 0, 0
    for i in range(N):
        if X[i] == 'S':
            ns += 1
        elif ns > 0:
            ns -= 1
        else:
            nt += 1
    return nt + ns


print(solve())