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

def A(w, v, n,V):
    mem=[0 for i in range(V+1)]
    if n == 0 or V == 0:
        return 0
 
    for i in range(n):
        for j in range(V,w[i]-1,-1):
            mem[j] = max(mem[j], v[i]+ mem[j - w[i]])
    return mem[V]
n,V=input().split()
n,V=int(n),int(V)
 
w=[0]*n
v=[0]*n
for i in range(n):
  x,y=input().split()
  w[i],v[i]=int(x),int(y)
 
print(A(w,v,n,V))

### FIXED CODE ###

def A(w, v, n,V):
    mem=[0 for i in range(V+1)]
    if n == 0 or V == 0:
        return 0
 
    for i in range(n):
        for j in range(V,w[i]-1,-1):
            m=v[i]+ mem[j - w[i]]
            if m>mem[j]:
                mem[j]=m
    return mem[V]
n,V=input().split()
n,V=int(n),int(V)
 
w=[0]*n
v=[0]*n
for i in range(n):
  x,y=input().split()
  w[i],v[i]=int(x),int(y)
 
print(A(w,v,n,V))
### BUGGY CODE ###

n = int(input())

cost = [[float("inf") for i in range(n)] for _ in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c
for i in range(n):
    cost[i][i] = 0

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

def dijkstra(s,n,cost):
    d = [float("inf")]*n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if(not used[i]) and (v == -1):
                v = i
            elif(not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
    
        for j in range(n):
            d[j] = min(d[j],d[v]+cost[v][j])
    return d

d = dijkstra(k-1,n,cost)
ans = []
for i in range(q):
    x,y = map(int,input().split())
    ans.append(d[x-1]+d[y-1])
print(*ans , sep = "\n")

### FIXED CODE ###

from collections import deque

def f(k,edge,n):
    root = [[] for _ in range(n)]
    for i in range(n-1):
        a,b,c = edge[i][0],edge[i][1],edge[i][2]
        root[a-1].append([b-1,c])
        root[b-1].append([a-1,c])
    
    que = deque()
    for l in root[k]:
        que.append(l)
    
    dist = [float("inf")]*n
    dist[k] = 0
    visited = [False]*n
    que = deque([k])

    while que:
        pos = que.popleft()
        if not visited[pos]:
            visited[pos] = True
        for x,y in root[pos]:
            if not visited[x]:
                dist[x] = dist[pos] + y
                visited[x] = True
                que.append(x)
    return dist

n = int(input())
edge = [list(map(int,input().split())) for _ in range(n-1)]

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

ans = []
d = f(k-1,edge,n)
for i in range(q):
    x,y = map(int,input().split())
    ans.append(d[x-1] + d[y-1])

print(*ans , sep = "\n")
### BUGGY CODE ###

n = int(input())
s = input()
r = s.count('R')
g = s.count('G')
b = s.count('B')

ans = r*g*b

for i in range(n-2):
  for j in range(i+1, n-1):
    k = j + (j - i)
    if k > n-1:
    	break
    if len(set([s[i], s[j], s[k]])) == 3:
      ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
r = s.count('R')
g = s.count('G')
b = s.count('B')

ans = r*g*b

for i in range(n-2):
  for j in range(i+1, n-1):
    k = j + (j - i)
    if k > n-1:
    	break
    if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
      ans -= 1
print(ans)
### BUGGY CODE ###

import itertools
from sys import stdin
N=int(input())
st=list(stdin.readline().strip())
count=0
cnt=0
stt=set(st)
stt=list(stt)
num=["0","1","2","3","4","5","6","7","8","9"]
num = [s for s in num if s in stt ]
num_list= ["".join(i) for i in itertools.product(num,repeat=3)]

for number in num_list:
    for i in range(N):
        if number[cnt]==st[i]:
            cnt+=1
            if cnt==3:break
            continue

    if cnt==3:
        count+=1
    cnt=0
print(count)

### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

N, K = map(int, raw_input().split())
A = list(map(int, raw_input().split()))

A = sorted([a for a in A if a < K])
N = len(A)

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m + 1:]

    if sum(B) < K - A[m]:
        l = m
        continue

    dp = [False] * (K + 1)
    dp[0] = True
    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j - B[i]]

    for k in range(K - A[m], K + 1):
        if dp[k]:
            if k >= K:  # 不要
                l = m
            else:
                r = m
            break
    else:
        l = m

print r

### FIXED CODE ###

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

A = sorted([a for a in A if a < K])
N = len(A)
S = sum(A)

# あああああああああああああああああああ＼(＾o＾)／
if S < K:
    print(N)
    exit()
elif S - A[0] < N:
    print(0)
    exit()

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m + 1:]

    if S - A[m] < K - A[m]:
        l = m
        continue

    dp = [False] * (K + 1)
    dp[0] = True
    flg= False

    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j - B[i]]

            if dp[j] and K-A[m] <= j < K:
                r = m
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        l = m

print(r)
### BUGGY CODE ###

import collections
N = int(input())
S = [input() for _ in range(N)]
c = collections.Counter(S)
n = len(c)
max = c.most_common()[0][1]
d = 0
for j in range(n):
  if c.most_common()[j][1] == max:
    d += 1
  else:
    d = j
    break
ans = [c.most_common()[i][0] for i in range(d)]
ans.sort()
for i in range(d):
  print(ans[i])


### FIXED CODE ###

from collections import defaultdict
N = int(input())
S = [input() for _ in range(N)]
dic = defaultdict(int)
for i in range(N):
        dic[S[i]] += 1
dic = dict(dic)
dic = sorted(dic.items(),key = lambda x:-x[1])
n = len(dic)
max = dic[0][1]
d = 0
for i in range(n):
  if dic[i][1] == max:
    d += 1
  else:
    d = i
    break
dic = sorted(dic[0:d],key = lambda x:x[0])
for i in range(len(dic)):
  print(dic[i][0])
### BUGGY CODE ###

S=list(input())
K=int(input())
N=len(S)
l=[]
for k in range(1,N+1):
    for n in range(N):
        tmp=S[n:n+k]
        l.append("".join(tmp))
l.sort()

n_l=[l[0]]
for n in range(1,len(l)):
    if l[n]!=l[n-1]:
        n_l.append(l[n])

print(n_l[K-1])

### FIXED CODE ###

def main2():
    S=list(input())
    K=int(input())
    N=len(S)

    P=sorted(S)
    l=[]
    a=[]
    k=0
    while len(l)<=5 and k<N:
        if P[k] not in a:
            a.append(P[k])
            for n in range(N):
                if S[n]==P[k]:
                    for i in range(1,6):
                        if n+i<=N:
                            tmp="".join(S[n:n+i])
                            if tmp not in l:
                                l.append(tmp)
        k+=1
    l.sort()
    print(l[K-1])

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

import numpy as np
n = int(input())
a = np.array([[int(i) + 1, int(i), int(i)-1] for i in input().split()])

maxs = 0
for i in range(a.min(), a.max() + 1):
  maxs = max(maxs, (a==i).sum())

print(maxs)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
li=[]

for i in a:
    li.append(i-1)
    li.append(i+1)
    li.append(i)

import collections
L=collections.Counter(li)
print(max(L.values()))
### BUGGY CODE ###

from collections import deque
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
cmax = 0
for i in range(H):
    for j in range(W):
            for k in range(H):
                for l in range(W):
                    if S[i][j]=="." and S[k][l]==".":
                        que = deque([(i,j,0)])
                        hist = {(n,m):0 for n in range(H) for m in range(W)}
                        hist[(i,j)] = 1
                        while que:
                            x = que.popleft()
                            n,m,c = x[0],x[1],x[2]
                            if n==k and m==l:
                                cmax = max(cmax,c)
                                break
                            if m+1<W and S[n][m+1]=="." and hist[(n,m+1)]==0:
                                que.append((n,m+1,c+1))
                                hist[(n,m+1)] = 1
                            if m-1>-1 and S[n][m-1]=="." and hist[(n,m-1)]==0:
                                que.append((n,m-1,c+1))
                                hist[(n,m-1)] = 1
                            if n+1<H and S[n+1][m]=="." and hist[(n+1,m)]==0:
                                que.append((n+1,m,c+1))
                                hist[(n+1,m)] = 1
                            if n-1>-1 and S[n-1][m]=="." and hist[(n-1,m)]==0:
                                que.append((n-1,m,c+1))
                                hist[(n-1,m)] = 1
print(cmax)

### FIXED CODE ###

import heapq
INFTY = 10**3
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
dist = {(i,j):{(k,l):INFTY for k in range(H) for l in range(W)} for j in range(W) for i in range(H)}
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            hist = {(k,l):0 for k in range(H) for l in range(W)}
            heap = [(0,i,j)]
            dist[(i,j)][(i,j)]= 0
            hist[(i,j)] = 1
            while heap:
                d,k,l = heapq.heappop(heap)
                if d>dist[(i,j)][(k,l)]:continue
                hist[(k,l)] = 1
                if l+1<W and S[k][l+1]=="." and hist[(k,l+1)]==0:
                    if dist[(i,j)][(k,l+1)]>d+1:
                        dist[(i,j)][(k,l+1)] = d+1
                        heapq.heappush(heap,(d+1,k,l+1))
                if l-1>-1 and S[k][l-1]=="." and hist[(k,l-1)]==0:
                    if dist[(i,j)][(k,l-1)]>d+1:
                        dist[(i,j)][(k,l-1)]=d+1
                        heapq.heappush(heap,(d+1,k,l-1))
                if k+1<H and S[k+1][l]=="." and hist[(k+1,l)]==0:
                    if dist[(i,j)][(k+1,l)]>d+1:
                        dist[(i,j)][(k+1,l)]=d+1
                        heapq.heappush(heap,(d+1,k+1,l))
                if k-1>-1 and S[k-1][l]=="." and hist[(k-1,l)]==0:
                    if dist[(i,j)][(k-1,l)]>d+1:
                        dist[(i,j)][(k-1,l)]=d+1
                        heapq.heappush(heap,(d+1,k-1,l))
dmax = 0
for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                if dist[(i,j)][(k,l)]<INFTY:
                    dmax = max(dmax,dist[(i,j)][(k,l)])
print(dmax)
### BUGGY CODE ###

from collections import deque
import numpy as np

h, w = map(int, input().split())

s = []
cnt = 0
for _ in range(h):
    tmp = list(input())
    cnt += tmp.count("#")
    s.append(tmp)

pos = [0, 0]
ans = 1
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
queue = deque()
queue.append(pos)
queue.append(ans)
check = np.zeros([h, w], dtype = bool)
while queue:
    pos = queue.popleft()
    ans = queue.popleft()
    check[pos[0]][pos[1]] = True
    ans += 1
    for dy, dx in direction:
        y = pos[0] + dy
        x = pos[1] + dx
        if x == -1 or x == w or y == -1 or y == h:
            continue
        if check[y][x]:
            continue
        if s[y][x] == "#":
            continue
        if y == h - 1 and x == w - 1:
            print(h * w - cnt - ans)
            exit()
        queue.append([y, x])
        queue.append(ans)
    
else:
    print(-1)
    exit()


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())

s = []
cnt = 0
for _ in range(h):
    tmp = list(input())
    cnt += tmp.count("#")
    s.append(tmp)

pos = [0, 0]
ans = 1
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
queue = deque()
queue.append(pos)
queue.append(ans)
check = [[False for _ in range(w)] for _ in range(h)]
check[0][0] = True
while queue:
    pos = queue.popleft()
    ans = queue.popleft()
    ans += 1
    for dy, dx in direction:
        y = pos[0] + dy
        x = pos[1] + dx
        if x == -1 or x == w or y == -1 or y == h:
            continue
        if check[y][x]:
            continue
        if s[y][x] == "#":
            check[y][x] = True
            continue
        if y == h - 1 and x == w - 1:
            print(h * w - cnt - ans)
            exit()
        check[y][x] = True
        queue.append([y, x])
        queue.append(ans)
    
else:
    print(-1)
    exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


def f(x, cur):
    #print(x, cur)
    if x == 0:
        return cur
    return f(x%bin(x).count("1"), cur+1)

N = int(input())
X = input()

Xint = int(X, 2)
popcountX = X.count("1")
#print("test", Xint, popcountX)

for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((Xint%(popcountX+1) + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((Xint%(popcountX-1) - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
X = input()
Xint = int(X, 2)
Xcount = X.count("1")

"""
0010
1010 10(mod2) -> 0
i = n-1の時だけ +1
0011 -> 3 -> 1->0
0110 -> 6(mod2) -> 0
"""

if Xcount == 1:
    for i in range(N):
        if X[i] == "1":
            print(0)
        elif i == N-1:
            print(2)
        else:
            print(1)
    exit()

Modplus, Modminus = Xint%(Xcount+1), Xint%(Xcount-1)

def f(x):
    if x == 0:
        return 0
    return f(x%bin(x).count("1"))+1

for i in range(N):
    if X[i] == "1":
        print(1+f((Modminus-pow(2, N-1-i, Xcount-1))%(Xcount-1)))
    else:
        print(1+f((Modplus+pow(2, N-1-i, Xcount+1))%(Xcount+1)))
### BUGGY CODE ###

S = list(input())
Q = int(input())
reverse = False
for i in range(Q):
    Query = input()
    T = int(Query[0])
    if T == 1:
        reverse = not reverse 
    elif T == 2:
        F = int(Query[2])
        C = Query[4]
        if (F == 1 and reverse == False) or (F == 2 and reverse == True):
            S.insert(0, C)
        elif (F == 2 and reverse == False) or (F == 1 and reverse == True):
            S.append(C)

if reverse%2 == 1:
    S = S[::-1]


print(''.join(S))
print('\n')


### FIXED CODE ###

S = input()
Q = int(input())
front = ''
end = ''
reverse = False
for i in range(Q):
    Query = input()
    if Query[0] == '1':
        reverse = not reverse 
    else:
        if (Query[2] == '1' and reverse == False) or (Query[2] == '2' and reverse == True):
            front = Query[4] + front
        else:
            end = end + Query[4]

S = front + S + end
if reverse == True:
    S = S[::-1]


print(S)
print('\n')
### BUGGY CODE ###

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

#i個目を選ぶとき合計価値がjになる場合の重さの最小値
#(i-1,j)  or  (i-1,j-v)+w

dp = [[10**12-1]*100010 for i in range(N)]

dp[0][WV[0][1]] = WV[0][0]
res = WV[0][1]

for i in range(1,N):
  w = WV[i][0]
  v = WV[i][1]
  dp[i][WV[i][1]] = WV[i][0]
  res = max(res,WV[i][1])
  for j in range(1,100010):
    if j>=v:
      dp[i][j] = min(dp[i-1][j],dp[i-1][j-v]+w,dp[i][j])
    else:
      dp[i][j] = min(dp[i-1][j],dp[i][j])
    if 0 < dp[i][j] <= W:
      res = max(res,j)
    
print(res)

### FIXED CODE ###

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

#i個目を選ぶとき合計価値がjになる場合の重さの最小値
#(i-1,j)  or  (i-1,j-v)+w

dp = [[10**12-1]*100010 for i in range(N)]

dp[0][WV[0][1]] = WV[0][0]
res = WV[0][1]

for i in range(1,N):
  w = WV[i][0]
  v = WV[i][1]
  dp[i][WV[i][1]] = WV[i][0]
  res = max(res,WV[i][1])
  for j in range(1,100010):
    if j>=v:
      dp[i][j] = min(dp[i-1][j],dp[i-1][j-v]+w,dp[i][j])
    else:
      dp[i][j] = min(dp[i-1][j],dp[i][j])
    if 0 < dp[i][j] <= W:
      res = max(res,j)
    
print(res)
### BUGGY CODE ###

N,K=map(int,raw_input().split())
c=[]
for i in range(N):
	a,b=map(int,raw_input().split())
	c+=[a]*b

c.sort()
print c[K-1]

### FIXED CODE ###

N,K=map(int,raw_input().split())
c=[0]*N
for i in range(N):
	a,b=map(int,raw_input().split())
	c[i]=(a,b)
c.sort()
i,j=0,0
while i<=K-1:
	i+=c[j][1]
	if i>=K:break
	j+=1
print c[j][0]
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = {}
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS and j + k < N:
                ANS[j+k] = i
                count += 1
    if count == N : break

for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

K = int(input())

import math
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += math.gcd(math.gcd(i,j),k)
print(ans)

### FIXED CODE ###

K = int(input())

import math
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += math.gcd(math.gcd(i,j),k)
print(ans)
### BUGGY CODE ###

S = list(input())
S = [int(s) for s in S]
N = len(S)
#print('S:', S)

count=0
i=1
while True:
    #print(S,i)
    if len(S)==0 or len(S)==1 or sum(S)==len(S) or sum(S)==0 :
        break

    elif S[i-1] != S[i]:
        del S[i-1]
        del S[i-1]
        count+=1
        i=1
    else:
        i+=1

print(count*2)

### FIXED CODE ###

S = list(input())
S = [int(s) for s in S]
#N = len(S)
#print('S:', S)

print((min(S.count(0), S.count(1)))*2)
### BUGGY CODE ###

import copy

n = int(input())
a_list = []
out_list = []

for i in range(n):
    a_list.append(int(input()))

is_max = False
#print(a_list)    
for i in range(n):
    if not is_max:
        a_copy = copy.copy(a_list)
        a_copy.pop(i)
        #print(a_copy)
        a_max = max(a_copy)
        #print(a_max)
        out_list.append(a_max)
        if a_list[i] == a_max:
            is_max = True
            out_list += [a_max for i in range(n-i-1)]
#print(out_list)        
print("\n".join(map(str, out_list)))

### FIXED CODE ###


n = int(input())
a = []

for i in range(n):
    a.append(int(input()))
    
a_copy = list(a)
a.sort(reverse=True)

max_1 = a[0]
max_count = a.count(max_1)

for i in a:
    if i < max_1:
        max_2 = i
        break
        
for a in a_copy:
    if a == max_1 and max_count == 1:
        print(max_2)
    else:
        print(max_1)
### BUGGY CODE ###

# coding:utf-8

n, y = map(int, input().split())
dist_list = [abs(x-y) for x in map(int, input().split())]

d_kouho_max = max(dist_list)

for d in reversed(range(d_kouho_max)):
    able = True
    for dist in dist_list:
        if dist%(d+1) == 0:
            pass
        else:
            able = False
            break
    if(able):
        d_max = d+1
        break

print(d_max)

### FIXED CODE ###

# coding:utf-8

from fractions import gcd 

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

dist_list = [abs(x-y) for x in map(int, input().split())]

if n == 1:
    d = dist_list[0]
else:
    d = gcd(dist_list[1], dist_list[0])
    for i in range(n-2):
        d = gcd(d, dist_list[i+1])

print(d)
### BUGGY CODE ###

a,b,k = map(int, input().split())

A = a
B = b
i = 1
while True:
  if A >= 1:
    A += -1
  else:
    if B >= 1:
      B += -1
    else:
      print(0, 0)
  if i == k:
    print(A, B)
    exit()
  else:
    i  += 1

### FIXED CODE ###

a,b,k = map(int, input().split())

if a >= k:
  print(a-k,b)
elif a<k and b>= k-a:
  print(0,b-(k-a))
else:
  print(0,0)
### 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 i in range(K+1):
    for j in range(K+1):
            if 0<=S-i-j<=K:
                count += 1
print(count)
### BUGGY CODE ###

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



### FIXED CODE ###


n = int(input())
a = list(map(int,input().split()))
b = {0:0}
c = 0
for i in range(n):
    c = c+a[i]
    if c in b:
        b[c] += 1
    else:
        b[c] = 0
d = list(b.values())
ans = 0
for i in d:
    ans+= ((i+1)*i)//2
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
dp = [[0]*13 for i in range(N+1)]

mod = 10**9 + 7
dp[0][0] = 1
for i, x in enumerate(S):
    for j in range(13):
        if x != '?':
            x = int(x)
            k = j*10 + x
            dp[i+1][k % 13] += dp[i][j]
            dp[i+1][k % 13] %= mod
        else:
            for k in range(10):
                dp[i+1][(j*10+k) % 13] += dp[i][j]
                dp[i+1][(j*10+k) % 13] %= mod
print(dp[-1][5])


### FIXED CODE ###

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

N,M = map(int,input().split())

tmp = M//N
ans = 0
for i in range(1,tmp+1):
    if M%i==0:
        ans = i
print(ans)

### FIXED CODE ###

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

a = (m//n)

for i in range(a, 0, -1):
    if m%i == 0:
        print(i)
        break
### BUGGY CODE ###

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

a.sort()
bc = [list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x:x[1],reverse=True)
l = []
[l.extend([i[1]] * i[0]) for i in bc]

for i in range(min(len(a),len(l))):
    a[i]=max(a[i],l[i])
print(sum(a))

### FIXED CODE ###

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

a.sort()
bc = [list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x:x[1],reverse=True)
l = []
for i in bc:
    l.extend([i[1]] * i[0])
    if len(l) > len(a):
        break

for i in range(min(len(a),len(l))):
    a[i] = max(a[i],l[i])
print(sum(a))
### BUGGY CODE ###

n, k = map(int, input().split())
ans = n

while n > 0:
  if k == 1:
    ans = 0
    break
    
  ans = min(ans, abs(n - k))
  n -= k

print(ans)

### FIXED CODE ###

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

ans = min(n % k, k - n % k)

print(ans)