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

import bisect
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
ope = []
d = []
for i in range(m):
    ope.append(list(map(int,input().split())))
ope = sorted(ope,key = lambda x:-x[1])
for b,c in ope:
    if len(d) == n:
        break
    elif len(d) + b > n:
        d  = d + [c]*(n-len(d))
    else:
        d = d + [c]*b
d.reverse()
arr = sorted(arr,reverse = True)
x = [0]*(n+1)
x[0] = sum(arr)
for i in range(1,n+1):
    t_arr = arr.pop()
    if d:
        t_d = d.pop()
    else:
        t_d = t_arr
    x[i] = x[i-1] + t_d - t_arr
    if x[i] < x[i-1]:
        break
print(max(x))

### FIXED CODE ###

import bisect
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
ope = []
d = []
for i in range(m):
    ope.append(list(map(int,input().split())))
ope = sorted(ope,key = lambda x:-x[1])
i = 0
ok = True
for b,c in ope:
    for rep in range(b):
        if i >= n or arr[i] > c:
            ok = False
            break
        arr[i] = c
        i += 1
    if ok:
        continue
    else:
        break
print(sum(arr))
### BUGGY CODE ###

# coding: utf-8


def rpow(x, y, z):
    i = 1
    a = x
    while i*i < y:
        a = (a*a) % z
        i *= 2
    return (a*pow(x, y-i, z)) % z if 0 < y else 1


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    P = [1]*(k+1)
    p = rpow(m-1, n-1-k, mod)
    for i in range(k+1):
        P[-1-i] = p
        p = p*(m-1) % mod

    ret = m*P[0] % mod
    ncr = 1
    for i in range(1, k+1):
        ncr = ncr*(n-i)//i
        ret += m*P[i]*ncr % mod

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def bpow(x, y, z):
    a = 1
    for b in format(y, 'b'):
        a = (a*a) % z
        if b == '1':
            a = (a*x) % z
    return a


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    if m == 1 and n-1 == k:
        return str(1)

    ncr = 1
    p = m*bpow(m-1, n-1, mod) % mod
    ret = p
    inv = bpow(m-1, mod-2, mod)
    for i in range(1, k+1):
        ncr = (ncr * (n-i)*bpow(i, mod-2, mod)) % mod
        p = (p*inv) % mod
        ret += p*ncr % mod

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

S=list(input())
T=list(input())
As={chr(ord('a')+i):[] for i in range(26)}
At={chr(ord('a')+i):[] for i in range(26)}

ans='Yes'
if len(set(S))==len(set(T)):
    for i in range(len(S)):
        As[S[i]].append(i)
        At[T[i]].append(i)
        if As[S[i]]!=At[T[i]]:
            ans='No'
            break
else:
    ans='No'

print(ans)

### FIXED CODE ###

from collections import defaultdict

S=list(input())
T=list(input())

Sm=defaultdict(str)
Tm=defaultdict(str)

for s,t in zip(S,T):
    if (Sm[s] and Sm[s]!=t) or (Tm[t] and Tm[t]!=s): print('No'); exit()
    else: Sm[s]=t; Tm[t]=s
print('Yes')
### BUGGY CODE ###

N=int(input())
a=[]
s=0
for i in range(N):
  b=input()
  if b not in a:
    s+=1
    a.append(b)
print(s)

### FIXED CODE ###

N=int(input())
a=[]
s=0
for i in range(N):
  a.append(input())

print(len(set(a)))
### BUGGY CODE ###

import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
A2 = [0]*(N+1)
for i in range(K):
    for j in range(N):
        g = math.ceil(j+1-A[j]-0.5)
        if g<1:
            g=1
        h = math.floor(j+1+A[j]+0.5)
        if h>N:
            h=N
        A2[g-1]+=1
        A2[h]-=1
    A[0]=A2[0]
    for j in range(1, N):
        A[j]=A[j-1]+A2[j]
    A2 = [0]*(N+1)
    c = 0
    for p in range(N):
        c+=A[p]
    if c >= N*N:
        break

print(*A)

### FIXED CODE ###

import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
A2 = [0]*(N+1)
for i in range(K):
    for j in range(N):
        g = math.ceil(j+1-A[j]-0.5)
        if g<1:
            g=1
        h = math.floor(j+1+A[j]+0.5)
        if h>N:
            h=N
        A2[g-1]+=1
        A2[h]-=1
    A[0]=A2[0]
    for j in range(1, N):
        A[j]=A[j-1]+A2[j]
    A2 = [0]*(N+1)
    c = 0
    for p in range(N):
        c+=A[p]
    if c >= N*N:
        break

print(*A)
### BUGGY CODE ###

H,W = map(int, input().split())
S = [list(input()) for _ in range(H)]

w_score = [[0]*W for _ in range(H)]
h_score = [[0]*W for _ in range(H)]

begin = -1
streak = 1
for hi in range(H):
    for wi in range(W):
        if begin == -1 and S[hi][wi]=='.':
            begin = wi
        elif begin != -1 and S[hi][wi] == '.':
            streak += 1
        if wi ==W-1 or(begin != -1 and S[hi][wi]=='#'):
            if wi == W-1 and S[hi][wi]=='.':
                w_score[hi][wi]=streak
            for i in range(W)[begin:wi]:
                w_score[hi][i] = streak
            streak = 1
            begin = -1

# for s in w_score:
#     print(s)
# print('-'*10)

begin = -1
streak = 1
for wi in range(W):
    for hi in range(H):
        if begin == -1 and S[hi][wi]=='.':
            begin = hi
        elif begin != -1 and S[hi][wi] == '.':
            streak += 1
        if hi ==H-1 or(begin != -1 and S[hi][wi]=='#'):
            if hi == H-1 and S[hi][wi]=='.':
                h_score[hi][wi]= streak
            for i in range(H)[begin:hi]:
                h_score[i][wi] = streak
            streak = 1
            begin = -1

# for s in h_score:
#     print(s)
# print('-'*10)

ans = 0
score = [[0]*W for _ in range(H)]
for hi in range(H):
    for wi in range(W):
        w =w_score[hi][wi] 
        h= h_score[hi][wi] 
        score_ = w+h
        score_ += -1 if w>0 and h>0 else 0
        ans = max(ans,score_)
        score[hi][wi] = score_
        
# for s in score:
#     print(s)

print(ans)


### FIXED CODE ###

H,W = map(int, input().split())
S = [list(input()) for _ in range(H)]

w_score = [[0]*W for _ in range(H)]
h_score = [[0]*W for _ in range(H)]

begin = -1
streak = 1
for hi in range(H):
    for wi in range(W):
        if begin == -1 and S[hi][wi]=='.':
            begin = wi
        elif begin != -1 and S[hi][wi] == '.':
            streak += 1
        if wi ==W-1 or(begin != -1 and S[hi][wi]=='#'):
            if wi == W-1 and S[hi][wi]=='.':
                w_score[hi][wi]=streak
            for i in range(W)[begin:wi]:
                w_score[hi][i] = streak
            streak = 1
            begin = -1

# for s in w_score:
#     print(s)
# print('-'*10)

begin = -1
streak = 1
for wi in range(W):
    for hi in range(H):
        if begin == -1 and S[hi][wi]=='.':
            begin = hi
        elif begin != -1 and S[hi][wi] == '.':
            streak += 1
        if hi ==H-1 or(begin != -1 and S[hi][wi]=='#'):
            if hi == H-1 and S[hi][wi]=='.':
                h_score[hi][wi]= streak
            for i in range(H)[begin:hi]:
                h_score[i][wi] = streak
            streak = 1
            begin = -1

# for s in h_score:
#     print(s)
# print('-'*10)

ans = 0
score = [[0]*W for _ in range(H)]
for hi in range(H):
    for wi in range(W):
        w =w_score[hi][wi] 
        h= h_score[hi][wi] 
        score_ = w+h
        score_ += -1 if w>0 and h>0 else 0
        ans = max(ans,score_)
        score[hi][wi] = score_
        
# for s in score:
#     print(s)

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

import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
X = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(X[0][0])
for i in range(H):
  for j in range(W):
    for k in dp[i][j]:
      if i + 1 < H:
        u = k + X[i + 1][j]
        v = abs(k - X[i + 1][j])
        dp[i + 1][j].add(u)
        dp[i + 1][j].add(v)
      if j + 1 < W:
        u = k + X[i][j + 1]
        v = abs(k - X[i][j + 1])
        dp[i][j + 1].add(u)
        dp[i][j + 1].add(v)
res = float("inf")
#print(dp[1][1])
for k in dp[-1][-1]: res = min(k, res)
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
X = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
dp1 = [set() for _ in range(W)]
dp1[0].add(X[0][0])
dp2 = [set() for _ in range(W)]
dplimit = [[0] * W for _ in range(H)]
dplimit[-1][-1] = 80
for i in range(H - 1, -1, -1):
  for j in range(W - 1, -1, -1):
    x = X[i][j]
    if i > 0: dplimit[i - 1][j] = max(dplimit[i - 1][j], dplimit[i][j] + x)
    if j > 0: dplimit[i][j - 1] = max(dplimit[i][j - 1], dplimit[i][j] + x)
for i in range(H):
  if i % 2 == 0:
    dp2 = [set() for _ in range(W)]
  else: dp1 = [set() for _ in range(W)]
  for j in range(W):
    if i % 2 == 0:
      for k in dp1[j]:
        if i + 1 < H:
          u = k + X[i + 1][j]
          v = abs(k - X[i + 1][j])
          if u <= dplimit[i][j]: dp2[j].add(u)
          if v <= dplimit[i][j]: dp2[j].add(v)
        if j + 1 < W:
          u = k + X[i][j + 1]
          v = abs(k - X[i][j + 1])
          if u <= dplimit[i][j]: dp1[j + 1].add(u)
          if v <= dplimit[i][j]: dp1[j + 1].add(v)
    else:
      for k in dp2[j]:
        if i + 1 < H:
          u = k + X[i + 1][j]
          v = abs(k - X[i + 1][j])
          if u <= dplimit[i][j]: dp1[j].add(u)
          if v <= dplimit[i][j]: dp1[j].add(v)
        if j + 1 < W:
          u = k + X[i][j + 1]
          v = abs(k - X[i][j + 1])
          if u <= dplimit[i][j]: dp2[j + 1].add(u)
          if v <= dplimit[i][j]: dp2[j + 1].add(v)
res = float("inf")
if H % 2:
  for k in dp1[-1]: res = min(k, res)
else:
  for k in dp2[-1]: res = min(k, res)
print(res)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

s = [int(i) for i in STR()]
l = len(s)
arr = [-1 for _ in range(l)]
tmp = 0
for i in range(l):
    tmp += s[i] * (10 ** (l - i))
    arr[i] = tmp % 2019
arr.sort()
tmp = arr[0]
cnt = 1
ans = 0
for i in range(1, l):
    if tmp == arr[i]:
        cnt += 1
    else:
        ans += cnt * (cnt - 1) // 2
        if tmp == 0:
            ans += cnt
        cnt = 1
        tmp = arr[i]
ans += cnt * (cnt - 1) // 2
if tmp == 0:
    ans += cnt
print(ans)


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

s = [int(i) for i in STR()]
l = len(s)
arr = [-1 for _ in range(l)]
tmp = 0
for i in range(l):
    tmp += s[i] * pow(10, l - i, 2019)
    tmp %= 2019
    arr[i] = tmp
arr.sort()
tmp = arr[0]
cnt = 1
ans = 0
for i in range(1, l):
    if tmp == arr[i]:
        cnt += 1
    else:
        ans += cnt * (cnt - 1) // 2
        if tmp == 0:
            ans += cnt
        cnt = 1
        tmp = arr[i]
ans += cnt * (cnt - 1) // 2
if tmp == 0:
    ans += cnt
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

R, C, K = map(int,input().split())
RC = [[0] * (C+1) for _ in range(R+1)]

for _ in range(K):
    r, c, v = map(int,input().split())
    RC[r-1][c-1] = v


dp = [[[0] * 4 for _ in range(C+1)] for _ in range(R+1)]

dp[0][0][1] = RC[0][0]
for r in range(R):
    for c in range(C):
        for i in range(4):
            dp[r][c+1][i] = max(dp[r][c][i], dp[r][c+1][i])
            dp[r+1][c][0] = max(dp[r][c][i], dp[r+1][c][0])
            if i <= 2:
                dp[r][c+1][i+1] = max(dp[r][c][i] + RC[r][c+1], dp[r][c+1][i+1])
        dp[r+1][c][1] = max(dp[r+1][c][1], dp[r+1][c][0] + RC[r+1][c])
        
print(max(dp[-2][-2]))
            
                
            
    


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

R, C, K = map(int,input().split())
RC = [[0] * (C+1) for _ in range(R+1)]

for _ in range(K):
    r, c, v = map(int,input().split())
    RC[r-1][c-1] = v


dp = [[[0] * (C+1) for i in range(R+1)] for j in range(4)]

dp[1][0][0] = RC[0][0]
for r in range(R):
    for c in range(C):
        for i in range(4):
            dp[i][r][c+1] = max(dp[i][r][c], dp[i][r][c+1])
            if i <= 2:
                dp[i+1][r][c+1] = max(dp[i][r][c] + RC[r][c+1], dp[i+1][r][c+1])
            dp[0][r+1][c] = max(dp[i][r][c], dp[0][r+1][c])
        dp[1][r+1][c] = max(dp[1][r+1][c], dp[0][r+1][c] + RC[r+1][c])

print(max(dp[0][-2][-2], dp[1][-2][-2], dp[2][-2][-2], dp[3][-2][-2]))
### BUGGY CODE ###

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

for j in range(n):
	L = [a[j] for i in range(n) if abs(a[i] - a[j]) <= 1]
	if max < len(L):
		max = len(L)
print(max)

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int,input().split()))
M = 1

c = collections.Counter(a)

for x in range(max(a) + 2):
	d = c[x] + c[x-1] + c[x+1]
	if d >= M:
		M = d

print(M)
### BUGGY CODE ###

A = int(input())
B = list(map(int, input().split()))  
C = int(input())

sum_l=[]
for i in range(C):
  D = list(map(int, input().split()))
  
  for h in range(A):
    if B[h] == D[0]:
      B[h]=D[1]
    
  print(sum(B))

  

### FIXED CODE ###

import collections

n=int(input())
arr=list(map(int,input().split()))
cnt=collections.defaultdict(int)
for val in arr: #あらかじめ各Aiの個数を数えておく
 cnt[val]+=1
sums=sum(arr) #あらかじめAiの総和を求めておく
q=int(input())
for _ in range(q):
 b,c=map(int,input().split())
 diff=(c-b)*(cnt[b]) #各クエリにおいて数列Aの総和は(値がBiである要素の個数)*(Ci-Bi)だけ変化する
 sums+=diff
 print(sums) 
 cnt[c]+=cnt[b] #値がCi,Biである要素の個数を更新する
 cnt[b]=0
### BUGGY CODE ###

n,k = map(int,input().split())
A = list(map(int,input().split()))
sub = [0]*n
ans = 1
cir = 0
a = 0
b = 0
if k < n:
  for i in range(k+1):
    sub[i] = ans
    ans = A[ans-1]
  print(sub[k])
else:
  for i in range(n):
    sub[i] = ans
    b = A[ans-1]
    if b in sub:
      a = sub.index(b)
      cir = i+1 - a
      break
    else:
      ans = b
  print(sub[a + (k - a) % cir])


### FIXED CODE ###

n,k = map(int,input().split())
A = list(map(int,input().split()))
sub = [0]*n
city = 0
all = []
roop = []
while sub[city] != 2:
  if sub[city] == 0:
    all.append(city+1)
  else:
    roop.append(city+1)
  sub[city] += 1
  city = A[city] -1
if len(all) > k:
  print(all[k])
else:
  print(roop[(k-(len(all)-len(roop)))%len(roop)])
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def fft(A, B, L):
    import numpy as np
    from numpy.fft import rfft, irfft

    # FFT
    res = irfft(rfft(A, L) * rfft(B, L), L)
    # 四捨五入して整数に
    res = np.rint(res).astype(np.int64)
    return res

MAX = 10 ** 5
N, M = MAP()
A1 = [0] * (MAX+1)
A2 = [0] * (MAX+1)
for a in LIST():
    A1[a] += 1
    A2[a] += 1

L = 2 ** 18
res = fft(A1, A2, L)

ans = cnt = 0
for a in range(L-1, -1, -1):
    c = res[a]
    if cnt + c <= M:
        cnt += c
        ans += a * c
    else:
        while cnt < M:
            cnt += 1
            ans += a
        break
print(ans)


### FIXED CODE ###

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

import sys
from bisect import bisect_left
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

# 右手と左手(a,b)の和がx以上となる組の数
def calc(x):
    # 各aについて、条件を満たす数を数える
    ans = 0
    for a in A:
        # 式変形： a + b >= x → b >= x - a
        ans += N - bisect_left(A, x - a)
    return ans >= M

N, M = MAP()
A = LIST()

A.sort()
res = bisearch_max(0, 10**10+1, calc)

ans = m = 0
acc = [0] + list(accumulate(A))
for a in A:
    idx = bisect_left(A, res - a)
    cnt = N - idx
    # 幸福度
    ans += a * cnt + (acc[N] - acc[idx])
    # 握手の回数
    m += cnt

# 同値でMを超えた分の調整
ans -= res * (m - M)
print(ans)
### BUGGY CODE ###

import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)


def solve():
    N, *a = map(int, read().split())
    a = tuple(a)
    INF = float('inf')
    memo = [[INF] * N for _ in range(N)]

    def f(i, j):
        if memo[i][j] != INF:
            return memo[i][j]
        n = j - i + 1
        if i == j:
            if n % 2 == r:
                s = a[i]
            else:
                s = -a[i]
            memo[i][j] = s
            return s
        if n % 2 == r:
            s = max(f(i, j - 1) + a[j], f(i + 1, j) + a[i])
        else:
            s = min(f(i, j - 1) - a[j], f(i + 1, j) - a[i])
        memo[i][j] = s
        return s

    r = N % 2
    f(0, N - 1)
    return memo[0][N - 1]


print(solve())


### FIXED CODE ###

import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)


def solve():
    n, *a = map(int, read().split())
    a = tuple(a)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[i + 1][j]
            R = a[j] - dp[i][j - 1]
            if L > R:
                dp[i][j] = L
            else:
                dp[i][j] = R
    return dp[0][n - 1]


print(solve())
### BUGGY CODE ###

n = int(input())
s = str(input())
L = set()
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            L.add(s[i]+s[j]+s[k])
print(len(L))


### FIXED CODE ###

n = int(input())
s = str(input())
cnt = 0
for i in range(1000):
    x = str(i).zfill(3)
    i1 = s.find(x[0])
    i2 = s[i1+1:].find(x[1])
    i3 = s[i1+i2+2:].find(x[2])
    if -1 not in (i1, i2, i3):
        cnt += 1
print(cnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = sorted(A)

idx = B[0]
idx_count = 0
idx_set = []
for i in range(N):
  if idx != B[i]:
    tmp1 = int(idx_count*(idx_count-1)/2)		# 同一の整数を持つボールの組合せ数
    tmp2 = int((idx_count-1)*(idx_count-2)/2)	# 同一の整数を持つボールを1つ除いたときの組合せ数
    idx_set.append([idx, tmp1, tmp2])
    idx_count = 0
    idx = B[i]
  idx_count+=1
if idx_count != 0:
  tmp1 = int(idx_count*(idx_count-1)/2)			# 同一の整数を持つボールの組合せ数
  tmp2 = int((idx_count-1)*(idx_count-2)/2)		# 同一の整数を持つボールを1つ除いたときの組合せ数
  idx_set.append([idx, tmp1, tmp2])
#print(idx_set)
idx_sum_set = []
all_c = 0
for i in range(len(idx_set)):
  all_c += idx_set[i][1]
for i in range(len(idx_set)):
  tmp = all_c-idx_set[i][1]+idx_set[i][2]
  idx_sum_set.append([idx_set[i][0], tmp])    

for i in range(N):
  j = int(len(idx_sum_set)/2)
  while 1:
    if A[i] == idx_sum_set[j][0]:
      print(idx_sum_set[j][1])
      break
    elif A[i] > idx_sum_set[j][0]:
      j = j + int((len(idx_sum_set)-j)/2)
    elif A[i] < idx_sum_set[j][0]:
      j = int(j/2)



### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
B = np.zeros(N+1)

for i in range(N):
  B[A[i]]+=1
#print(B)

all_c = 0
for i in range(1,N+1):
  all_c += int(B[i]*(B[i]-1)/2)			# 同一の整数を持つボールの組合せ数
for i in range(N):
  if B[A[i]] != 0:
    print(int(all_c-(B[A[i]]-1)))
### BUGGY CODE ###

#!/usr/bin/env python3

MOD = 10**9 + 7

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

dp = [[0] * (m + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(m):
        dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j]
        if s[i] == t[j]:
            dp[i + 1][j + 1] += dp[i][j] + 1
        dp[i + 1][j + 1] %= MOD

print(dp[n][m] + 1)



### FIXED CODE ###

#!/usr/bin/env python3

MOD = 10**9 + 7

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

dp = [[0] * (m + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(m):
        dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j]
        if s[i] == t[j]:
            dp[i + 1][j + 1] += dp[i][j] + 1
        dp[i + 1][j + 1] %= MOD

print(dp[n][m] + 1)
### BUGGY CODE ###

S=input()
N=len(S)
L=N
for i in range(L):
  S="".join(S.split("01"))
  S="".join(S.split("10"))
  #print(S)
  if L==len(S):
    break
  L=len(S)
  
#print(S)
print(N-L)

### FIXED CODE ###

S=input()
N=len(S)
ones=S.count("1")
zeros=S.count("0")
print(N-abs(ones-zeros))
### BUGGY CODE ###

n=int(input())
c=0
ans1=0
ans2=0
for a in range(1,3501):
    for b in range(a+1,3501):
        if 4*a*b>(b+a)*n and (a*b*n)%(4*a*b-(b+a)*n)==0:
            c=a*b*n//(4*a*b-(b+a)*n)
            ans1=a
            ans2=b
            break
lists=[ans1,ans2,c]
print(*lists)

### FIXED CODE ###

n=int(input())
x=0
y=0
c=0
if n%2==0:
  lists=[n,n,n//2]
  print(*lists)
elif n%4==3:
  lists=[(n+1)//4,n*(n+1)//2,n*(n+1)//2]
  print(*lists)
else:
  for a in range(2,3501,2):
    for b in range(a,3501,2):
      if 4*a*b>(b+a)*n and (a*b*n)%(4*a*b-(b+a)*n)==0:
            x=a
            y=b
            c=(a*b*n)//(4*a*b-(b+a)*n)
            break
  lists=[x,y,c]
  print(*lists)