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

d = input().split()
N = int(d[0])
M = int(d[1])
d = input().split()
As = [int(num) for num in d]
As.sort()


def main():
    dic = {}
    lis = []
    for i in range(1, M+1):
        d = input().split()
        b = int(d[0])
        c = int(d[1])
        lis.append([c, b])
        dic[c] = b
    dic = sorted(dic.items(), key=lambda x:(-x[0], x[1]))
    lis = sorted(lis,key=lambda x:(-x[0], x[1]))
    count = 0
    asum = 0
    tmp = [0 for i in range(N)]
    for c, b in lis:
        for i in range(count, b+count):
            if i < N:
                tmp[i] = c
        count += b
    for i in range(N):
        if tmp[i] > As[i]:
            asum += tmp[i]
        else:
            asum += As[i]
    print(asum)
        

if __name__ == '__main__':
    main()





### FIXED CODE ###

d = input().split()
N = int(d[0])
M = int(d[1])
d = input().split()
As = [int(num) for num in d]
As.sort()


def main():
    lis = []
    for i in range(1, M+1):
        d = input().split()
        b = int(d[0])
        c = int(d[1])
        lis.append([c, b])
    lis = sorted(lis,key=lambda x:(-x[0], x[1]))
    count = 0
    asum = 0
    tmp = [0 for i in range(N)]
    for c, b in lis:
        if count < N:
            for i in range(count, b+count):
                if i < N:
                    tmp[i] = c
            count += b
    for i in range(N):
        if tmp[i] > As[i]:
            asum += tmp[i]
        else:
            asum += As[i]
    print(asum)
        

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

import sys

def solve():
    N = int(input())
    print("0" + "\n", flush = True)
    a = input()
    basis = -1
    if a == "Vacant": return 0
    elif a == "Male": basis = 0
    else: basis = 1
    low, high = 0, N
    while high - low > 1:
        mid = (low + high) // 2
        print(str(mid) + "\n", flush = True)
        a = input()
        if a == "Vacant": break
        else:
            b = (0 if a == "Male" else 1)
            if (mid - basis) % 2 != (basis ^ b):
                high = mid
            else:
                low = mid
                basis = b
    else:
        print(str(low) + "\n", flush = True)

    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###

N = int(input())

print(0, flush = True)
s = input()
if s == "Vacant": exit()
else:
    reference_state = s
    opposite_state = ("Male" if s == "Female" else "Female") 
    low, high = 0, N
    count = 1
    while count < 20:
        mid = (low + high)//2
        expected_state = (reference_state if mid % 2 == 0 else opposite_state)
        print(mid, flush = True)
        s = input()
        if s == "Vacant":
            break
        else:
            if s == expected_state: low = mid
            else: high = mid
            count += 1
### BUGGY CODE ###

while 1:
    try:
        n = input()
        c = 0
        ps = [False for i in range(n)]
        for i in xrange(2, n):
            ps[i] = True
        for i in xrange(2, int(n**0.5+1)):
            if ps[i]:
                for j in xrange(i**2, n, i):
                    ps[j] = False
            
        for i in xrange(n):
            if ps[i] is True:
                c += 1
        print c
    except EOFError:
        break

### FIXED CODE ###

n = 10**6
c = 0
ps = [False]*(n+1)
for i in xrange(2, n+1):
    if i%2 != 0 or i == 2:
        ps[i] = True
for i in xrange(2, int(n**0.5+1)):
    if ps[i]:
        for j in xrange(i**2, n+1, i):
            ps[j] = False

while 1:
    try:
        n = input()
        if n == 2: print 1
        else: print len([0 for i in xrange(2, n+1) if ps[i]])
    except EOFError:
        break
### BUGGY CODE ###

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

ans = 0
while True:
    minh = 100
    sub = 0
    for i in range(n):
        if h[i] != 0:
            break

    for fin in range(i, n):
        if h[fin] == 0:
            fin -= 1
            break
    for j in range(i,fin + 1):
        if minh > h[j]:
            minh = h[j]
            sub = j
    minus = h[sub]
    for k in range(i, fin + 1):
        h[k] -= minus
    ans += minus
    
    if h.count(0) == n:
        break

print(ans)

### FIXED CODE ###

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

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

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

# 入力
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]


array = [0]*(10**5+1)

for a in A:
    array[a] += 1

for bc in BC:
    b, c = bc
    array[c] += array[b]
    array[b] = 0

    total = 0
    for i in range(10 ** 5 + 1):
        total += i * array[i]
    print(total)


### FIXED CODE ###

# 入力
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]


array = [0]*(10**5+1)
total = sum(A)

for a in A:
    array[a] += 1

for bc in BC:
    b, c = bc
    total += c*array[b]-b*array[b]
    array[c] += array[b]
    array[b] = 0
    print(total)
### BUGGY CODE ###

import sys, scipy
import numpy as np
from scipy.sparse import csr_matrix, isspmatrix_csr, isspmatrix_csc, isspmatrix
from scipy.sparse.csgraph._shortest_path import shortest_path
n=int(input())

g=[[0]*n for _ in range(n)]
for _ in range(n-1):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    g[a][b]=c
    g[b][a]=c

G=csr_matrix(g)

q,k=map(int,input().split())
k-=1
d=shortest_path(G, method="D")

for _ in range(q):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    print(int(d[x][k]+d[k][y]))


### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
g=[[]for _ in range(n)]
for _ in range(n-1):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    g[a].append((b,c))
    g[b].append((a,c))


q,k=map(int,input().split())
k-=1

dist=[float("inf")]*n
dist[k]=0
def dfs(s):
    for v,c in g[s]:
        if dist[v]==float("inf"):
            dist[v]=dist[s]+c
            dfs(v)


dfs(k)

for _ in range(q):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    print(dist[x]+dist[y])
### BUGGY CODE ###

def gcd(a, b):
    if(a < b):
        a, b = b, a

    while b:
        a, b = b, a % b
    return a

def lcm(a,b):
    return a*b / gcd(a,b)

n = int(input())
a = list(map(int, input().split()))
nums = 1
for i in range(n):
    nums = lcm(nums, a[i])
ans = 0
for i in a:
    ans += (nums - 1) % i
print(int(ans))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
nums = a[0]
for num in a:
    if(nums % num != 0):
        nums *= num
ans = 0
nums -= 1
for i in a:
    ans += nums % i
print(ans)
### BUGGY CODE ###

n = int(input())
ls = [input() for o in range(n)]
a = [0 for j in range(len(set(ls)))]
ls.sort()
u = list(set(ls))
u.sort()
p = 0
for i in range(n):
    if i ==0:
        a[i] += 1
    else:
        if ls[i] == ls[i-1]:
            a[p] += 1
        else:
            p +=1
            a[p] +=1
t = max(a)
r = 0
for l in range(len(a)):
    if a[l] != t:
        u.remove(u[r])
    else:
        r +=1
[print(e) for e in u]


### FIXED CODE ###

import collections
n = int(input())
ls = [input() for i in range(n)]
c = collections.Counter(ls)
mx = max(c.values())
A = [e for e,j in c.items() if j == mx]
A.sort()
for p in A:
  print(p)
### BUGGY CODE ###

a, b, c, d, e, f = map(int, input().split())

w = 0
s = 0
ratio = 0

for i in range(31):
    for j in range(31):
        water = a*i + b*j
        for k in range(1501):
            l = 0
            hoge = 1024
            while hoge:
                nl = l+hoge
                sugar = k*c+nl*d
                if 0 < water and water*100 + sugar <= f and sugar <= water*e:
                    l = nl
                hoge //= 2
            sugar = k*c+nl*d
            if ratio <= sugar / (water*100+sugar):
                w = water*100
                s = sugar
                ratio = sugar / (water*100+sugar)

print("%d %d"%(w+s,s))


### FIXED CODE ###

a,b,c,d,e,f = map(int, input().split(' '))

w = 0
s = 0
ratio = 0

for i in range((f // (b*100))+1):
    for j in range(((f-(i*b*100))//(a*100))+1):
        if i == 0 and j == 0:
            continue
        smax = min(f-(j*a+i*b)*100,(j*a+i*b)*e)
        sm = 0
        for k in range((smax//d)+1):
            sm = max(sm, k*d+c*((smax-(k*d))//c))
        if ratio <= sm/((j*a+i*b)*100+sm):
            ratio = sm/((j*a+i*b)*100+sm)
            w = (j*a+i*b)*100
            s = sm


print("%i %i" %(w+s,s))
### BUGGY CODE ###

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

import copy

N = int(input())
A = [int(input()) for i in range(N)]

for i in range(N):
        TMP = copy.deepcopy(A)
        TMP.pop(i)
        print(max(TMP))



### FIXED CODE ###

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

import copy

N = int(input())
A = [int(input()) for i in range(N)]

Amax = max(A)
TMP = copy.deepcopy(A)
TMP.remove(Amax)
Amax2 = max(TMP)

for i in range(N):
        if A[i] == Amax:
                print(Amax2)
        else:
                print(Amax)
### BUGGY CODE ###

from functools import lru_cache
import sys 
sys.setrecursionlimit(2147483647)

N = int(input())
A = []
for i in range(0,N):
    A.append(list(map(int,input().split())))

@lru_cache(None)
def dfs(d,pre):
    if d>=N-1: return 0
    tmp = [0] 
    for idx,a in enumerate(A[d]):
        if idx != pre:
            res = dfs(d + 1,idx) + a 
            tmp.append(res)
    return max(tmp)

print(dfs(-1,-1))

### FIXED CODE ###

N = int(input())
A = []
for i in range(0,N):
    A.append(list(map(int,input().split())))

dp = [[0 for _ in range(3)] for _ in range(N)]
for i in range(N):
    for j in range(3):
        if i == 0:
            dp[i][j]= A[i][j]
        else:
            tmp = [0] 
            for k in range(3):
                if j !=k:
                    tmp.append(dp[i-1][k])
            dp[i][j] = max(tmp) + A[i][j]
print(max(dp[-1]))
### BUGGY CODE ###

H, W = map( int, input().split())
S = [ input() for _ in range(H)]
T = [ [1]*W for _ in range(H)]
Y = [ [1]*W for _ in range(H) ]
for i in range(H):
    now = 0
    cnt = 0
    for j in range(W):
        if S[i][j] == ".":
            cnt += 1
        else:
            for k in range(now, j):
                T[i][k] = cnt
            cnt = 0
            now = j+1
        if cnt > 0:
            for k in range(now, W):
                T[i][k] = cnt
            
for i in range(W):
    now = 0
    cnt = 0
    for j in range(H):
        if S[j][i] == ".":
            cnt += 1
        else:
            for k in range(now, j):
                Y[k][i] = cnt
            cnt = 0
            now = j+1
        if cnt > 0:
            for k in range(now, H):
                Y[k][i] = cnt

ans = 0
for i in range(H):
    for j in range(W):
        if ans < T[i][j] + Y[i][j]-1:
            ans = T[i][j] + Y[i][j]-1
print(ans)

### FIXED CODE ###

H, W = map( int, input().split())
S = [["#"]*(W+2)]+[ "#"+input()+"#" for _ in range(H)]+ [["#"]*(W+2)]
H += 2
W += 2
L = [[0]*(W+2) for _ in range(H+2)]
R = [[0]*(W+2) for _ in range(H+2)]
D = [[0]*(W+2) for _ in range(H+2)]
U = [[0]*(W+2) for _ in range(H+2)]
cnt = 0

for i in range(1,H-1):
    for j in range(W):
        if S[i][j] == "#":
            cnt = 0
        else:
            cnt += 1
            R[i][j] = cnt
            
for i in range(1,H-1):
    for j in range(W-1,-1,-1):
        if S[i][j] == "#":
            cnt = 0
        else:
            cnt += 1
            L[i][j] = cnt

for j in range(1,W-1):
    for i in range(H):
        if S[i][j] == "#":
            cnt = 0
        else:
            cnt += 1
            D[i][j] = cnt

for j in range(1,W-1):
    for i in range(H-1,-1,-1):
        if S[i][j] == "#":
            cnt = 0
        else:
            cnt += 1
            U[i][j] = cnt

ans = 0
for i in range(1,H-1):
    for j in range(1,W-1):
        if ans < L[i][j] + R[i][j] + U[i][j] + D[i][j]:
            ans =  L[i][j] + R[i][j] + U[i][j] + D[i][j]
print(ans-3)
### BUGGY CODE ###

from collections import deque

n,m = map(int,input().split())
g = [set() for _ in range(n+1)]
gg = [0]*(n+1)
for _ in range(n-1+m):
    a,b = map(int,input().split())
    g[a].add(b)
    gg[b] = 1
p = [-1]*(n+1)
q = deque()
for i in range(1,n+1):
  if gg[i] == 0:
    p[i] = 0
    q.append(i)
    break
while q:
  v = q.popleft()
  for x in g[v]:
    q.append(x)
    p[x] = v
for x in p[1:]:
  print(x)


### FIXED CODE ###

from collections import deque

n,m = map(int,input().split())
g = [set() for _ in range(n+1)]
gg = [0]*(n+1)
for _ in range(n-1+m):
    a,b = map(int,input().split())
    g[a].add(b)
    gg[b] += 1
p = [-1]*(n+1)
q = deque()
for i in range(1,n+1):
  if gg[i] == 0:
    p[i] = 0
    q.append(i)
    break
while q:
  v = q.popleft()
  for x in g[v]:
    gg[x] -= 1
    if gg[x] == 0:
      q.append(x)
      p[x] = v
for x in p[1:]:
  print(x)
### BUGGY CODE ###

N, M = map(int, input().split())
works = [list(map(int, input().split())) for _ in range(N)]
works.sort(key=lambda x:(-x[1], -x[0]))
days = [0] * (M+1)
ans = 0
for work in works:
  if work[0] > M:
    continue
  for day in range(work[0], M+1):
    if days[day] == 0:
      days[day] = 1
      ans += work[1]
      full = False
      break
print(ans)


### FIXED CODE ###

import heapq

MAX = 10**5+1
N, M = map(int, input().split())
works = [[] for _ in range(MAX)]
for _ in range(N):
  day, reward = map(int, input().split())
  works[day].append(reward)
hp = []
ans = 0
for day in range(1, M+1):
  if len(works[day]) > 0:
    for reward in works[day]:
      heapq.heappush(hp, -reward)
  if len(hp) > 0:
    ans += -heapq.heappop(hp)
print(ans)
### BUGGY CODE ###

from operator import or_


class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


def solve():
    N, Q = map(int, input().split())
    *c, = map(lambda x:{int(x)}, input().split())
    tree = SegTree(N, set(), or_)
    tree.set_list(c)
    for _ in range(Q):
        l, r = map(int, input().split())
        print(len(tree.get(l-1, r)))
    

solve()


### FIXED CODE ###

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [list(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(list(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


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

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

def discount(l):
  l[-1] = l[-1] // 2
  l.sort()

for i in range(M):
  discount(A)
  
print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(lambda x:int(x)*(-1), input().split()))
heapq.heapify(A)

for i in range(M):
  max_value = heapq.heappop(A)*(-1)
  heapq.heappush(A, (max_value//2)*(-1))
  
print((-1)*sum(A))
### BUGGY CODE ###

N = int(input())
A= [input() for i in range(N)]

normal = max(A)
maxindex = [i for i, x in enumerate(A) if x == max(A)]
A.remove(normal)
exception = max(A)

for i in range(N):
    if i in maxindex:
        print(exception)
    else:
        print(normal)

### FIXED CODE ###

N = int(input())
A=[int(input()) for i in range(N)]

normal = max(A)
hoge=sorted(A)
exception = hoge[-2]

for i in range(N):
    if A[i] == normal:
        print(exception)
    else:
        print(normal)
### BUGGY CODE ###

N = int(input())
S = input()
w = [0]*N
b = [0]*N

for i in range(N):
    b[i] = b[i-1]
    if S[i] == '#':
        b[i] += 1
    w[i] = w[i-1]
    if S[::-1][i] == '.':
        w[i] += 1

m = min(w[N-1],b[N-1])
for i in range(N-1):
    m = min(m,b[i]+w[N-i-2])

print(m)

### FIXED CODE ###

N = int(input())
S = input()
w = [0]*N
b = [0]*N
s = S[::-1]
for i in range(N):
    b[i] = b[i-1]
    if S[i] == '#':
        b[i] += 1
    w[i] = w[i-1]
    if s[i] == '.':
        w[i] += 1

m = min(w[N-1],b[N-1])
for i in range(N-1):
    m = min(m,b[i]+w[N-i-2])

print(m)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]*n

for i in range(1, n+1):
  b[i-1] = a.index(i)+1
  
  
print(*b)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
d=[0]*n
for i,val in enumerate(l):
  d[val-1]=i+1
print(*d)
### BUGGY CODE ###

n,t=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]

c=0
dif=0
for i in range(1,n):
    m=min(a[:i])
    if(dif<a[i]-m):
        c=1
        dif=a[i]-m
    elif(dif==a[i]-m):
        c+=1
print(c)
    



### FIXED CODE ###

n,t=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]

c=0
dif=0
m=a[0]
for i in range(1,n):
    if(m>a[i]):
        m=a[i]
    if(dif<a[i]-m):
        c=1
        dif=a[i]-m
    elif(dif==a[i]-m):
        c+=1
print(c)
### BUGGY CODE ###

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


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
result = 1
overflow = False
for i in a:
    result *= i
    if result > 1e18:
        result = 1
        overflow = True
if result != 0 and overflow:
    print(-1)
else:
    print(result)
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<p:break
   q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque()
now.append([x1-1,y1-1])
dp[x1-1][y1-1]=0
#kの更新が遅い
def bfs(d):
    global h,w,k,dp,now,x2,y2
    l=len(now)
    if l==0:
        return
    dp_sub=deque()
    cand=set()
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp_sub.append([x,y+j,d])
                #dp[x][y+j]=d
                cand.add((x,y+j))
                #now.append([x,y+j])
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub.append([x,y-j,d])
                #dp[x][y-j]=d
                cand.add((x,y-j))
                #now.append([x,y-j])
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub.append([x+j,y,d])
                #dp[x+j][y]=d
                cand.add((x+j,y))
                #now.append([x+j,y])
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub.append([x-j,y,d])
                #dp[x-j][y]=d
                cand.add((x-j,y))
                #now.append([x-j,y])
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now.append(i)
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from bisect import bisect_left, bisect_right

def main():
    N,C,K = map(int, input().split())
    Ti = list(int(input()) for _ in range(N))
    Ti.sort()
    ret = 0
#    print(Ti)
    while len(Ti)>0:
        Tto = K + Ti[0]
        Ti = Ti[min(C,bisect_right(Ti, Tto)):]
        ret += 1
#        print(Ti)
    print(ret)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from bisect import bisect_left, bisect_right

def main():
    N,C,K = map(int, input().split())
    Ti = list(int(input()) for _ in range(N))
    Ti.sort()
    i = 0
    ret = 0
    while i<N:
        ret += 1
        s = i
        Ts = Ti[i]
        while i<N and Ti[i]<=(Ts+K) and (i-s)<C:
            i += 1

    print(ret)

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

import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
sm=0
for i in range(n):
  b1=bisect.bisect_left(b,a[i]+1)
  for j in range(b1,n):
    sm+=n-bisect.bisect_left(c,b[j]+1)
print(sm)
  

### FIXED CODE ###

import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
sm=0
for i in range(n):
  b1=bisect.bisect_left(a,b[i])
  c1=n-bisect.bisect_left(c,b[i]+1)
  sm+=b1*c1
print(sm)
### BUGGY CODE ###

n = int(input())
nums = [int(e) for e in input().split()]
import numpy as np
npnums = np.array(nums)

cnt = 0 #個数のカウント

for i in nums:
    if np.count_nonzero(i % npnums == 0) > 1:
        cnt +=1
    else:
        continue
print(n-cnt)

### FIXED CODE ###

n = int(input())
nums = [int(e) for e in input().split()]
import numpy as np

ans= np.zeros(max(nums)+1)

for i in nums:
    if ans[i] >1:
        continue
    else:
        ans[i::i] +=1

cnt = 0
for i in nums:
    if ans[i] ==1:
        cnt +=1

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

# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque
inf = 10 ** 15
mod = 10 ** 9 + 7
s = input()
n = len(s)
# 区間DP ダルマ落とし
dp = [[0 for j in range(n)]for i in range(n)] # iからjまで崩せる最大値 (0オリジン)
for k in range(1,n):  # 区間長1からn-1
    for i in range(0,n-k):  # i が区間の始まり   i+k が区間の終わり
        # 両端が揃ったら消せる かつ 間が全部消えるなら
        if s[i] == 'S' and s[i+k] == 'T' and dp[i+1][i+k-1] == k-1:
            dp[i][i+k] = dp[i+1][i+k-1] + 2
        else:
            # i+j が区間を区切るところ(i+jは左側に含まれる)  | i ~ i+j  |  i+j+1 ~ i+k | で考えてる。
            # 今回は今回はダルマを崩す順番の問題
            for j in range(k):
                dp[i][i+k] = max(dp[i][i+k], dp[i][i+j] + dp[i+j+1][i+k])
print(n-dp[0][n-1])

### FIXED CODE ###

# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque
inf = 10 ** 15
mod = 10 ** 9 + 7
s = input()
n = len(s)
stack = []
for c in s:
    if c == 'S':
        stack.append(c)
    if c == 'T':
        if stack:
            if stack.pop() == 'T':
                stack.append('T')
                stack.append(c)
        else:
            stack.append(c)
print(len(stack))