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

def main():
    import sys
    input = sys.stdin.readline
    from bisect import bisect_left,bisect
    
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    S = [list(map(int, input().split())) for i in range(M)]
    A.sort()
    A = A[::-1]
    S = sorted(S, key=lambda x: x[1])[::-1]
    
    T = []
    count = 0
    
    for i in range(M):
        T += [S[i][1]]*S[i][0]
        count += S[i][0]
    
    a = 0
    t = 0
    SUM = 0
    for _ in range(N):
        if t >= count:
            SUM += A[a]
            a += 1
        elif A[a] > T[t]:
            SUM += A[a]
            a += 1
        else:
            SUM += T[t]
            t += 1
    print(SUM)
    
    

main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from bisect import bisect_left,bisect
    
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    S = [list(map(int, input().split())) for i in range(M)]
    A.sort()
    A = A[::-1]
    S = sorted(S, key=lambda x: x[1])[::-1]
    
    T = []
    count = 0
    
    for i in range(M):
        T += [S[i][1]]*S[i][0]
        count += S[i][0]
        if count >= N:
            break
    
    a = 0
    t = 0
    SUM = 0
    for _ in range(N):
        if t >= count:
            SUM += A[a]
            a += 1
        elif A[a] > T[t]:
            SUM += A[a]
            a += 1
        else:
            SUM += T[t]
            t += 1
    print(SUM)
    
    

main()
### BUGGY CODE ###

S = input()
N = len(S)
sosu = 10 ** 9 + 7
dp = [[0 for i in range(13)] for j in range(N)]
amari = [0 for i in range(N)]
if S[0] == '?':
    for k in range(10):
        amari =  k * (10 ** (N-1) % 13) % 13
        dp[0][amari] += 1
else:
    amari = int(S[0]) * (10 ** (N-1) % 13) % 13
    dp[0][amari] = 1
#print(dp)
for j in range(1,N):
    if S[j] == '?':
        for k in range(10):
            amari = k * (10 ** (N-j-1) % 13) % 13
            for i in range(13):
                if i >= amari:
                    dp[j][i] += dp[j - 1][i - amari]
                    dp[j][i] = dp[j][i] % sosu
                else:
                    dp[j][i] += dp[j - 1][i + 13 - amari]
                    dp[j][i] = dp[j][i] % sosu
    else:
        amari = int(S[j]) * (10 ** (N-j-1) % 13) % 13
        for i in range(13):
            if i >= amari:
                dp[j][i] = dp[j-1][i-amari]
            else:
                dp[j][i] = dp[j-1][i + 13 - amari]
print(dp[N-1][5])

### FIXED CODE ###

S = input()
N = len(S)
sosu = 10 ** 9 + 7
dp = [[0 for i in range(13)] for j in range(N)]
j = 0
if S[j] == '?':
    flag = -1
else:
    flag = int(S[j])
if flag == -1:
    for i in range(10):
        dp[j][i] += 1
else:
    dp[j][flag] = 1
#print(dp)
for j in range(1, N):
    if S[j] == '?':
        flag = -1
    else:
        flag = int(S[j])
    for k in range(10):
        if flag == -1:
            for i in range(13):
                dp[j][(i * 10 + k) % 13] += dp[j - 1][i]
            for i in range(13):
                dp[j][i] = dp[j][i] % sosu
        else:
            for i in range(13):
                dp[j][(i * 10 + flag) % 13] = dp[j-1][i]
 
print(dp[N-1][5])
### BUGGY CODE ###

from collections import Counter

N = int(input())
D = [int(i) for i in input().split()]
M = int(input())
T = [int(i) for i in input().split()]

d = Counter(D)
t = Counter(T)
d_key = d.keys()
t_key = t.keys()

for i in t_key:
    if i not in d_key or t[i] > d[i]:
        print('NO')
        exit()

print('YES')


### FIXED CODE ###

from collections import Counter

N = int(input())
D = [int(i) for i in input().split()]
M = int(input())
T = [int(i) for i in input().split()]

d = Counter(D)
t = Counter(T)
d_key = list(d.keys())
t_key = list(t.keys())

p = len(d_key)
d_key += t_key
q = set(d_key)

if p != len(q):
    print('NO')
    exit()

for i in t_key:
    if t[i] > d[i]:
        print('NO')
        exit()

print('YES')
### BUGGY CODE ###

import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class SegmentTree:
    def __init__(self, S):
        N = len(S)
        d = N.bit_length()
        T = [set() for _ in range(2 ** (d + 1) - 1)]
        for i, s in enumerate(S):
            T[i + 2 ** d - 1].add(s)
        for i in range(2 ** d - 2, -1, -1):
            T[i] = T[2 * i + 1].union(T[2 * i + 2])
        self.d = d
        self.T = T

    def update(self, i, a):
            i = i + 2 ** self.d - 1
            while i > 0:
                i = (i - 1) // 2
                self.T[i] = self.T[2 * i + 1].union(self.T[2 * i + 2])
    
    def query(self, a, b):
        return self._query(a, b, 0, 0, 2 ** self.d)

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return set()

        if a <= l and r <= b:
            return self.T[k]
        else:
            s1 = self._query(a, b, 2 * k + 1, l, (l + r) // 2)
            s2 = self._query(a, b, 2 * k + 2, (l + r) // 2, r)
            return s1.union(s2)


def main():
    N, Q = read_values()
    C = read_list()

    ST = SegmentTree(C)
    for _ in range(Q):
        a, b = read_index()
        print(len(ST.query(a, b + 1)))




if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class BIT:
    def __init__(self, N):
        self.N = N
        self.T = [0] * (N + 1)

    def add(self, i, x):
        i += 1
        while i <= self.N:
            self.T[i] += x
            i += i & -i

    def _sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.T[i]
            i -= i & -i
        return s

    def sum(self, i, j):
        si = self._sum(i - 1)
        sj = self._sum(j)
        return sj - si
    

def main():
    N, M = read_values()
    C = read_list()
    Q = []
    for i in range(M):
        l, r = read_index()
        Q.append((l, r, i))
    Q.sort(key=lambda a: a[1])

    ans = [0] * M
    T = [-1] * M
    bit = BIT(N)
    q = 0
    # print(Q)
    for i in range(N):
        c = C[i] - 1
        t = T[c]
        if t != -1:
            bit.add(t, -1)
        T[c] = i
        bit.add(i, 1)

        # print(i, T, bit.T)
        while q < len(Q) and i == Q[q][1]:
            l, r, k = Q[q]
            ans[k] = bit.sum(l, r)
            q += 1

    print("\n".join(map(str, ans))) 

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

N = int(input())
S = input()
ans = 0
for i in range(N-2):
    a = S[i]
    for j in range(i+1,N-1):
        b = S[j]
        if a != b:
            if a != 'R' and b != 'R':
                ans += S[j+1:].count('R')
                if 2*j-i < N and S[j+j-i] == 'R':
                    ans -= 1
            if a != 'G' and b != 'G':
                ans += S[j+1:].count('G')
                if 2*j-i < N and S[j+j-i] == 'G':
                    ans -= 1
            if a != 'B' and b != 'B':
                ans += S[j+1:].count('B')
                if 2*j-i < N and S[j+j-i] == 'B':
                    ans -= 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
count = [[0 for i in range(N)] for j in range(3)]
for i in range(N):
    if S[i] == 'R':
        count[0][i] = 1
    if S[i] == 'G':
        count[1][i] = 1
    if S[i] == 'B':
        count[2][i] = 1
for i in range(3):
    for j in range(N-1,0,-1):
        count[i][j-1] += count[i][j]
for i in range(N-2):
    a = S[i]
    for j in range(i+1,N-1):
        b = S[j]
        if a != b:
            if a != 'R' and b != 'R':
                ans += count[0][j]
                if 2*j-i < N and S[j+j-i] == 'R':
                    ans -= 1
            if a != 'G' and b != 'G':
                ans += count[1][j]
                if 2*j-i < N and S[j+j-i] == 'G':
                    ans -= 1
            if a != 'B' and b != 'B':
                ans += count[2][j]
                if 2*j-i < N and S[j+j-i] == 'B':
                    ans -= 1
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
tasks=[None]*n
for i in range(n):
  a,b=map(int,input().split())
  tasks[i]=[a,b]

tasks=sorted(tasks,key=lambda x:x[1],reverse=True)
used=[False]*n
ans=0
for i in range(m,-1,-1):
  left=m-i
  for j in range(len(tasks)):
    if used[j]==False and tasks[j][0]<=left:
      ans+=tasks[j][1]
      used[j]=True
      break

print(ans)


### FIXED CODE ###

n,m=map(int,input().split())
tasks=[None]*n
for i in range(n):
  a,b=map(int,input().split())
  tasks[i]=[a,b]

tasks=sorted(tasks,key=lambda x:x[0])
import heapq
que=[]
ans=0
heapq.heapify(que)
j=0
for i in range(m,-1,-1):
  left=m-i
  while j<len(tasks):
    if tasks[j][0]<=left:
      heapq.heappush(que, tasks[j][1]*(-1))
    else:
      break
    j+=1
  if len(que)>0:
    val=heapq.heappop(que)*(-1)
    ans+=val
      
print(ans)
### BUGGY CODE ###

from itertools import  product
K, S = map(int, input().split())
ans = 0
for x,y in product(range(K+1),repeat=2):
    z = S - x - y
    if 0 <= z <= K and x + y + z == S:
        ans += 1
print(ans)

### FIXED CODE ###

from itertools import  product
K, S = map(int, input().split())
ans = 0
for x,y in product(range(K+1),repeat=2):
    z = S - x - y
    if 0 <= z <= K and x + y + z == S:
        ans += 1
print(ans)
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
arr = np.array(list(map(int, input().split())))


for _ in range(k):
    tmp = np.zeros(n + 2, np.int32)
    for i in range(n):
        power = arr[i]
        left = max(0, i - power + 1)
        right = min(n + 1, i + power + 2)
        tmp[left] += 1
        tmp[right] -= 1
    arr = np.cumsum(tmp)[1:-1]

print(*arr)

### FIXED CODE ###

from itertools import accumulate
import sys

n, k = map(int, input().split())
arr = list(map(int, input().split()))

for cnt in range(k):
    tmp = [0] * (n + 2)
    for i in range(n):
        power = arr[i]
        left = max(0, i - power + 1)
        right = min(n + 1, i + power + 2)
        tmp[left] += 1
        tmp[right] -= 1
    arr = list(accumulate(tmp))[1:-1]
    if cnt > 40:
        arr = [n] * n
        print(*arr)
        sys.exit()

print(*arr)
### BUGGY CODE ###

A,B,N=map(int,input().split())
import math
def f(x):
    return math.floor(A*x/B) - A*math.floor(x/B)

ans = []
for i in range(1, N//B+1):
    ans.append(f(B*i-1))
ans.append(f(N))
ans.append(f(1))
#print(f(N))
print(max(ans))

### FIXED CODE ###


A,B,N=map(int,input().split())
import math
def f(x):
    return math.floor(A*x/B) - A*math.floor(x/B)


print(f(min(B-1,N)))
### BUGGY CODE ###

n,m = map(int,input().split())

l1 = [[] for i in range(n)]
l2 = []

for i in range(m):
    p,y = map(int,input().split())
    l1[p-1].append(y)
    l2.append((p,y))

for p in range(n):
    l1[p].sort()

for i in range(m):
    p = l2[i][0]
    k = l1[p-1].index(l2[i][1])+1
    p = str(p)
    k = str(k)
    ans = "0"*(6-len(p))+p+"0"*(6-len(k))+k
    print(ans)

### FIXED CODE ###

n,m = map(int,input().split())

l1 = [[] for i in range(n)]
l2 = []

for i in range(m):
    p,y = map(int,input().split())
    l1[p-1].append(y)
    l2.append((p,y))

dic = {}

for p in range(n):
    l1[p].sort()
    for i in range(len(l1[p])):
        dic[l1[p][i]] = i+1
        

for i in range(m):
    p = l2[i][0]
    k = dic[l2[i][1]]
    p = str(p)
    k = str(k)
    ans = "0"*(6-len(p))+p+"0"*(6-len(k))+k
    print(ans)
### BUGGY CODE ###

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

for i in range(m):
    cnt = 0
    b,c = map(int, input().split())
    for j in range(n):
        if a[j] < c:
            a[j] = c
            cnt += 1
            if cnt >= b:
                break
        else:
            break
    a.sort()

print(sum(a))


### FIXED CODE ###

n,m = map(int, input().split())
a = list(map(int,input().split()))
a.sort()
ans = 0
tmp = []
tm = 0
for i in range(m):
    cnt = 0
    b,c = map(int, input().split())
    tmp.append([b,c])

tmp = sorted(tmp, reverse = True, key = lambda x : x[1])
cnt = 0
for i in range(n):
    if a[i] < tmp[cnt][1]:
        a[i] = tmp[cnt][1]
        tmp[cnt][0] -= 1
        if tmp[cnt][0] == 0:
            cnt += 1
            if cnt == m:
                break
    else:
        break

print(sum(a))
### BUGGY CODE ###

import sys
aa=list(map(int,sys.stdin.read().split()))
aa=aa[1:]
n=len(aa)
import bisect
bb=[]
for i in range(n):
    if not bb:
        bb.append(aa[i])
    else:
        if bb[0] >= aa[i]:
            if bb[-1] == aa[i]:
                bb.append(aa[i])
            else:
                bb.insert(0, aa[i])
        else:
            j = bisect.bisect_left(bb,aa[i])
            bb[j-1] = aa[i]
print(len(bb))

### FIXED CODE ###

import sys
aa=list(map(int,sys.stdin.read().split()))
aa=aa[1:aa[0]+1]
n=len(aa)
import bisect
bb=[]
for i in range(n):
    if not bb:
        bb.append(aa[-i-1])
    else:
        if bb[-1] <= aa[-i-1]:
            bb.append(aa[-i-1])
        else:
            j = bisect.bisect_right(bb,aa[-i-1])
            bb[j] = aa[-i-1]
print(len(bb))
### BUGGY CODE ###

K,S = map(int,input().split())
count = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k == S:
                count+=1
print(count)

### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for X in range(K+1):
  for Y in range(K+1):
    if 0 <= S-X-Y <= K:
      count += 1
print(count)
### BUGGY CODE ###

n = int(input())
a = [int(e) for e in input().split()]
flag = False
for i in range(0,n):
    for j in range(0,n):
        if i != j and a[i] == a[j]:
            flag = True
            break
if flag:
    print('NO')
else:
    print('YES')


### FIXED CODE ###

n = int(input())
a = [int(e) for e in input().split()]
a.sort()
flag = False
for i in range(0,n-1):
    if a[i] == a[i+1]:
        flag = True

if flag:
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

import numpy as np
 
def chk_route(c):
    global H,W
    ans=[]
    if c[0] != H-1:
        if T[c[0]+1][c[1]]==0:
            ans.append(c[0]+1)
            ans.append(c[1])
    if c[0] != 0:
        if T[c[0]-1][c[1]]==0:
            ans.append(c[0]-1)
            ans.append(c[1])
 
    if c[1] != W-1:
        if T[c[0]][c[1]+1]==0:
            ans.append(c[0])
            ans.append(c[1]+1)
 
    if c[1] != 0:
        if T[c[0]][c[1]-1]==0:
            ans.append(c[0])
            ans.append(c[1]-1)
    return ans
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)

for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
B=T.copy()    
d=0
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
        c=[]    

        s=1
        c.append(i)
        c.append(j)
        T=B.copy()
        t=len(c)//2

        while t>0: 
                t=len(c)//2
                for k in range(t):T[c[0+k*2]][c[1+k*2]]=s
                for k in range(t):
                        c += (chk_route([c.pop(0),c.pop(0)]))
                s+=1
        d = max(d,np.max(T))
 
print(d-1)

### FIXED CODE ###

from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)
#T=[]
S=np.zeros_like(T,dtype=int) 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#B=T.copy()    
d=0
c=deque()  
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
          
        c.append((i,j))
        S[i][j] = 1
        #c.append(j)
        
        #t=len(c)
        while True:

                try:
                  m,n = c.popleft()
                except IndexError: break
                
                
                for kk in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                  if not (0<=kk[0]<H and 0<= kk[1] <W): continue
                  if T[kk]==1:continue
                  if S[kk] == 0:
                    c.append(kk)
                    S[kk] = S[m][n]+1        
                        
 
        #print(T)
        d = max(d,np.max(S))
        S=np.zeros_like(T,dtype=int)
        
print(d-1)
### BUGGY CODE ###

N_n_osatsu, Y_sum_money = map(int, input().split())

rest_money = Y_sum_money
n_each_osatsu_list = [] # 万札、五千円札、千円札の枚数の2重リスト

for n_10000 in range(int(Y_sum_money/10000 +1)): # 万札枚数。0枚からスタート
    rest_money = Y_sum_money - 10000*n_10000
    if rest_money == 0: # 万札だけで目標金額になる場合
        n_each_osatsu_list.append([n_10000, 0, 0])
        break
    if rest_money < 0: # もう万札が追加できない場合
        break
    for n_5000 in range(int(rest_money/5000 + 1)): # 万札枚数決定後に5000円の枚数を探索。5000円0枚からスタート
        if (rest_money - n_5000*5000) >= 0:
            n_1000 = int((rest_money - n_5000*5000)/1000)
            n_each_osatsu_list.append([n_10000, n_5000, n_1000])

n_sum_osatsu_list = [sum(x) for x in n_each_osatsu_list] # お札合計枚数のリスト

try:
    print(*n_each_osatsu_list[n_sum_osatsu_list.index(N_n_osatsu)], sep=" ")
except:
    print("-1 -1 -1")

### FIXED CODE ###

N_n_osatsu, Y_sum_money = map(int, input().split())

rest_money = Y_sum_money
rest_n_osatsu = N_n_osatsu
n_each_osatsu_list = [] # 万札、五千円札、千円札の枚数の2重リスト

def skip_search(rest_money, rest_n_osatsu):  # 明らかに無理な場合、処理をスキップ。これを入れないと制限時間超過
    if rest_n_osatsu*1000 > rest_money or rest_n_osatsu*10000 < rest_money:
        return True

for n_10000 in range(int(Y_sum_money/10000 +1)): # 万札枚数。0枚からスタート
    rest_money = Y_sum_money - 10000*n_10000
    rest_n_osatsu = N_n_osatsu - n_10000
    if skip_search(rest_money, rest_n_osatsu):
        break

    if rest_money == 0: # 万札だけで目標金額になる場合
        n_each_osatsu_list.append([n_10000, 0, 0])
        break

    for n_5000 in range(int(rest_money/5000 + 1)): # 万札枚数決定後に5000円の枚数を探索。5000円0枚からスタート
        rest_money = Y_sum_money - 10000*n_10000 - 5000*n_5000
        rest_n_osatsu = N_n_osatsu - n_10000 - n_5000
        if skip_search(rest_money, rest_n_osatsu):
            break
        n_1000 = int(rest_money/1000)
        n_each_osatsu_list.append([n_10000, n_5000, n_1000])

n_sum_osatsu_list = [sum(x) for x in n_each_osatsu_list] # お札合計枚数のリスト

try:
    print(*n_each_osatsu_list[n_sum_osatsu_list.index(N_n_osatsu)], sep=" ")
except:
    print("-1 -1 -1")
### BUGGY CODE ###

import copy

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

jumpIndex = -1

for i in range(N):
    if i == jumpIndex - 1:
        print(tmpMax)
        continue
    tmp = copy.copy(A)
    tmp.remove(A[i])
    tmpMax = max(tmp)
    for j in range(i + 1, N):
        if A[i] == tmpMax:
            jumpIndex = i
    print(tmpMax)


### FIXED CODE ###

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

maxNum = max(A)
index = -1
for i in range(N):
    if A[i] == maxNum:
        index = i

for i in range(N):
    if i != index:
        print(maxNum)
        continue
    else:
        A.remove(maxNum)
        print(max(A))
### BUGGY CODE ###

from heapq import heappush, heappop

H, W = map(int, input().split())
grid = [0] * H
D = [None]*H
Q = []
for h in range(H):
    D[h] = [10**9]*W
    l = input().strip()
    for w in range(W):
        if l[w] == "#":
            D[h][w] = 0
            Q.append((0, h, w))
    grid[h] = l

m = 0
while Q:
    d, h, w = heappop(Q)
    m = max(m, d)
    for dx, dy in [(-1,0), (1,0), (0,-1), (0, +1)]:
        h1, w1 = h+dx, w+dy
        if 0 <= h1 < H and 0 <= w1 < W:
            if D[h1][w1] > d + 1:
                D[h1][w1] = d + 1
                heappush(Q, (d + 1, h1, w1))

#for h in range(H): print(D[h])
print(m)






### FIXED CODE ###

def gen():
    print("1000 1000")
    print("#"+"."*999)
    for i in range(1000-1):
        print("."*1000)

def main():
    from collections import deque
    import sys
    from heapq import heappush, heappop
    input = sys.stdin.readline
    H, W = map(int, input().split())
    D = [None]*H
    Q = deque()
    for h in range(H):
        D[h] = [10e10]*W
        l = input()
        for w in range(W):
            if l[w] == "#":
                D[h][w] = 0
                Q.append((h, w))
    m = 0
    while Q:
        h, w = Q.popleft()
        alt = D[h][w] + 1
        for dx, dy in [(-1,0), (1,0), (0,-1), (0, +1)]:
            h1, w1 = h+dx, w+dy
            if 0 <= h1 < H and 0 <= w1 < W:
                if D[h1][w1] > alt:
                    D[h1][w1] = alt
                    m = max(m, alt)
                    Q.append((h1, w1))

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

import math
N = int(input())
S = [input() for i in range(N)]

for i, s in enumerate(S):
    S[i] = "".join(sorted(list(s)))

skiptbl = [False for j in range(N)]
count = 0
for i in range(N):
    if skiptbl[i]:
        continue
    d = 0
    for j in range(i+1, N):
        if skiptbl[j]:
            continue
        if S[i] == S[j]:
            d += 1
            skiptbl[j] = True
    count += d if d <= 1 else d + math.factorial(d) / (2 * math.factorial(d - 2))
print(int(count))


### FIXED CODE ###

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

count = 0
appeared = {}
for i in range(N):
    S[i] = "".join(sorted(list(S[i])))
    if S[i] in appeared:
        count += appeared[S[i]]
        appeared[S[i]] += 1
    else:
        appeared[S[i]] = 1
print(int(count))
### BUGGY CODE ###

a,b,n=map(int, input().split())
list =[]
for x in range(n+1) :
    list.append(int(a*x/b) - a* int(x/b))
print(max(list))

### FIXED CODE ###

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

import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


class LinkedList:
    def __init__(self, val, pre):
        self.prev = pre
        self.value = val


s = input()
t = input()

info = deque(deque() for _ in range(26))
check = []
for i in range(len(s)):
    info[ord(s[i]) - 97].appendleft(i)
ans = [INF] * (max(len(s), len(t)) + 10)
link = [0] * (max(len(s), len(t)) + 10)
for i in t:
    for l in info[ord(i) - 97]:
        ind = bisect_left(ans, l)
        ans[ind] = l
        a = LinkedList(i, link[ind-1])
        link[ind] = a
num = bisect_left(ans, INF)
ans = deque()
a = link[num-1]
while len(ans) < num:
    ans.appendleft(a.value)
    a = a.prev
print("".join(ans))


### FIXED CODE ###

import sys
import math
from collections import deque
import copy

input = sys.stdin.readline

s = input()
t = input()

dp = [[0 for _ in range(len(t) + 10)] for _ in range(len(s) + 10)]

for i in range(1, len(s)):
    for l in range(1, len(t)):
        if s[i - 1] == t[l - 1]:
            dp[i][l] = max(max(dp[i - 1][l - 1] + 1, dp[i][l - 1]), dp[i - 1][l])
        else:
            dp[i][l] = max(dp[i][l - 1], dp[i - 1][l])
length = dp[len(s) - 1][len(t) - 1]
if length == 0:
    print("")
else:
    ans = ''
    i = len(s) - 1
    l = len(t) - 1
    while i > 0 and l > 0:
        if dp[i-1][l] == dp[i][l] and i >= 1:
            i -= 1
        elif dp[i][l-1] == dp[i][l] and l >= 1:
            l -= 1
        else:
            ans = s[i - 1] + ans
            i -= 1
            l -= 1
    print(ans)