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

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**10, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


#@njit("i4(i4[:], i4[:], i4, i4[:])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for bits in range(1 << len(vs)):
        for i in range(len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    mask = (weights <= L)     
    return np.amax(dp_[L - weights[mask]] + values[mask])

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)
from bisect import bisect_left
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

from functools import lru_cache
@lru_cache(maxsize=None)
def fibo(n):
    ind = bisect_left(A, n)
    if ind < M and n == A[ind]:
        return 0
    elif n == 0 or n == 1:
        return 1
    return fibo(n-2) + fibo(n-1)

print(fibo(N) % 1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
A = set([int(input()) for i in range(M)])
t = 10**9+7
import sys
sys.setrecursionlimit(500000)
from functools import lru_cache
@lru_cache(maxsize=None)
def fibo(n):
    if n in A:
        return 0
    elif n == 0 or n == 1:
        return 1
    return (fibo(n-2) + fibo(n-1)) % t
print(fibo(N) % t)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)
from collections import Counter
def input(): return sys.stdin.readline().strip()

N = int(input())
a = list(map(int, input().split()))
c = Counter(a)
one, two, three = c[1], c[2], c[3]
dp = [[[-1 for i in range(three + 1)] for j in range(N+1)] for k in range(N+1)]

def rec(i, j, k):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0
    if i > 0:
        res += rec(i-1, j, k) * i
    if j > 0:
        res += rec(i+1, j-1, k) * j
    if k > 0:
        res += rec(i, j+1, k-1) * k
    res += N
    res /= i+j+k
    dp[i][j][k] = res
    return res

rec(one, two, three)
print(dp[one][two][three])

### FIXED CODE ###

import sys
from collections import Counter
sys.setrecursionlimit(10000)

N = int(input())
a = list(map(int, input().split()))
dp = [[[-1 for i in range(N+1)] for j in range(N+1)] for k in range(N+1)]

def rec(i, j, k):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0
    if i > 0:
        res += rec(i-1, j, k) * i
    if j > 0:
        res += rec(i+1, j-1, k) * j
    if k > 0:
        res += rec(i, j+1, k-1) * k
    res += N
    res *= 1.0/(i+j+k)

    dp[i][j][k] = res
    return res

c = Counter(a)
one, two, three = c[1], c[2], c[3]
print(rec(one, two, three))
### BUGGY CODE ###

import numpy as np

N = int(input())
P = np.array(input().split(' '), dtype = int)
# P = list(map(int, input().split(' ')))

print(N - sum([np.any(P[:i+1] < P[i]) for i in range(N)]))

### FIXED CODE ###

N = int(input())
# P = np.array(input().split(' '), dtype = int)
P = list(map(int, input().split(' ')))

p_min = P[0]
ans = 0
for p in P:
    if p <= p_min:
        p_min = p
        ans += 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    adjmatrix[i][i] = 0
    
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if adjmatrix[a][b] > c:
        adjmatrix[a][b] = c
        adjmatrix[b][a] = c

#print(abc)

# Warshall-Floyd Algorithm
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            adjmatrix[i][j] = min([adjmatrix[i][j],
                      adjmatrix[i][k] + adjmatrix[k][j]])
            adjmatrix[j][i] = adjmatrix[i][j]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]][route[i+1]]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)
        
        

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Oct  8 10:17:39 2018

@author: maezawa
"""

import math
from itertools import permutations

#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   glath[j][i] = glath[i][k] + glath[k][j]				
	return glath

N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 
r=[int(x) for x in str(input()).split()]
graph=[[float("inf")]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c

#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)


max_count=float("inf")
for i in permutations(r):
        cost=0
        for j in range(len(i)-1):                
                cost+= all_cost[i[j]-1][i[j+1]-1]       
        max_count=min(max_count,cost)

print(max_count)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
arr = [0] * N
for i in range(N):
  arr[i] = A.index(i+1) + 1
print(*arr)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
arr = {}
for i in range(N):
  arr[A[i]] = i + 1
for i in range(N):
  print(arr[i+1], end="")
  if i == N-1:
    print("\n", end="")
  else:
    print(" ",end="")
### BUGGY CODE ###

from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()


n = int(input())

graph = [[] for _ in range(n+1)]

A = [0]+list(map(int, input().split()))

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

dist = [-1] * (n+1)
dist[0] = 0
dist[1] = 1

d = deque()
d.append((1, [0, A[1]]))


def update(dp, AA):
    ndp = dp.copy()
    if ndp[-1] < AA:
        ndp.append(AA)
    else:
        bis = bisect.bisect_left(ndp, AA)
        ndp[bis] = AA
    return ndp


while d:
    v, dp = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        newdp = update(dp, A[i])
        dist[i] = len(newdp)-1
        d.append((i, newdp))

ans = dist[1:]
print(*ans, sep="\n")

### FIXED CODE ###

from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
for i in range(m):
     b,c = map(int,input().split())
     a += [c]*b
a.sort(reverse=True)
print(sum(a[:n]))

### FIXED CODE ###

def f(n,m):
     a = list(map(int,input().split()))
     min_a = min(a)
     a = [(1,i) for i in a]
     b_c = [tuple(map(int,input().split())) for i in range(m)]
     a += b_c
     a.sort(key=lambda x:x[1])
     ans = 0
     while True:
          if n>a[-1][0]:
               ans += a[-1][0]*a[-1][1]
               n -= a[-1][0]
               a.pop()
          else:
               ans += a[-1][1]*n
               break
     print(ans)

n,m = map(int,input().split())
f(n,m)
### BUGGY CODE ###

h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="#":
			b.append(1)
			new=True
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while new:
	p=0
	black_new=[]
	new=False
	black.sort()
	q=len(black)
	for i in range(h):
		for j in range(w):
			if p>=q:
				break
			if [i,j]==black[p]:
				p+=1
				if i!=0 and field[i-1][j]==False:
					field[i-1][j]=True
					black_new.append([i-1,j])
					new=True
				if i!=h-1 and field[i+1][j]==False:
					field[i+1][j]=True
					black_new.append([i+1,j])
					new=True
				if j!=0 and field[i][j-1]==False:
					field[i][j-1]=True
					black_new.append([i,j-1])
					new=True
				if j!=w-1 and field[i][j+1]==False:
					field[i][j+1]=True
					black_new.append([i,j+1])
					new=True
	black=black_new
	ans+=1
print(ans-1)




### FIXED CODE ###

h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="#":
			b.append(1)
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while len(black):
	black_new=[]
	q=len(black)
	for k in range(q):
		i,j=black[k][0],black[k][1]
		if i!=0 and field[i-1][j]==False:
			field[i-1][j]=True
			black_new.append([i-1,j])
		if i!=h-1 and field[i+1][j]==False:
			field[i+1][j]=True
			black_new.append([i+1,j])
		if j!=0 and field[i][j-1]==False:
			field[i][j-1]=True
			black_new.append([i,j-1])
		if j!=w-1 and field[i][j+1]==False:
			field[i][j+1]=True
			black_new.append([i,j+1])
	black=black_new
	ans+=1
print(ans-1)
### BUGGY CODE ###

n = int(input())
i = 2
while True:
  if i%2==0 and i%n==0:
    print(i)
    break
  i +=1

### FIXED CODE ###

n = int(input())
if n%2==0:
  print(n)
else:
  print(2*n)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
import math
ans = 0
for i in range(math.ceil(n / r)+1):
    for j in range(math.ceil(n / g)+1):
        if n - r * i - g * j < 0:
            break
        if  (n - r * i - g * j) % b == 0:
            ans += 1
print(ans)

### FIXED CODE ###

r, g, b, n = map(int, input().split())

import math
ans = 0
for i in range(math.ceil(n / r)+1):
    for j in range(math.ceil(n / g)+1):
        if n - r * i - g * j < 0:
            break
        if  (n - r * i - g * j) % b == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

import heapq
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

from scipy.sparse.csgraph import floyd_warshall
a_opt = floyd_warshall(a)
# for i in range(n): print(a[i], a_opt[i])

def solve():
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            if a_opt[i][j] < a[i][j]:
                print(-1)
                return
            else:
                d = a[i][j]
                for k in range(n):
                    if k in [i, j]:
                        continue
                    elif a[i][k]+a[k][j] == d:
                        d = 0
                ans += d
    print(ans)
    return

solve()


### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
INF = 10**9

n = int(input())
a = np.array([list(map(int, input().split())) for _ in range(n)])
a_opt = floyd_warshall(a)
# for i in range(n): print(a[i], a_opt[i])

for i in range(n):
    a[i][i] = INF
    
ans = 0
for i in range(n):
    for j in range(i+1, n):
        if a_opt[i][j] < a[i][j]:
            print(-1)
            exit()
        else:
            d = a[i][j]
            if d < np.min(a[i]+a[j]):
                ans += d
                
            # Straight solution, but TLE in python
            # for k in range(n):
            #     if k in [i, j]:
            #         continue
            #     elif a[i][k]+a[k][j] == d:
            #         d = 0
            # ans += d
print(ans)
### BUGGY CODE ###

import random
from copy import deepcopy

n,m,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(q)]

gene_length=n
individual_length=n*10
generation=100
elite_gene=1
individual_mutation=0.01
gene_mutation=0.01

def get_population():
  pop=[]
  for i in range(individual_length):
    pop.append([random.randrange(1,m+1) for j in range(gene_length)])
  return pop


def get_fitness(indiv):
  fitness=0
  for a,b,c,d in l:
    a-=1
    b-=1
    if indiv[b]-indiv[a]==c:
      fitness+=d
  return fitness


def elite_selection(pop):
  pop.sort(reverse=True, key=lambda x:x[1])
  return pop[:elite_gene+1]


def two_point_crossover(parent1,parent2):
  r1=random.randint(0,gene_length-1)
  r2=random.randint(0,gene_length-1)
  child=deepcopy(parent1)
  child[r1:r2]=parent2[r1:r2]
  return child


pop=[[p,get_fitness(p)] for p in get_population()]
pop.sort(reverse=True,key=lambda x:x[1])

for g in range(generation):
  elites=elite_selection(pop)
  pop=elites
  while len(pop)<individual_length:
    if random.random()<individual_mutation:
      child=[random.randrange(1,m+1) for j in range(gene_length)]
    else:
      m1=random.randint(0,len(elites)-1)
      m2=random.randint(0,len(elites)-1)
      child=two_point_crossover(elites[m1][0],elites[m2][0])
    pop.append([child,get_fitness(child)])

    n_pop=[]
    for i in pop:
      if i not in n_pop:
        n_pop.append(i)
    pop=n_pop

  pop.sort(reverse=True,key=lambda x:x[1])

ans=pop[0][1]
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n,m,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(q)]

def dfs(nl):
  if len(nl)==n:
    global ans
    t_ans=0
    for a,b,c,d in l:
      a-=1
      b-=1
      if nl[b]-nl[a]==c:
        t_ans+=d
    ans=max(ans,t_ans)
    return

  for i in range(nl[-1], m+1):
        dfs(nl+[i])

ans=0
for i in range(1,m+1):
  dfs([i])

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

import bisect

def get_indexes(num):
  idx = -1
  idxs = []
  while idx != N-1:
    tmp_idx = S[idx+1:].find(str(num))
    if tmp_idx == -1:
      return idxs
    else:
      idx += tmp_idx+1
      idxs.append(idx)
  return idxs
      
N = int(input())
S = input()

ans = 0
S_idxs = []
for i in range(10):
  S_idxs.append(get_indexes(i))

used = set([])
for i in range(10):
  for ii in S_idxs[i]:
    for j in range(10):
      for jj in S_idxs[j]:
        for k in range(10):
          for kk in S_idxs[k]:
            if ii<jj and jj<kk and str(i)+str(j)+str(k) not in used:
              ans += 1
              used.add(str(i)+str(j)+str(k))
              #print(i,j,k,ii,jj,kk)
print(ans)
#print(S_idxs)

#print('*'*20)
#print(get_indexes(1))

### FIXED CODE ###

import bisect

def get_indexes(num):
  idx = -1
  idxs = []
  while idx != N-1:
    tmp_idx = S[idx+1:].find(str(num))
    if tmp_idx == -1:
      return idxs
    else:
      idx += tmp_idx+1
      idxs.append(idx)
  return idxs

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

ans = 0
S_idxs = []
for i in range(10):
  S_idxs.append(get_indexes(i))

for i in range(10):
  if S_idxs[i] == []:continue
  ii = min(S_idxs[i])
  for j in range(10):
    if S_idxs[j] == []:continue
    jj = max(S_idxs[j])
    for k in range(10):
      for kk in S_idxs[k]:
        if ii<kk and kk<jj:
          ans += 1
          break
          
print(ans)
#print(S_idxs)

#print('*'*20)
#print(get_indexes(1))
### BUGGY CODE ###

import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
ec = [0] * (N - 1)


def dfs(v, pc):
    colors = set()
    colors.add(pc)

    for idx, e in [x for x in enumerate(edge) if ec[x[0]] == 0 and v in x[1]]:
        for c in range(1, N):
            if c not in colors:
                ec[idx] = c
                colors.add(c)
                break

        nv = e[0] if e[1] == v else e[1]
        dfs(nv, c)


dfs(0, 0)
print(max(ec))
for c in ec:
    print(c)


### FIXED CODE ###

import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append((b - 1, i))
    edge[b - 1].append((a - 1, i))
ec = [0] * (N - 1)


def dfs(node, pc):
    color = 1

    for to, idx in edge[node]:
        if ec[idx] == 0:
            if color == pc:
                color += 1
            ec[idx] = color

            dfs(to, color)
            color += 1


dfs(0, -1)
print(max(ec))
for c in ec:
    print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

X,Y,Z,K = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse=True)
B = sorted(list(map(int,input().split())),reverse=True)
C = sorted(list(map(int,input().split())),reverse=True)

res = []

for a in A:
    for b in B:
        res.append(a+b)

res.sort(reverse=True)

res = res[:K]
ans = []

for ab in res:
    for c in C:
        ans.append(ab+c)
    
ans.sort(reverse=True)
ans = ans[:K]

for a in ans:
    print(a)

### FIXED CODE ###

import sys
input = sys.stdin.readline

X,Y,Z,K = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse=True)
B = sorted(list(map(int,input().split())),reverse=True)
C = sorted(list(map(int,input().split())),reverse=True)

res = []

for a in A:
    for b in B:
        res.append(a+b)

res.sort(reverse=True)

res = res[:K]
ans = []

for ab in res:
    for c in C:
        ans.append(ab+c)
    
ans.sort(reverse=True)
ans = ans[:K]

for a in ans:
    print(a)
### BUGGY CODE ###

import bisect

a, b, q = map(int, input().split())
s = sorted([int(input()) for _ in range(a)])
t = sorted([int(input()) for _ in range(b)])

for _ in range(q):
    x = int(input())
    s_i = bisect.bisect_left(s, x)
    t_i = bisect.bisect_left(t, x)

    s0, s1, t0, t1 = None, None, None, None
    ans = 10 ** 11
    if s_i > 0:
        s0 = x - s[s_i-1]
    if s_i < a:
        s1 = s[s_i] - x
    if t_i > 0:
        t0 = x - t[t_i-1]
    if t_i < b:
        t1 = t[t_i] - x

    if s0 is not None and t0 is not None:
        ans = min(ans, max(s0, t0))
    if s1 is not None and t1 is not None:
        ans = min(ans, max(s1, t1))
    if s0 is not None and t1 is not None:
        ans = min(ans, s0*2 + t1, t1*2 + s0)
    if s1 is not None and t0 is not None:
        ans = min(ans, s1*2 + t0, t0*2 + s1)

    print(ans)

### FIXED CODE ###

import bisect
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

a, b, q = map(int, input().split())
s = sorted([int(input()) for _ in range(a)])
t = sorted([int(input()) for _ in range(b)])

for _ in range(q):
    x = int(input())
    s_i = bisect.bisect_left(s, x)
    t_i = bisect.bisect_left(t, x)

    s0, s1, t0, t1 = None, None, None, None
    ans = 10 ** 11
    if s_i > 0:
        s0 = x - s[s_i-1]
    if s_i < a:
        s1 = s[s_i] - x
    if t_i > 0:
        t0 = x - t[t_i-1]
    if t_i < b:
        t1 = t[t_i] - x

    if s0 is not None and t0 is not None:
        ans = min(ans, max(s0, t0))
    if s1 is not None and t1 is not None:
        ans = min(ans, max(s1, t1))
    if s0 is not None and t1 is not None:
        ans = min(ans, s0*2 + t1, t1*2 + s0)
    if s1 is not None and t0 is not None:
        ans = min(ans, s1*2 + t0, t0*2 + s1)

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

X = input()
while True:
	i = X.find('ST')
	if i == -1:
		break
	else:
		X = X[:i] + X[i+2:]
print(len(X))

### FIXED CODE ###

X = input()
s,t = (0,0)
for i in range(len(X)):
	if X[i]=='S':
		s += 1
	else:
		if s==0:
			t += 1
		else:
			s -= 1
print(s+t)
### BUGGY CODE ###

import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    # pivots = [r + 1 for r in range(H - 1) if mask[r]]
    # blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    # blocks = blocks.reshape(len(pivots) + 1, W)
    blocks = np.zeros((sum(mask) + 1, W), dtype=int)
    block_id = 0
    for r in range(H - 1):
        blocks[block_id] += A[r]
        if mask[r]:
            block_id += 1
    blocks[block_id] += A[-1]

    if blocks.max() > K:
        continue

    n_vert_cut = 0
    n_block = blocks.shape[0]
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_vert_cut += 1
            sums = adds

    ans = min(ans, n_vert_cut + n_block - 1)

print(ans)


### FIXED CODE ###

import itertools

H, W, K = map(int, input().split())
A = [[int(x) for x in input()] for _ in range(H)]


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
A=list(map(int,input().split()))
while(m>0):
    A=sorted(A,reverse=True)
    if n>1:
        while(A[0]>=A[1]):
            A[0]=A[0]//2
            m-=1
    else:
        A[0]=A[0]//2
        m-=1
print(sum(A))

### FIXED CODE ###

from heapq import heappop,heappush,heapify
n,m=map(int,input().split())
A=list(map(int,input().split()))
A_m=list(map(lambda x: -x,A))
heapify(A_m)
pop=lambda: -heappop(A_m)
push=lambda x: heappush(A_m,-x)
for _ in range(m):
    x=pop()
    push(x//2)
print(-sum(A_m))