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

import itertools
N, Ma, Mb = map(int, input().split())
L = [[int(i) for i in input().split()] for _ in range(N)]

inf = N * 101
dp = [[[inf for _ in range(N*10+11)] for _ in range(N*10+11)] for _ in range(N+1)]

dp[0][0][0] = 0
cmb = itertools.product(range(N), range(N*10), range(N*10))
for i, j, k in cmb:
    dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
    dp[i+1][j+L[i][0]][k+L[i][1]] = min(dp[i+1][j+L[i][0]][k+L[i][1]], dp[i][j][k] + L[i][2])
ans = inf
for i in range(1, N*10//max(Ma, Mb)):
    ans = min(ans, dp[N][i*Ma][i*Mb])

if ans == inf:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import itertools
N, Ma, Mb = map(int, input().split())
L = [[int(i) for i in input().split()] for _ in range(N)]

inf = N * 101
dp = [[[inf for _ in range(N*10+11)] for _ in range(N*10+11)] for _ in range(N+1)]

dp[0][0][0] = 0
cmb = itertools.product(range(N), range(N*10), range(N*10))
for i, j, k in cmb:
    dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
    dp[i+1][j+L[i][0]][k+L[i][1]] = min(dp[i+1][j+L[i][0]][k+L[i][1]], dp[i][j][k] + L[i][2])
ans = inf
for i in range(1, N*10//max(Ma, Mb)):
    ans = min(ans, dp[N][i*Ma][i*Mb])

if ans == inf:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n, s = [int(i) for i in  raw_input().split()]
weights = []
values = []

for _ in xrange(n):
    w, v = [int(i) for i in raw_input().split()]
    weights.append(w)
    values.append(v)

def knapsack(weights, values, limit):
    n = len(weights)
    # f = [[0 for _ in xrange(limit+1)] for _ in xrange(n)]

    prev = [0 for _ in xrange(limit+1)]

    if weights[0] <= limit:
        for w in xrange(weights[0], limit+1):
            prev[w] = values[0]

    for i in xrange(1, n):
        # print prev
        current = [0] * (limit+1)
        for w in xrange(1, limit+1):
            current[w] = max(prev[w], current[w])
            if weights[i] <= w:
                current[w] = max(current[w], prev[w-weights[i]] + values[i])
        prev = list(current)

    return prev[-1]

# weights = [10, 20, 30]
# values = [60, 100, 120]
print(knapsack(weights, values, s))

### FIXED CODE ###

n, s = [int(i) for i in  raw_input().split()]
weights = []
values = []

for _ in xrange(n):
    w, v = [int(i) for i in raw_input().split()]
    weights.append(w)
    values.append(v)

def knapsack(weights, values, limit):
    n = len(weights)
    # f = [[0 for _ in xrange(limit+1)] for _ in xrange(n)]

    prev = [0 for _ in xrange(limit+1)]

    if weights[0] <= limit:
        for w in xrange(weights[0], limit+1):
            prev[w] = values[0]

    for i in xrange(1, n):
        # print prev
        current = [0] * (limit+1)
        for w in xrange(1, limit+1):
            current[w] = max(prev[w], current[w])
            if weights[i] <= w:
                current[w] = max(current[w], prev[w-weights[i]] + values[i])
        prev = list(current)

    return prev[-1]

# weights = [10, 20, 30]
# values = [60, 100, 120]
print(knapsack(weights, values, s))
### BUGGY CODE ###

from collections import deque
N, X, Y = map(int, input().split())

graph = []
graph.append([1])
for i in range(1, N-1):
    graph.append([i-1, i+1])
graph.append([N-2])

graph[X-1].append(Y-1)
graph[Y-1].append(X-1)

cnt = [0]*N

def bfs(num):
    dq = deque()
    dq.append((num,0))
    visited = [-1]*N
    visited[num] = 0
    while dq:
        a, b = dq.popleft()
        for i in graph[a]:
            if visited[i] == -1:
                visited[i] = b+1
                dq.append((i, b+1))

    for i in visited:
        if i > 0:
            cnt[i] += 1
    return cnt
for i in range(N): bfs(i)
for i in cnt[1:]:
    print(i//2)


### FIXED CODE ###

from collections import deque
N, X, Y = map(int, input().split())

graph = []
graph.append([1])
for i in range(1, N-1):
    graph.append([i-1, i+1])
graph.append([N-2])

graph[X-1].append(Y-1)
graph[Y-1].append(X-1)

cnt = [0]*N

def bfs(num):
    dq = deque()
    dq.append((num,0))
    visited = [-1]*N
    visited[num] = 0
    while dq:
        a, b = dq.popleft()
        for i in graph[a]:
            if visited[i] == -1:
                visited[i] = b+1
                dq.append((i, b+1))
    return visited

vx = bfs(X-1)
vy = bfs(Y-1)

for i in range(0,N-1):
    for j in range(i+1, N):
        if abs(X-1-i) <= abs(Y-1-i):
            idx = min(j-i, abs(X-1-i) + vx[j])
        else:
            idx = min(j-i, abs(Y-1-i) + vy[j])
        cnt[idx] += 1
    
for i in cnt[1:]:print(i)
### BUGGY CODE ###

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

count = 0

# table2jou = []
# for mi in range(m + 1):
#     table2jou.append(pow(mi, 2))

# tablef = []
# for mi in range(m + 1):
#     # tablef.append(table2jou[mi] % m)
#     tablef.append(pow(mi, 2, m))


count = x
pre_an = x
his = [x]
for ni in range(2, n + 1):
    # an = tablef[pre_an]
    an = pow(pre_an, 2, m)
    if an in his:
        leftnum = n - ni + 1
        start = his.index(an)
        end = leftnum % (len(his) - start) + start
        loopnum = leftnum // (len(his) - start)
        count = count + sum(his[start: end])
        count = count + sum(his[start:]) * loopnum
        break
    his.append(an)
    count = count + an
    pre_an = an

print(count)


### FIXED CODE ###

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

count = 0

# table2jou = []
# for mi in range(m + 1):
#     table2jou.append(pow(mi, 2))

# tablef = []
# for mi in range(m + 1):
#     # tablef.append(table2jou[mi] % m)
#     tablef.append(pow(mi, 2, m))

is_used = [0] * (m + 1)

count = x
pre_an = x
his = [x]
for ni in range(2, n + 1):
    # an = tablef[pre_an]
    an = pow(pre_an, 2, m)
    if is_used[an] == 1:
        leftnum = n - ni + 1
        start = his.index(an)
        end = leftnum % (len(his) - start) + start
        loopnum = leftnum // (len(his) - start)
        count = count + sum(his[start: end])
        count = count + sum(his[start:]) * loopnum
        break
    his.append(an)
    is_used[an] = 1
    count = count + an
    pre_an = an

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

def main():
	s = int(input())
	a = list(map(int,input().split()))
	import collections
	for i in range(s):
		# print("i is {}".format(i))
		c = collections.Counter(a[0:i] + a[i+1:s])
		Set = set(a[0:i] + a[i+1:s])
		# print("Set is {}".format(Set),"c is {}".format(c))
		ans = 0
		for t in Set:
			# print("t is {}".format(t))
			if c[t] > 1:
				ct = int(c[t])
				ans += (ct * (ct-1))/2
		print(int(ans))

if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	import collections
	s = int(input())
	a = list(map(int,input().split()))
	ac = collections.Counter(a)
	ans = 0
	for i in set(ac):
		at = ac[i]
		ans += (at * (at-1))/2
	for t in a:
		ans_print = ans -((ac[t] * (ac[t] -1))/2) + (((ac[t]-1) * ((ac[t]-1)-1))/2)
		print(int(ans_print))
if __name__ == '__main__':
	main()
### BUGGY CODE ###

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

from bisect import bisect_left, bisect_right

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    A.sort()
    B.sort()
    C.sort()

    ret = 0
    for a in A:
        ib = bisect_right(B,a)
        for b in B[ib:]:
            ic = bisect_right(C,b)
            ret += N - ic
    print(ret)

if __name__ == '__main__':
    main()

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
B.sort()
C=list(map(int,input().split()))
C.sort()
from bisect import bisect_right
ret=0
Cb=[0]*(N+1)
for i in range(N):
  Cb[i]=N-bisect_right(C,B[i])
for i in range(N-1,-1,-1):
  Cb[i]+=Cb[i+1]
for a in A:
  bi=bisect_right(B,a)
  ret+=Cb[bi]
print(ret)
### BUGGY CODE ###

x,y = map(int,input().split(" "))

#xの約数を求める
list_x = [i for i in range(1,x+1) if x % i == 0]

#yの約数を求める
list_y = [j for j in range(1,y+1) if y % j == 0]

x_set = set(list_x)
y_set = set(list_y)

print(max(list(x_set & y_set)))



### FIXED CODE ###

x,y = map(int,input().split(" "))

while y != 0:
    x,y=y,x%y

print(x)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[-1]*W for _ in range(H)]
    from collections import deque
    queue = deque()

    for i in range(H):
        st = input()
        for j in range(W):
            if st[j] == "#":
                queue.append((i,j,0))

    while queue:
        i,j,count = queue.popleft()

        if 0<=i<H and 0<=j<W and isVisited[i][j] == -1:
            isVisited[i][j] = count
            for ix,iy in [(0,1),(1,0),(-1,0),(0,-1)]:
               queue.append((i+ix,j+iy,count+1))
 
    answer = 0
    for i in range(H):
        answer = max(answer,max(isVisited[i]))
    print(answer)
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[False]*W for _ in range(H)]
    queue = deque()

    for i in range(H):
        st = input()
        for j in range(W):
            if st[j] == "#":
                queue.append((i,j))

    answer = 0
    a =  [(0,1),(1,0),(-1,0),(0,-1)]
    while True:
        nqueue = deque()
        while queue:
            i,j = queue.popleft()

            if not isVisited[i][j]:
                isVisited[i][j] = True
                for ix,iy in a:
                    if 0<=i+ix<H and 0<=j+iy<W:
                        nqueue.append((i+ix,j+iy))
        
        if nqueue:
            answer += 1
            queue = nqueue
        else:
            break
 
    print(max(answer-1,0))
    return

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

a = int(input())
b = list(map(int, input().split()))
b.sort()
l = 0
for i in range(1,a+1):
     l = len(b)
     b = [j for j in b if j != i]
     print(l-len(b))

### FIXED CODE ###

def main():
    a = int(input())
    b = list(map(int, input().split()))
    c = [0]*a
    for i in b:
        c[i-1] += 1
    for j in c:
        print(j)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# coding: utf-8
# Your code here!
def dfs(num,hiyo):
    ans[num]=hiyo
    for item in way[num]:
        if ans[item]==-1:
            dfs(item,hiyo+cost[num][item])
    
    return 

N=int(input())

way=[[] for i in range(N)]
cost=[[0]*N for i in range(N)]
ans=[-1]*N

for _ in range(N-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    way[u].append(v)
    way[v].append(u)
    cost[u][v]=w
    cost[v][u]=w

dfs(0,0)

for item in ans:
    print(item%2)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
 
sys.setrecursionlimit(10**7)

def dfs(num,hiyo):
    ans[num]=hiyo
    for to,cos in way[num]:
        if ans[to]==-1:
            dfs(to,hiyo+cos)
    
    return 

N=int(input())

way=[[] for i in range(N)]
ans=[-1]*N

for _ in range(N-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    way[u].append([v,w])
    way[v].append([u,w])

#lis.sort(key=lambda x:(x[0],x[1]))

dfs(0,0)
#print(ans)
for item in ans:
    print(item%2)
### BUGGY CODE ###

L=int(input())
ans=0
tmp=0
#分割数
d=1000
l=5
L_=int(L**(1/3))
for i in range(max(0,int(L_-l)*d),int(L_+l)*d):
  for j in range(max(0,int(L_-l)*d-i),int(L_+l)*d-i):
    tmp=(i/d)*(j/d)*(L-(i/d)-(j/d))
    ans=max(ans,tmp,0)
print(ans)

### FIXED CODE ###

L=int(input())
print((L**3)/27)
### BUGGY CODE ###

def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    
#    print(A)
    result = 0
    s = [A[0]]
    for i in range(1, N):
        s.append(s[i - 1] + A[i])
#    print(s)
    
    for i in range(N):
        if(s[i] == 0):
            result += 1
        for j in range(i):
#            print(s[i] - s[j])
            if((s[i] - s[j]) == 0):
                result += 1
                
#    for nc_len in range(1, N + 1):
#        for i in range(N - nc_len + 1):
##            print(A[i : i + nc_len])
#            if(sum(A[i : i + nc_len]) == 0):
#                result += 1
    
    print(result)
    
if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    
    result = 0
    s = [0]
    for i in range(N):
        s.append(s[-1] + A[i])
        
    s.sort()
#    print(s)
    
    count = 1
    for i in range(N):
        if(s[i] == s[i+1]):
            count += 1
        else:
            result += count * (count -1 ) // 2
            count = 1
    result += count * (count -1 ) // 2
    print(result)
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

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

a = [1+(i-1)/2 for i in p]
ans = 0
for i in range(n-k+1):
    ans = max(ans, sum(a[i:i+k]))
print(ans)

### FIXED CODE ###

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

a = [1+(i-1)/2 for i in p]
l = sum(a[:k])
ans = l
for i in range(1, n-k+1):
    l = l-a[i-1]+a[k+i-1]
    ans = max(ans, l)
print(ans)
### BUGGY CODE ###

import bisect
def reversed_num(num):
  num_len=len(bin(num))-2
  f=2**num_len-1
  return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
  x=reversed_num(number.pop())+1
  if len(number)==0:
    break
  y=bisect.bisect_left(number,x)
  if x>number[-1]:
    y-=1
  if number[y] ==x:
    number.pop(y)
    count+=1
print(count)

### FIXED CODE ###

import bisect
def reversed_num(num):
  num_len=len(bin(num))-2
  f=2**num_len-1
  return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
  k=number.pop()
  if len(number)==0:
    break
  if k==int(k):
    x=reversed_num(k)+1
    y=bisect.bisect_left(number,x)
    if x>number[-1]:
      y-=1
    if number[y] ==x:
      number[y]-=0.5
      count+=1
print(count)
### BUGGY CODE ###

from bisect import *
N,M,Q=map(int,input().split())
LR=[list(map(int,input().split())) for i in range(M)]
PQ=[list(map(int,input().split())) for i in range(Q)]
data=[[] for i in range(N+1)]
for l,r in LR:
    data[l].append(r)
data=[sorted(data[i]) for i in range(N+1)]
for p,q in PQ:
    count=0
    for i in range(p,q+1):
        count+=bisect_right(data[i],q)
    print(count)


### FIXED CODE ###

from bisect import *
N,M,Q=map(int,input().split())
LR=[list(map(int,input().split())) for i in range(M)]
PQ=[list(map(int,input().split())) for i in range(Q)]
data=[[] for i in range(N+1)]
for l,r in LR:
    data[l].append(r)
for i in range(1,N):
    data[i].sort()

data2=[[0] for i in range(N+1)]
for i in range(1,N+1):
    for c in range(1,N+1):
        data2[i].append(bisect_right(data[i],c))
#print(data2)
for p,q in PQ:
    count=0
    for i in range(p,q+1):
        count+=data2[i][q]
    print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
b=[None]*m
c=[None]*m
for i in range(m):
    b[i],c[i] = map(int, input().split(" "))
for bb,cc in zip(b,c):
    if cc < a[0]:
        continue
    a[0:bb] = list(map(lambda x: x if cc < x else cc, a[0:bb]))
    a.sort()
print(sum(a))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        break
for i in range(n):
    if len(l) <= i or l[i] <= a[i]:
        break
    a[i] = l[i]
print(sum(a))
### BUGGY CODE ###

import math
n, m = input().split()
N = int(n)
M = int(m)

A = [int(a) for a in input().split()]

for i in range(M):
    k = A.index(max(A))
    A[k] = math.floor(A[k] / 2)

print(sum(A))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
it = 0
for i in range(M):
    A[it]=A[it]//2
    if it<N-1:
        if A[it]<A[it+1] and A[0]<A[it+1]:
            it+=1
        else:
            A.sort(reverse = True)
            it = 0
    if it == N-1:
        A.sort(reverse = True)
        it = 0
print(sum(A))
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

K = int(input())
S = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            S += gcd(i,j,k)

print(S)


### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

K = int(input())
S = 0

for i in range(1,K+1):
    for j in range(i+1,K+1):
        for k in range(j+1,K+1):
            S += gcd(i,j,k)*6

for i in range(1,K+1):
    for j in range(i+1,K+1):
        S+= gcd(i,j)*6

for i in range(1,K+1):
    S+=i

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

def main():
    n = int(input())
    s = [["" for j in range(10)] for i in range(n)]

    for i in range(n):
        s[i] = list(input())
        s[i].sort()

    print(int(count_anagram(s[0], s[1:], 0)))


def count_anagram(s, str_list, total):
    cnt = 0
    tmp = []
    for i, t in enumerate(str_list):
        if s == t:
            cnt += 1
            tmp.append(i)
    if cnt > 0:
        total += (cnt+1) * cnt / 2
        for i in reversed(tmp):
            str_list.pop(i)

    if str_list:
        return count_anagram(str_list[0], str_list[1:], total)
    else:
        return total


if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections

n = int(input())
s = ["".join(sorted(input())) for i in range(n)]

counter = collections.Counter(s)

ans = 0
for i in counter.values():
   if i > 0:
        ans += i * (i - 1) // 2

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

if __name__=='__main__':
    from collections import deque
    h, w, k = map(int, input().split())
    maze = [input() for _ in range(h)]
    visited = [[-1]*w for j in range(h)]
    for i in range(h):
        if 'S' in maze[i]:
            sy, sx = i, maze[i].index('S')
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    r = 10**18
    while queue:
        y, x = queue.popleft()
        r = min(r, y, x, h-1-y, w-1-x)
        if visited[y][x] == k: continue
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+i, x+j
            if new_y < 0 or new_y >= h: continue
            if new_x < 0 or new_x >= w: continue
            if maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    print(1 -(-r // k))

### FIXED CODE ###

from collections import deque
h, w, k = map(int, input().split())
maze = [input() for _ in range(h)]
visited = [[-1]*w for j in range(h)]
for i in range(h):
    if 'S' in maze[i]:
        sy, sx = i, maze[i].index('S')
queue = deque([[sy, sx]])
visited[sy][sx] = 0
r = 10**18
while queue:
    y, x = queue.popleft()
    r = min(r, y, x, h-1-y, w-1-x)
    if visited[y][x] == k: continue
    for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y+i, x+j
        if new_y < 0 or new_y >= h: continue
        if new_x < 0 or new_x >= w: continue
        if maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
            visited[new_y][new_x] = visited[y][x] + 1
            queue.append([new_y, new_x])
print(1 -(-r // k))
### BUGGY CODE ###

import numpy as np
N=int(input())
L=np.array(list(map(int, input().split())))
S=0
L.sort()
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if L[i]+L[j]>L[k]:
                S+=1
            else:
                break
print(S)

### FIXED CODE ###

import bisect

N=int(input())
L=sorted(list(map(int, input().split())))
S=0

for i in range(N):
    for j in range(i+1,N):
        S+=bisect.bisect_left(L,L[i]+L[j])-j-1
print(S)
### BUGGY CODE ###

from collections import Counter
import json
import hashlib

N = int(input())
c = []

for _ in range(N):
    s = input()
    d = dict(Counter(s))
    ds = sorted(d.items(), key=lambda x:x[0])
    h = hashlib.md5(json.dumps(ds).encode("utf-8")).hexdigest()
    c.append(h)

sum = 0
for i , v in Counter(c).items():
    sum += (v*(v-1)//2)
print(sum)


### FIXED CODE ###

from collections import Counter
import json

N = int(input())
ss = []
c = []

for _ in range(N):
    s = input()
    ss.append("".join(sorted(s)))

sum = 0

for i , v in Counter(ss).items():
    sum += (v*(v-1)//2)
print(sum)
### BUGGY CODE ###

s = list(input())

MOD = pow(10, 9) + 7

n = len(s)
s.reverse()

dp = [[0] * 13 for _ in range(n)]

#r = list(range(10))

#init
if s[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    q = int(s[0])
    dp[0][q] = 1

for i in range(1, n):

    # for l in range(10):
    #     r[l] = r[l] * 10 % 13

    #print(r)

    if s[i] == "?":
        for j in range(10):
            q = j * pow(10, i, 13) % 13
            for k in range(13):
                dp[i][k] += dp[i-1][k-q]
    
    else:
        q = int(s[i]) * pow(10, i, 13) % 13
        #print(q)
        for k in range(13):
            dp[i][k] += dp[i-1][k-q]
    #print(dp[i])

print(dp[n-1][5] % MOD)

### FIXED CODE ###

s = list(input())

MOD = pow(10, 9) + 7

n = len(s)

dp = [[0] * 13 for _ in range(n)]

#r = list(range(10))

#init
if s[-1] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    q = int(s[-1])
    dp[0][q] = 1

r = 1

for i in range(1, n):
    r = r * 10 % 13
    # for l in range(10):
    #     r[l] = r[l] * 10 % 13

    #print(r)

    if s[n-i-1] == "?":
        for j in range(10):
            q = j * r % 13
            for k in range(13):
                dp[i][k] += dp[i-1][k-q] % MOD
    
    else:
        q = int(s[n-i-1]) * r % 13
        #print(q)
        for k in range(13):
            dp[i][k] += dp[i-1][k-q] % MOD
    #print(dp[i])

print(dp[n-1][5] % MOD)
### BUGGY CODE ###

import bisect
import copy
n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
ng=-1
ok=A[-1]*2+1
B=[0]*n
C=[0]*n
while ok-ng>1:
  mid=(ok+ng)//2
  d=0
  for i in range(n):
    c=n-bisect.bisect_right(A,mid-A[i],lo=0,hi=len(A))
    B[i]=c
    d=d+c
  if d<m:
    ok=mid
    C=copy.deepcopy(B)
  else:
    ng=mid
D=[0]
for i in range(n):
  D.append(D[-1]+A[n-i-1])
ans=0
for i in range(n):
  ans=ans+A[i]*C[i]+D[C[i]]
ans=ans+(m-sum(C))*ok
print(ans)

### FIXED CODE ###

import bisect
n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
ng=-1
ok=A[-1]*2+1
B=[[0]*n for k in range(2)]
ii=0
while ok-ng>1:
  mid=(ok+ng)//2
  d=0
  for i in range(n):
    c=n-bisect.bisect_right(A,mid-A[i],lo=0,hi=len(A))
    B[ii][i]=c
    d=d+c
  if d<m:
    ok=mid
    ii=(ii+1)%2
  else:
    ng=mid
D=[0]
for i in range(n):
  D.append(D[-1]+A[n-i-1])
ans=0
for i in range(n):
  x=B[(ii+1)%2][i]
  ans=ans+A[i]*x+D[x]
ans=ans+(m-sum(B[(ii+1)%2]))*ok
print(ans)
### BUGGY CODE ###

h,w,m = map(int, input().split())
row = [0]*(h+1)
rn = [[] for _ in range(h+1)]
col = [0]*(w+1)
cn = [[] for _ in range(w+1)]
data = []
for _ in range(m):
  hd,wd = map(int, input().split())
  row[hd] += 1
  rn[hd].append(wd)
  col[wd] += 1
  cn[wd].append(hd)

cm = max(col)
rm = max(row)
ri = [x for x,y in enumerate(row) if y == rm]
ci = [x for x,y in enumerate(col) if y == cm]
ans = -1
for c in ci:
  for r in ri:
    if c not in set(rn[r]):
      ans = max(ans,cm+rm)
      print(ans)
      exit()
ans = cm+rm-1
print(ans)

### FIXED CODE ###

h,w,m = map(int, input().split())
row = [0]*(h+1)
rn = [[] for _ in range(h+1)]
col = [0]*(w+1)
cn = [[] for _ in range(w+1)]
data = []
for _ in range(m):
  hd,wd = map(int, input().split())
  row[hd] += 1
  rn[hd].append(wd)
  col[wd] += 1
  cn[wd].append(hd)

cm = max(col)
rm = max(row)
ri = [x for x,y in enumerate(row) if y == rm]
ci = [x for x,y in enumerate(col) if y == cm]
for r in ri:
  rs = set(rn[r])
  for c in ci:
    if c not in rs:
      ans = cm+rm
      print(ans)
      exit()
ans = cm+rm-1
print(ans)