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

import sys,queue,math,copy,itertools,bisect,collections
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

N,M = LI()
data = [LI() for _ in range(N)]
dp = [0] * (M+1)

data.sort(key=lambda x:x[1], reverse=True)
for a,b in data:
    for i in range(M-a,-1,-1):
        if b > dp[i]:
            dp[i] = b
            break
print(sum(dp))

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

N,M = LI()
data = [LI() for _ in range(N)]
dp = [0] * (M+1)
data.sort(key=lambda x:x[1], reverse=True)

N0 = 2 ** M.bit_length()
seg = [0] * (2*N0)

def seg_set(i,x):
    i = i + N0- 1
    seg[i] = x
    while i > 0:
        i = (i-1) // 2
        seg[i] = max(seg[i*2+1],seg[i*2+2])

def seg_query(i):
    i = i + N0 - 1
    ret = seg[i]
    while i ^ (i+1) < i+1:
        i = (i-2) // 2
        ret = max(ret,seg[i])
    return ret

for i in range(M+1):
    seg_set(i,i)

for a,b in data:
    if a <= M:
        i = seg_query(M-a+1)
        if i > 0:
            dp[i] = b
            seg_set(i,0)
print(sum(dp))
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
import copy
from itertools import combinations


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

li = list(combinations(l, 2))


ans = 0
for i in li:
    x = copy.deepcopy(l)
    x.remove(i[0])
    x.remove(i[1])
    left = abs(i[0] - i[1])
    right = min(i[0], i[1])

    left_div = bisect_left(x, left+1)
    right_div = bisect_right(x, right-1)
    ans += max(0, right_div - left_div)

print(ans)

### FIXED CODE ###

from bisect import bisect_left
import copy

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


ans = 0
for small in range(n - 2):
    for mid in range(small + 1, n - 1):
        div = bisect_left(l, l[small] + l[mid], 0, n)
        if div > mid + 1:
            ans += div - mid - 1

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

from collections import defaultdict

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

s = input()

def fact(n):
  ans = 1
  for i in range(2,n+1):
    ans*=i
  return ans

m = max(s.count("B"),s.count("W"))
print(fact(m))

### FIXED CODE ###

from collections import defaultdict

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

s = input()

ans = 0
bCount = 0
for i in s:
  if i=="B":
    bCount += 1
  else:
    ans+=bCount
print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 1

for i in A:
    ans *= i
if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 1

if 0 in A:
    ans = 0
else:
    for i in A:
        ans *= i
        if ans >10**18:
            ans = -1
            break
        
print(ans)
### BUGGY CODE ###

import numpy as np
# dp[i][j]: i+1個目までの品物で重量の総和がj以下である時の価値の最大値

N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    tmp = list(map(int, input().split()))
    w.append(tmp[0])
    v.append(tmp[1])
    
dp = np.zeros(shape=(N+1, W+1), dtype=int)
for i in range(N):
    for j in range(W+1):
        if w[i] <= j:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
        else:
            #dp[i+1][j] = max(dp[i][j], dp[i+1][j])
            dp[i+1][j] = dp[i][j]
print(dp[N][W])

### FIXED CODE ###

# pypyはnumpyが使えないみたい
#import numpy as np
# dp[i][j]: i+1個目までの品物で重量の総和がj以下である時の価値の最大値

N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    tmp = list(map(int, input().split()))
    w.append(tmp[0])
    v.append(tmp[1])
    
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if w[i] <= j:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
        else:
            #dp[i+1][j] = max(dp[i][j], dp[i+1][j])
            dp[i+1][j] = dp[i][j]
print(dp[N][W])
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline())
S = sys.stdin.readline().strip()

ans = 0
for L in range(1, N):
	dp = [0]*N 
	for x in range(N - L):
		if S[x] == S[x+L]:
			if x==0: dp[x] += 1
			else: dp[x] = min(dp[x-1]+1, L)
			ans = max(ans, dp[x])
print(ans)

### FIXED CODE ###

import sys

N = int(sys.stdin.readline())
S = sys.stdin.readline().strip()

ans = 0
for L in range(1, N):
	dp = [0]*N 
	for x in range(N - L):
		if S[x] == S[x+L]:
			if x==0: dp[x] += 1
			else: dp[x] = min(dp[x-1]+1, L)
			ans = max(ans, dp[x])
print(ans)
### BUGGY CODE ###

S = list(input())
ans = 0

while True:
    count = 0
    for i in range(0, len(S)-1):
        if S[i] == "B" and S[i+1] == "W":
            count += 1
            S[i] = "W"
            S[i+1] = "B"
    if count > 0:
        ans += count
    else:
        print(ans)
        exit()

### FIXED CODE ###

S = input()
ans = 0
count = [0] * len(S)
tmp = 0
for i in reversed(range(len(S))):
    if S[i] == "B":
        count[i] = tmp
    else:
        tmp += 1

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

n = int(input())
s = input()
dp = [[0]*(n) for _ in range(n)]

for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if i == n-1 or j == n-1:
            if s[i] == s[j]:
                dp[i][j] += 1
            continue

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

ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        ans = max(ans, min(abs(j-i), dp[i][j]))
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
dp = [[0]*(n) for _ in range(n)]

for i in range(n-1, -1, -1):
    for j in range(i-1, -1, -1):
        if i == (n-1):
            if s[i] == s[j]:
                dp[i][j] += 1
            continue

        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1        

ans = 0
for i in range(n-1, -1, -1):
    for j in range(i, -1, -1):
        ans = max(ans, min(abs(j-i), dp[i][j]))
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = []
for i in range(n):
  if i%2==0:
    ans.append(a[i])
  else:
    ans.insert(0,a[i])
if n%2!=0:
  ans = ans[::-1]
print(*ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = []
if n%2==0:
  front = a[::2]
  back = a[1::2][::-1]
else:
  front = a[1::2]
  back = a[::2][::-1]
ans = back+front
print(*ans)
### BUGGY CODE ###

n = int(raw_input())
R = []
for i in xrange(n):
    L = raw_input().split()
    order = L[0]
    value = 0
    if len(L) > 1:
        value = int(L[1])
    if order == 'insert':
        R.insert(0, value)
    if order == 'delete' and value in R:
        R.remove(value)
    if order == 'deleteFirst':
        R.pop(0)
    if order == 'deleteLast':
        R.pop()
print ' '.join(map(str, R))

### FIXED CODE ###

from collections import deque
n = int(raw_input())
R = deque()
for i in xrange(n):
    L = raw_input().split()
    order = L[0]
    value = 0
    if len(L) > 1:
        value = int(L[1])
    if order == 'insert':
        R.appendleft(value)
    if order == 'delete' and value in R:
        R.remove(value)
    if order == 'deleteFirst':
        R.popleft()
    if order == 'deleteLast':
        R.pop()
print ' '.join(map(str, R))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
town = [[] for _ in range(N)]
for i in range(Q):
    place, year = map(int, input().split())
    tmp = [0,0]
    tmp[0] = year
    tmp[1] = i
    town[place-1].append(tmp)

# print(town)

ans = []

for item in town:
    index = town.index(item)
    # print(item)
    item.sort()
    index += 1
    index = str(index)
    while len(index) < 6:
        index = '0' + index
    for i in range(len(item)):
        num = i + 1
        num = str(num)
        while len(num) < 6:
            num = '0' + num
        xxx = index + num
        tmp = []
        tmp.append(item[i][1])
        tmp.append(xxx)
        ans.append(tmp)

ans.sort()
for item in ans:
    print(item[1])


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
town = [[] for _ in range(N)]
for i in range(Q):
    place, year = map(int, input().split())
    town[place-1].append([year,i])

# print(town)

ans = []
k = 0
for item in town:
    index = k
    # index = town.index(item)
    # print(item)
    item.sort()
    index = str(index+1)
    while len(index) < 6:
        index = '0' + index
    for i in range(len(item)):
        num = str(i+1)
        while len(num) < 6:
            num = '0' + num
        xxx = index + num
        ans.append([item[i][1],xxx])
    k += 1

ans.sort()
for item in ans:
    print(item[1])
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 10 ** 10
for i in range(1, N):
    ans = min(ans, abs(sum(a[:i]) - sum(a[i:])))

print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 10 ** 10
total = sum(a)
tmp = 0
for i in range(N - 1):
    tmp += a[i]
    ans = min(ans, abs(total - (2 * tmp)))

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

from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

s = stdin.readline().rstrip()
k = int(stdin.readline().rstrip())

finish = set()
S = len(s)

for i in range(S):
    for j in range(i+1,S+1):
        finish.add(s[i:j])

finish = list(finish)
finish.sort()

print(finish[k-1])

### FIXED CODE ###

from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

s = stdin.readline().rstrip()
k = int(stdin.readline().rstrip())


finish = set()
S = len(s)

for i in range(S):
    for j in range(1,6):
        finish.add(s[i:i+j])

finish = list(finish)
finish.sort()

print(finish[k-1])
### BUGGY CODE ###

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

diffMax = 2 * max(heights)
diffMin = 2 * min(heights)

cnt = 0

for i in range(diffMin, max([diffMax, n]) + 1):
    for j in range(n - i):
        if (heights[j] + heights[j + i]) == i:
            cnt += 1
print(cnt)

### FIXED CODE ###

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

diffMax = 2 * max(heights)
diffMin = 2 * min(heights)

cnt = 0

arrSize = min([max([i + heights[i] for i in range(len(heights))]),max([i - heights[i] for i in range(len(heights))])]) + 1

seppenPlus = [0] * arrSize
seppenMinus = [0] * arrSize


for i in range(len(heights)):
    seppenPlusNum = i + heights[i]
    seppenMinusNum = i - heights[i]

    if seppenPlusNum < arrSize:
    	seppenPlus[seppenPlusNum] += 1

    if seppenMinusNum >= 0:
        seppenMinus[seppenMinusNum] += 1

for i in range(len(seppenPlus)):
    cnt += seppenPlus[i] * seppenMinus[i]

print(cnt)
### BUGGY CODE ###

import sys
import math
X,Y = (int(x) for x in input().split())

if (X+Y) % 3 != 0:
  print(0)
  sys.exit()
  
n = (2*Y-X) / 3
m = (2*X-Y) / 3
if n < 0 or m < 0:
  print(0)
  sys.exit()
  
print(math.factorial(n+m) // (math.factorial(m) * math.factorial(n)))

### FIXED CODE ###

import sys

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

X,Y = (int(x) for x in input().split())

if (X+Y) % 3 != 0:
  print(0)
  sys.exit()

if (2*Y-X) % 3 == 0:
  n = (2*Y-X) // 3  
else:
  n = -1

if (2*X-Y) % 3 == 0:
  m = (2*X-Y) // 3
else:
  m = -1

if n < 0 or m < 0:
  print(0)
  sys.exit()
print(int(cmb(n+m,n)) % (10**9 +7))
### BUGGY CODE ###

import collections
n = int(input())
#h  = list(map(int, input().split()))
#h, w = list(map(int, input().split()))

#j-i=k-jではない 2j=k+i i=2j-k

s = input()
count = 0

"""
for i in range(n):
    for j in range(i+1, n):
        if s[i]!=s[j]:    
            for k in range(j+1, n):
                if j-i!=k-j:
                    if s[i]!=s[k] and s[j]!=s[k]:
                        count += 1
"""
for i in range(n):
    a = s[i:]
    if s[i]=="R":
        point = a.count("G")*a.count("B")
    elif s[i]=="G":
        point = a.count("R")*a.count("B")
    else:
        point = a.count("R")*a.count("G")
    count += point

#j-i=k-jではない 2j=k+i i=2j-k
#rgb

kom = 0
for i in range(n):
    for j in range(i+1, n):
        if 2*j-i < n:
            if s[i]!=s[j] and s[i]!=s[2*j-i] and s[j]!=s[2*j-i]:
                kom += 1


print(count-kom)





### FIXED CODE ###

n = int(input())
#h  = list(map(int, input().split()))
#h, w = list(map(int, input().split()))

#j-i=k-jではない 2j=k+i i=2j-k

s = input()
count = 0

"""
for i in range(n):
    for j in range(i+1, n):
        if s[i]!=s[j]:    
            for k in range(j+1, n):
                if j-i!=k-j:
                    if s[i]!=s[k] and s[j]!=s[k]:
                        count += 1
"""
for i in range(n):
    a = s[i:]
    if s[i]=="R":
        point = a.count("G")*a.count("B")
    elif s[i]=="G":
        point = a.count("R")*a.count("B")
    else:
        point = a.count("R")*a.count("G")
    count += point

#j-i=k-jではない 2j=k+i i=2j-k
#rgb

kom = 0
for i in range(n):
    for j in range(i+1, n):
        if 2*j-i < n:
            if s[i]!=s[j] and s[i]!=s[2*j-i] and s[j]!=s[2*j-i]:
                kom += 1


print(count-kom)
### BUGGY CODE ###

from fractions import gcd
from itertools import combinations
from functools import reduce


def calc_gcd(nums):
    return reduce(gcd, nums)


def main(input_1, input_2):
    nums_list = list(map(list, list(combinations(input_2, len(input_2)-1))))

    gcd_list = []
    for nums in nums_list:
        calced = calc_gcd(nums)
        gcd_list.append(calced)

    return max(gcd_list)


if __name__ == "__main__":
    input_1 = input()
    input_2 = list(map(int, input().split()))
    print(main(input_1, input_2))


### FIXED CODE ###

from fractions import gcd


def main(input_1, input_2):
    left = [0] * (input_1+1)
    for i in range(input_1):
        left[i+1] = gcd(left[i], input_2[i])

    right = [0] * (input_1 + 1)
    i = input_1 - 1
    while i >= 0:
        right[i] = gcd(right[i+1], input_2[i])
        i -= 1

    while i >= 0:
        right[i] = gcd(right[i+1], input_2[i])

    res = 0
    for i in range(input_1):
        l = left[i]
        r = right[i+1]
        gcd_val = gcd(l, r)
        if gcd_val > res:
            res = gcd_val

    return res


if __name__ == "__main__":
    input_1 = int(input())
    input_2 = list(map(int, input().split()))
    print(main(input_1, input_2))
### BUGGY CODE ###

N, K, Q = map(int,input().split())
scores = [K] * N

def minus(ans_i):
    for i in range(N):
        scores[i] -= 1
    scores[ans_i-1] += 1

for i in range(Q):
    ans_i = int(input())
    minus(ans_i)    

for player in scores:
    if player <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

N, K, Q = map(int,input().split())
scores = [0] * N

for i in range(Q):
    ans_i = int(input())
    scores[ans_i-1] += 1    

for i in range(N):
    final_res = K - (Q - scores[i])  
    if final_res <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

# F

N = int(input())

import bisect
list_plus = []
list_minus = []
for i in range(N):
    S = input()
    state = 0
    min_state = 0
    for s in S:
        if s == '(':
            state += 1
        else:
            state -= 1
        min_state = min(min_state, state)
    
    if state > 0:
        index = bisect.bisect_right(list_plus, [min_state, state])
        list_plus.insert(index, [min_state, state])
        # list_plus.append([min_state, state])
    else:
        index = bisect.bisect_right(list_minus, [min_state - state, -state])
        list_minus.insert(index, [min_state - state, -state])
        # list_minus.append([min_state - state, -state])

def compute(arr):
    total_state = 0

    for min_state, state in arr[-1::-1]:
        if total_state + min_state < 0:
            print('No')
            exit()
        total_state += state
    return total_state

total_state_plus = compute(list_plus)
total_state_minus = compute(list_minus)

print('Yes' if total_state_plus == total_state_minus else 'No')

### FIXED CODE ###

# F

N = int(input())

list_plus = []
list_minus = []
for i in range(N):
    S = input()
    state = 0
    min_state = 0
    for s in S:
        if s == '(':
            state += 1
        else:
            state -= 1
        min_state = min(min_state, state)
    
    if state > 0:
        list_plus.append((min_state, state))
    else:
        list_minus.append((min_state - state, -state))

def compute(arr):
    total_state = 0
    for min_state, state in arr[::-1]:
        if total_state + min_state < 0:
            print('No')
            exit()
        total_state += state
    return total_state

list_plus.sort()
total_state_plus = compute(list_plus)
list_minus.sort()
total_state_minus = compute(list_minus)

print('Yes' if total_state_plus == total_state_minus else 'No')
### BUGGY CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
m=0
S=0
t=0
x=0

for i in range(N-K+1):
  for k in range(K):
    S+=p[i+k]
    if (i+k)==(i+K-1):
      if m<S:
        m=S
        t=i
      S=0

for a in range(K):
  x+=(1+p[t+a])/2

print(x)
  
      

### FIXED CODE ###

def main():
    """"ここに今までのコード"""
import sys
input = sys.stdin.readline

N,K=map(int,input().split())
p=list(map(int,input().split()))
t=0
k=sum(p[0:K])

if N==K:
  print((k+K)/2)
else:
  for i in range(N-K):
    k-=p[i]
    k+=p[i+K]
    if k>t:
      t=k
    
  print((K+t)/2)

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

num = int(input())
flag_list = [int(i) for i in input().split()]


ans = 0
cont_game = True

while cont_game:
    no_change = 0
    for i in range(num):
        if flag_list[i] % 2 == 0:
            flag_list[i] //= 2
            break
        else:
            no_change += 1
            pass

    if no_change == num:
        break
    ans += 1

print(ans)

### FIXED CODE ###

num = int(input())
flag_list = [int(i) for i in input().split()]


ans = 0
cont_game = True

for val in flag_list:
    while val % 2 == 0:
        val //= 2
        ans += 1

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

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])%mod

    return result





n, k = map(int, input().split())
a=list(map(int, input().split()))
a.sort()
mod=10**9+7
min=0
max=0
for i in range(n-k+1):
    x=cmb(n-i-1,k-1)
    min+=a[i]*x
    max+=a[n-1-i]*x
    min%=mod
    max%=mod

ans=max-min


print(ans%mod)

### FIXED CODE ###

def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r=min(r,n-r)

    return g1[n] * g2[r] * g2[n - r] % mod


mod = 10 ** 9 + 7  # 出力の制限
N = 10 ** 5
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod =10**9+7
mi = 0
ma = 0
for i in range(n - k + 1):
    x = cmb(n - i - 1, k - 1, mod)
    mi += a[i] * x
    ma += a[n - 1 - i] * x
    mi %= mod
    ma %= mod

ans = ma - mi

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

import sys
N, M = map(int, sys.stdin.readline().split())
a_list = list(map(int, sys.stdin.readline().split()))
items = []
for i in range(M):
    items.append(tuple(map(int, sys.stdin.readline().split())))

ans = 0
import heapq

heapq.heapify(a_list)

for i in range(M):
    b, c = items[i]
    while b >= 1:
        q = heapq.heappop(a_list)
        if c > q:
            heapq.heappush(a_list, c)
        else:
            heapq.heappush(a_list, q)
            break
        b -= 1
print(sum(a_list))


### FIXED CODE ###

import sys

N, M = map(int, sys.stdin.readline().split())
a_list = list(map(int, sys.stdin.readline().split()))
items = []
for i in range(M):
    items.append(tuple(map(int, sys.stdin.readline().split())))


from collections import defaultdict

tar = defaultdict(int)
for a in a_list:
    tar[a] += 1

for i in range(M):
    b, c = items[i]
    tar[c] += b

tar = sorted(tar.items(), key=lambda x: -x[0])

cnt = 0
ans = 0
for k, v in tar:
    if cnt + v <= N:
        cnt +=v
        ans += k*v
    else:
        ans += k*(N-cnt)
        cnt = N
    if cnt >= N:
        break
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
S = [x for x in S]

s = len(S)
e = 0
while s != e:
  s = len(S)
  for i in range(len(S)-1):
    if i >= len(S)-1:break
    if S[i] == S[i+1]:S.pop(i)
    e = len(S)

print(len(S))


### FIXED CODE ###

N = int(input())
S = [x for x in input()]

def p(S):
  s = len(S)
  e = 0
  cnt = 0
  while s != e:
    cnt += 1
    if cnt > N:break
    s = len(S)
    for i in range(s-1):
      if i >= len(S)-1:break
      if S[i] == S[i+1]:S.pop(i)
      e = len(S)
  return len(S)

print(p(S))
### BUGGY CODE ###

N=int(input())
A=[int(i) for i in input().split()]
D={}
x=0
lis=[]
for a in A:
	if a in D.keys():
		D[a]=D[a]+((D[a]*2)**0.5//1)+1
	else:
		D[a]=0

z=sum(D.values())
for i in range(len(A)):
	x=0
	y=((D[A[i]]*2)**0.5)//1
	x=x+z-y
	print(int(x))


### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
D={}
x=0
lis=[]
for a in A:
	try:
		D[a]=D[a]+((D[a]*2)**0.5//1)+1
	except:
		D[a]=0

z=sum(D.values())
for i in range(len(A)):
	x=0
	y=((D[A[i]]*2)**0.5)//1
	x=x+z-y
	print(int(x))
### BUGGY CODE ###

from math import floor
a,b,n = map(int,input().split())
ans=0
for i in range(n+1):
    ans = max(ans, floor(a*i/b)-a*floor(i/b))
print(ans)

### FIXED CODE ###

from math import floor
a,b,n = map(int,input().split())
x=min(b-1,n)
print(floor(a*x/b)-a*floor(x/b))
### BUGGY CODE ###

s=list(input())+["G"]*2
n=0
while s[n+1]!="G":
    if s[n]+s[n+1]=="ST":
        del s[n]
        del s[n]
        if n!=0: n-=1
    else:
        n +=1
print(len(s)-2)

### FIXED CODE ###

from collections import deque
s=list(input())
A=deque([])
for i in s:
    if i=="S":A.append(i)
    elif i=="T":
        if len(A)==0 or A[-1]=="T":A.append(i)
        else:A.pop()
print(len(A))