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

from heapq import*
n,*a=map(int,open(0).read().split())
#print(a)
ans=-float("inf")
for i in range(n,2*n+1):
    score=0
    tmp=a[:i]
    heapify(tmp)
#    print(tmp)
    for j in range(i-n):
        heappop(tmp)
    score+=sum(tmp)
    tmp=a[i:]
    heapify(tmp)
#    print(tmp)
    score-=sum(heappop(tmp)for r in range(n))

    ans=max(score,ans)
print(ans)

### FIXED CODE ###

from heapq import*
n,*a=map(int,open(0).read().split())
b=a[:n]
c=[-i for i in a[n:][::-1]]
d=c[:n]
e=c[n:]
heapify(b)
heapify(d)
s=sum(b)
t=sum(d)
red=[s]
blue=[t]
for i in range(n,n*2):
    s+=a[i]-heappushpop(b,a[i])
    t+=c[i]-heappushpop(d,c[i])
    red+=[s]
    blue+=[t]
print(max(map(sum,zip(red,blue[::-1]))))

#あｈｊｆｋぁｄｓｈｆｌｋじゃｇはｌｋｊｄｊｇｌｋ；あｊｄｇｌｋ；あｄｓｊｇｌ；あｊｓｄｇｌｋ；あｊｓｄｇｌ；かｓ
### BUGGY CODE ###

from functools import reduce
import fractions
import sys
sys.setrecursionlimit(20000)

def lcm_base(a, b):
    return a * b / fractions.gcd(a, b)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
A = sorted(list(map(int, input().split())))
B = [0 for _ in range(N)]
mod = 10**9+7

ll = lcm_list(A)
ans = 0
for i in range(N):
    B[i] = (ll//A[i])%mod
    ans += B[i]
print(int(ans%mod))


### FIXED CODE ###

from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%mod)
### BUGGY CODE ###

import math
N = int(input())
L = [[int(i) for i in input().split()] for _ in range(N)]
T = 1
A = 1
for l in L:
    t, a = l[0], l[1]
    while(T > t or A > a):
        t += l[0]
        a += l[1]
    else:
        T, A = t, a
print(T+A)


### FIXED CODE ###

from math import ceil
N = int(input())
L = [[int(i) for i in input().split()] for _ in range(N)]
T = 1
A = 1
for l in L:
    k = max((T+l[0]-1)//l[0], (A+l[1]-1)//l[1])
    T = k * l[0]
    A = k * l[1]
print(T+A)
### BUGGY CODE ###

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return x

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
		return


n, m = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(m)]
x = [xy[i][0] for i in range(m)]
y = [xy[i][1] for i in range(m)]

uf = UnionFind(n)

for i in range(m):
	uf.union(x[i] - 1, y[i] - 1)

ans = 0
for i in range(n):
	if uf.find(p[i] - 1) == uf.find(i):
		ans += 1

print(ans)

### FIXED CODE ###

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x]) #xをxの根に直接つなぐ
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		else:
			st1 = self.table[s1]
			st2 = self.table[s2]
			if st1 > st2:
				self.table[s2] = s1
			elif st1 < st2:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

for i in range(m):
	x, y = map(int, input().split())
	uf.union(x - 1, y - 1)

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

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

# coding: utf-8
# Your code here!
import itertools

N,L= map(int,input().split())
S = [input() for i in range(N)]
ans= ""
for i in S:
    ans = ans+i 
for i in itertools.permutations(S):
    tmp = ""
    for j in i:
        tmp = tmp + j
    if tmp < ans:
        ans = tmp
print(ans)
 

### FIXED CODE ###

N,L= map(int,input().split())
S = [input() for i in range(N)]
S.sort()
for a in S:
    print(a,end ="")
### BUGGY CODE ###

s = input()
cnt = 0
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        if int(s[i:j]) % 2019 == 0:
            cnt += 1
print(cnt)       

### FIXED CODE ###

M = 2019
s = input()
tot, ten, ans = 0, 1, 0
cnt = [0] * M
for si in s[::-1]:
    cnt[tot] += 1
    tot += int(si) * ten
    tot %= M
    ans += cnt[tot]
    ten *= 10
    ten %= M
print(ans)
### BUGGY CODE ###

N= int(input())
H = [int(i) for i in input().split( )]


for i in range(1,N+1):
    for j in range(N):
        if H[j] == i:
            print(j+1)


### FIXED CODE ###

N= int(input())
H = [int(i) for i in input().split( )]
J = [0]*N
for i in range(N):
    J[H[i]-1] = i
for j in range(N):
    print(J[j]+1)
### BUGGY CODE ###

# K回前と現在の問いが同じだったら0点

str1 = input().split(" ")
str2 = input().split(" ")
t = input()

n = int(str1[0])
k = int(str1[1])

r = int(str2[0])
s = int(str2[1])
p = int(str2[2])

skill = {"r":p,"s":r,"p":s}

result = 0
hoge = 0
douchilist = []
for i in range(0,n):
    if i < k:
        continue
    if t[i] == t[i-k] and i-k not in douchilist:
        hoge += skill[t[i]]
        douchilist.append(i)
        continue

pres = p * t.count("r")
rres = r * t.count("s")
sres = s * t.count("p")


print(pres + rres + sres - hoge)

### FIXED CODE ###

# K回前と現在の問いが同じだったら0点

str1 = input().split(" ")
str2 = input().split(" ")
t = list(input())

n = int(str1[0])
k = int(str1[1])

r = int(str2[0])
s = int(str2[1])
p = int(str2[2])

result = 0
hoge = 0
for i in range(0,n):
    if i < k:
        continue

    j = i-k
    if t[i] == t[j]:
        t[i] = "_"

pres = p * t.count("r")
rres = r * t.count("s")
sres = s * t.count("p")

print(pres + rres + sres)
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int , input().split()))
a = collections.Counter(A)
S = len(list(set(A)))
k = 0
for j in range (S):
    b = a.most_common()[j][1]
    k = b * (b-1)/2 + k

for i in range(N):
    s = A[i]
    p = a[s]
    print(int(k - p +1))    


### FIXED CODE ###

import collections
N = int(input())
A = list(map(int , input().split()))
a = collections.Counter(A)
k = 0
def comb(n):
    return n * (n - 1) // 2
for j in a.values():
    k += comb(j)
    
for i in range(N):
    s = A[i]
    p = a[s]
    print(int(k - p + 1))
### BUGGY CODE ###

a = int(input())
min = 99999999999999
if a % 10 == 0:
    print(10)
else:
    for i in range(1, a):
        c = 0
        for j in range(i, a):
            if i + j == a:
                x = i
                y = j
                while (x > 0):
                    c += x % 10
                    x = x // 10
                while (y > 0):
                    c += y % 10
                    y = y // 10
                if min > c:
                    min = c
    print(min)

### FIXED CODE ###

a = int(input())
if a % 10 == 0:
    print(10)
else:
    c = 0
    while (a > 0):
        c += a % 10
        a = a//10
    print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

S = input().rstrip()
Q = int(input())
query = [list(input().split()) for _ in range(Q)]

ans = list(S)
for i in range(Q):
    if query[i][0] == '1':
        ans.reverse()
        continue
    elif query[i][0] == '2':
        f = query[i][1]
        c = query[i][2].rstrip()
        if f == '1':
            ans = [c] + ans
        else:
            ans = ans + [c]
print(''.join(ans))


### FIXED CODE ###

import sys
input = sys.stdin.readline

S = input().rstrip()
Q = int(input())
head = ''
tail = ''
rev = False

for _ in range(Q):
    query = list(input().split())
    if query[0] == '1':
        if rev:
            rev = False
        else:
            rev = True
    elif query[0] == '2':
        f = query[1]
        c = query[2].rstrip()
        if f == '1':
            if rev:
                tail = tail + c
            else:
                head = c + head
        else:
            if rev:
                head = c + head
            else:
                tail = tail + c
if rev:
    tmp = head + S + tail
    print(tmp[::-1])
else:
    print(head + S + tail)
### BUGGY CODE ###

from functools import reduce
import math
K = int(input())


def gcd(a, b, c):
    mi = min(a, b, c)
    for k in range(mi, 0, -1):
        if a % k == 0 and b % k == 0 and c % k == 0:
            return k


ans = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            ans += gcd(a, b, c)

print(ans)


### FIXED CODE ###

from fractions import gcd
K = int(input())


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


ans = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            ans += gcd(gcd(a, b), c)

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

N,K = map(int,input().split())
asiba = list(map(int,input().split()))
dp =[10**10] *N

#初期化
dp[0]=0
dp[1]=abs(asiba[1]-asiba[0])

for i in range(2,N):
    for j in range(1,min(i+1,K+1)):
        dp[i] = min(dp[i-j]+abs(asiba[i]-asiba[i-j]),dp[i])
print(dp[N-1])

### FIXED CODE ###

def main():
  n, k = [int(e) for e in input().split()]
  h = [int(e) for e in input().split()]
  cost = [0] * n
  for i in range(1, n):
    cost[i] = min(abs(h[i] - h[j]) + cost[j] for j in range(max(0, i - k), i))
  print(cost[n - 1])
main()
### BUGGY CODE ###

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

### FIXED CODE ###

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

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])




### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])
### BUGGY CODE ###

n = int(input())
s = list(input())

count = 0
for i in range(0, n-2):
    for j in range(i+1,n-1):
        if s[i] == s[j]:
            count += 0
        else:
            for k in range(j+1,n):
                if s[i] == s[k] or s[j] == s[k]:
                    count +=0
                elif j-i == k-j:
                    count +=0
                else:
                    count +=1

print(count)

### FIXED CODE ###

import math
n =  int(input())
s = list(input())

upper = s.count("R")*s.count("G")*s.count("B")

def counting(x):
  count = 0
  for i in range(1, math.ceil(x/2)):
    if s[x-1]!=s[x-1-i] and s[x-1-i]!=s[x-1-2*i] and s[x-1-2*i]!=s[x-1]:
      count += 1
    else:
      count += 0
  return count

if n>=3:
  minus = [0]*(n+1)
  if s[0]!=s[1] and s[1]!=s[2] and s[2]!=s[0]:
    minus [3] = 1
  else:
    minus [3] = 0
  for i in range(3,n):
    minus[i+1] = minus[i]+counting(i+1)
  print(int(upper-minus[n]))
else:
  print(int(0))
### BUGGY CODE ###

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

maxA = max(A)
maxl = len(bin(maxA)[2:])
binary_c = [0 for _ in range(maxl)]
for a in A:
    for i, n in enumerate(bin(a)[2:].zfill(maxl)):
        if n == "1":
            binary_c[i] += 1
is_inv = []
for bc in binary_c:
    if bc % 2 == 0:
        is_inv.append(False)
    else:
        is_inv.append(True)

for a in A:
    l = []
    for i, n in enumerate(bin(a)[2:].zfill(maxl)):
        if is_inv[i]:
            if n == "0":
                l.append("1")
            else:
                l.append("0")
        else:
            l.append(n)
    print(int("".join(l), 2))


### FIXED CODE ###

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

maxA = max(A)
maxl = len(bin(maxA)[2:])
binary_c = [0 for _ in range(maxl)]
A_binary = [bin(a)[2:].zfill(maxl) for a in A]
for a in A_binary:
    for i, n in enumerate(a):
        if n == "1":
            binary_c[i] += 1
is_inv = []
for bc in binary_c:
    if bc % 2 == 0:
        is_inv.append(False)
    else:
        is_inv.append(True)

for a in A_binary:
    l = []
    for i, n in enumerate(a):
        if is_inv[i]:
            if n == "0":
                l.append("1")
            else:
                l.append("0")
        else:
            l.append(n)
    print(int("".join(l), 2))
### BUGGY CODE ###

n,m=map(int, input().split());S=[[]for _ in range(m+1)];exec("l,r=map(int,input().split());S[r-l+1].append((l, r));"*n);B=[0]*(m+2)
def A(i,a):
 while i<=m+1:B[i]+=a;i+=i&(-i)
def C(i):
 r=0
 while i:r+=B[i];i-=i&(-i)
 return r
for i in range(1,m+1):
 for l,r in S[i]:n-=1;A(l,1);A(r+1,-1)
 r=n
 for j in range(0,m+1,i):r+=C(j)
 print(r)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
  n, m = map(int, input().split())
  LR = [list(map(int, input().split())) for _ in range(n)]
  
  BIT = [0]*(m+2)
  def add(i, a):
    while i <= m+1:
      BIT[i] += a
      i += i&(-i)
  def bit_sum(i):
    res = 0
    while i > 0:
      res += BIT[i]
      i -= i&(-i)
    return res
  
  for l, r in LR:
    add(l, 1)
    add(r+1, -1)
  
  S = sorted([(r-l+1, l, r) for l, r in LR])
  cnt = 0
  L = []
  for i in range(m, 0, -1):
    while S and S[-1][0] == i:
      c, l, r = S.pop()
      cnt += 1
      add(l, -1)
      add(r+1, 1)
    res = cnt
    for j in range(0, m+1, i):
      res += bit_sum(j)
    L.append(res)
  print(*L[::-1], sep="\n")

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

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
# dp[i][j][k] i番目まで見て和がjとなる総数
# k=0がL,Rが決まっていない、k=1がLだけ決定、k=2がLとRが決定
dp = [[[0] * 3 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(S+1):
        zero = dp[i][j][0]; one = dp[i][j][1]; two = dp[i][j][2]
        dp[i+1][j][0] += zero
        dp[i+1][j][1] += zero + one
        dp[i+1][j][2] += zero + one + two
        if a + j <= S:
            dp[i+1][j+a][1] = zero + one
            dp[i+1][j+a][2] = zero + one
        dp[i+1][j][2] %= MOD

answer = dp[N][S][2] % MOD
print(answer)
# 11

### FIXED CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
dp = [0] * (S+1)
answer = 0
for a in A:
    dp[0] += 1 # Lの数は１個ずつ加わる
    prev = dp.copy()
    for i in range(S-a+1):
        dp[i+a] += prev[i]
    answer += dp[-1] # その位置Rとした時

print(answer % MOD)
# 26
### BUGGY CODE ###

"""
解説を参考に作成
"""

from collections import deque


def solve():
    H, W = map(int, input().split())
    mass = [[0] * W for _ in range(H)]
    queue1 = deque([])
    queue2 = deque([])
    for Hi in range(H):
        massHi = [0 if s == '.' else 1 for s in list(input())]
        for Wi in range(W):
            mass[Hi][Wi] = [Hi, Wi, massHi[Wi]]
            if massHi[Wi] == 1:
                queue1.append(mass[Hi][Wi])

    count = -1
    while True:
        # print('count: {}, queue:{}'.format(count, len(queue1)))
        if len(queue1) == 0:
            break

        while len(queue1) > 0:
            h, w, a = queue1.popleft()
            # left
            if w != 0 and mass[h][w - 1][2] == 0:
                mass[h][w - 1][2] = 1
                queue2.append(mass[h][w - 1])
            # right
            if w < W - 1 and mass[h][w + 1][2] == 0:
                mass[h][w + 1][2] = 1
                queue2.append(mass[h][w + 1])
            # top
            if h < H - 1 and mass[h + 1][w][2] == 0:
                mass[h + 1][w][2] = 1
                queue2.append(mass[h + 1][w])
            # button
            if h != 0 and mass[h - 1][w][2] == 0:
                mass[h - 1][w][2] = 1
                queue2.append(mass[h - 1][w])

        count += 1
        queue1 = queue2
        queue2 = deque([])
    print(count)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

"""
解説と提出 #5747380を参考に作成
"""

from collections import deque


def solve():
    H, W = map(int, input().split())
    # mass = [[False] * W for _ in range(H)]
    # queue1 = deque([])
    # queue2 = deque([])
    queue1 = []
    queue2 = []
    mass = []
    mass.append([False] * (W + 2))  # 外枠
    for Hi in range(1, H + 1):
        mass.append([False] + [s == '.' for s in list(input())] + [False])
        for Wi in range(1, W + 1):
            if not mass[Hi][Wi]:
                queue1.append((Hi, Wi))
    mass.append([False] * (W + 2))  # 外枠
    import datetime
    d = datetime.datetime.now()
    count = -1
    while True:
        # print('count: {}, queue:{}'.format(count, len(queue1)))
        if len(queue1) == 0:
            break
        for h, w in queue1:
            # left
            if mass[h][w - 1]:
                mass[h][w - 1] = False
                queue2.append((h, w - 1))
            # right
            if mass[h][w + 1]:
                mass[h][w + 1] = False
                queue2.append((h, w + 1))
            # top
            if mass[h + 1][w]:
                mass[h + 1][w] = False
                queue2.append((h + 1, w))
            # button
            if mass[h - 1][w]:
                mass[h - 1][w] = False
                queue2.append((h - 1, w))

        count += 1
        queue1 = queue2
        queue2 = []
    print(count)

    # print(datetime.datetime.now() - d)


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

a=input()
num=len(a)
mod_map={0:1}
moji_int=0
for i in range(-1,-num-1,-1):
    moji_int+=int(a[i])*10**(-i-1)
    mod=moji_int%2019
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1

res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)

### FIXED CODE ###

a=reversed(input())
#num=len(a)
mod_list=[1]+[0]*2019
moji_int=0
Sn=0
tens=1
for i in a:
    tmp=int(i)*(tens)
    Sn=(Sn+tmp)%2019
    mod=Sn
    tens=tens*10%2019
    mod_list[mod]+=1
res=0
for i in mod_list:
    res+=int(i*(i-1)/2)
print(res)
### BUGGY CODE ###

from heapq import heappush, heappop, heapify
N=input()

A=[]
for i in range(N):
	x,y=map( int, raw_input().split() )
	A.append( [i+1,x,y] )

A.sort(key=lambda x:x[1])

hq=[]
for idx,s in enumerate(A):
	i,x,y=s[0],s[1],s[2]
	if idx==0:
		pre_i=i
		pre_x=x
		pre_y=y
	else:
		heappush(hq, (x-pre_x, pre_i, i ) )
		pre_i=i
		pre_x=x
		pre_y=y

A.sort(key=lambda x:x[2])

for idx,s in enumerate(A):
	i,x,y=s[0],s[1],s[2]
	if idx==0:
		pre_i=i
		pre_x=x
		pre_y=y
	else:
		heappush(hq, (y-pre_y, pre_i, i ) )
		pre_i=i
		pre_x=x
		pre_y=y


par=[ i for i in range(N+1)]

def root(x):
	if par[x]==x: return x
	else:
		par[x]=root(par[x])
		return par[x]
def same(x,y):
	return root(x)==root(y)

def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y: return
	par[x]=y


ans=0
while hq:
	cost,x,y=heappop(hq)

	if not same(x,y):
		unite(x,y)
		ans+=cost

print ans




### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq
import sys
sys.setrecursionlimit(10**6)
N = input()
a = []
for i in range(N):
	x,y=map(int,raw_input().split())
	a.append((i,x,y))

#a => point,x,y
a1=sorted(a, key=lambda x: x[1])
a2=sorted(a, key=lambda x: x[2])


#Union Find
#初めは各頂点が根
par=[ i for i in range(N) ]
#木の根を求める
def root(x):
	if par[x]==x:
		return x
	else:
		r=root(par[x])
		#経路圧縮
		par[x]=r
		return r
#xとyが同じ集合に属するか
def same(x,y):
	return root(x)==root(y)

#xとyが同じ根に所属していた場合、連結
def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y:
		return
	else:
		par[x]=y


b=[]
for i in range(N-1):
	# len_x,x,y
	heapq.heappush( b, ( abs(a1[i+1][1]-a1[i][1]),a1[i][0],a1[i+1][0],  ))

for i in range(N-1):
	# len_y,x,y
	heapq.heappush( b, ( abs(a2[i+1][2]-a2[i][2]),a2[i][0],a2[i+1][0],  ))

#print "# b"
#print b


ans=0
cnt=0
for i in range(len(b)):
	if cnt==N-1:
		break
	val=heapq.heappop(b)
	#２点が同じ根でない場合は、木を結合する
	if not same(val[1],val[2]):
		unite(val[1],val[2])
		ans+=val[0]
		cnt+=1

print ans
### BUGGY CODE ###

N , K = list(map(int,input().split()))
li = list(map(int,input().split()))
typ = []
for i in range(N):
    if li[i] == -1: 
        pass
    else:
        count = 0 
        num = li[i]
        for i2 in range(N - i): 
            if li[i + i2] == num:
                count += 1
                li[i + i2] = -1
        typ.append(count)
typ.sort()
count = 0 
if len(typ) > K:
    for i in range(len(typ) - K): 
        count += typ[i]
print(count)

### FIXED CODE ###

N , K = list(map(int,input().split()))
li = list(map(int,input().split()))
typ = []
li.sort()
count = 0 
for i in range(N - 1): 
    count += 1
    if li[i] != li[i + 1]: 
        typ.append(count)
        count = 0 
if li[N - 1] != li[N - 2]: 
    typ.append(1)
else:
    typ.append(count + 1)
typ.sort()
count = 0 
if len(typ) > K:
    for i in range(len(typ) - K): 
        count += typ[i]
print(count)
### BUGGY CODE ###


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def main():
    s=list(input())
    mod=10**9+7
    K=modinv(10,13)
    U=[[0 for i in range(10) ]for k in range(13)]
    for i in range(13):
        for j in range(10):
            U[i][j]=((i-j)*K)%13

    dp=[[0 for k in range(13)] for i in range(len(s))]
    #dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
    num=s[0]
    if s[0]=="?":
        for i in range(10):
            dp[0][i]=1
    else:
        number=int(s[0])
        dp[0][number]=1

    for i in range(1,len(s)):
        if s[i]=="?":
            for k in range(13):
                for j in range(10):
                    dp[i][k]+=dp[i-1][U[k][j]]%mod
            continue
        else:
            number=int(s[i])
            for k in range(13):
                dp[i][k]=dp[i-1][U[k][number]]
    print(dp[len(s)-1][5]%mod)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def main():
    s=list(input())
    mod=10**9+7
    K=modinv(10,13)
    U=[[0 for i in range(10) ]for k in range(13)]
    for i in range(13):
        for j in range(10):
            U[i][j]=((i-j)*K)%13

    dp=[[0 for k in range(13)] for i in range(len(s))]
    #dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
    num=s[0]
    if s[0]=="?":
        for i in range(10):
            dp[0][i]=1
    else:
        number=int(s[0])
        dp[0][number]=1

    for i in range(1,len(s)):
        for k in range(13):
            if s[i]=="?":
                for j in range(10):
                    dp[i][k]+=dp[i-1][U[k][j]]%mod
            else:
                number=int(s[i])
                dp[i][k]=dp[i-1][U[k][number]]%mod
    print(dp[len(s)-1][5]%mod)
if __name__ == "__main__":
    main()