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

import heapq

n, m = map(int, input().split())
baitos = []
for _ in range(n):
    baitos.append(list(map(int, input().split())))

baitos = sorted(baitos)
# print(sorted(baitos))
# print(baitos)

money = 0
avail = []
heapq.heapify(avail)
for day in range(m):
    while baitos:
        if baitos[0][0] > day + 1:
            break
        else:
            heapq.heappush(avail, -baitos[0][1])
            baitos.remove(baitos[0])
    # for baito in baitos:
    #     print(baito)
    #     if baito[0] > day + 1:
    #         print("break")
    #         break
    #     else:
    #         heapq.heappush(avail, -baito[1])
    #         baitos.remove(baito)
    # print("baitos", baitos)
    # print("avail", avail)
    if avail:

        money += -heapq.heappop(avail)
        # print(day, money)
    # money += max[1]
    # baitos.remove(max)

print(money)


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
baitos = [list(map(int, input().split())) for _ in range(n)]

baitos = sorted(baitos)
# print(sorted(baitos))
# print(baitos)

money = 0
avail = []
# heapq.heapify(avail)
index = 0
for day in range(m):
    while index < n and baitos[index][0] <= day + 1:
        heapq.heappush(avail, -baitos[index][1])
        index += 1
        # baitos.remove(baitos[0])
    # for baito in baitos:
    #     print(baito)
    #     if baito[0] > day + 1:
    #         print("break")
    #         break
    #     else:
    #         heapq.heappush(avail, -baito[1])
    #         baitos.remove(baito)
    # print("baitos", baitos)
    # print("avail", avail)
    if avail:

        money += -heapq.heappop(avail)
        # print(day, money)
    # money += max[1]
    # baitos.remove(max)

print(money)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
A,B,C= [[int(i) for i in input().split()] for j in range(3)]
AB = []
ABC = []
for i in range(x):
        for j in range(y):
                AB.append(A[i]+B[j])
AB.sort(reverse = True)
for i in range(min(k,len(AB))):
        for j in range(z):
                ABC.append(AB[i]+C[j])
ABC.sort(reverse = True)
for i in range(k):
        print(ABC[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
f = 0
count = 0
for j in range(1,N+1):
    for i in range(1,N+1):
        if i%j == 0:
            count +=i
    f = f + (j * count)
print(count)

### FIXED CODE ###

N = int(input())
count = 0
for i in range(1,N+1):
    t = N//i
    count += i * t*(t+1)/2
print(int(count))
### BUGGY CODE ###

import numpy as np
n=int(input())
l=list(map(int,input().split()))


arr=np.array(l)
arr2=np.append(np.hstack((0,arr)),0)
differ=sum(abs(np.diff(arr2)))
for i in range(1,n+1):
    difference=abs(np.diff(arr2)[i]+np.diff(arr2)[i-1])-abs(np.diff(arr2)[i])-abs(np.diff(arr2)[i-1])
    print(differ+difference)

   


### FIXED CODE ###

import numpy as np
n=int(input())
l=list(map(int,input().split()))


arr=np.array(l)
arr2=np.append(np.hstack((0,arr)),0)
differ=sum(abs(np.diff(arr2)))
dif=np.diff(arr2)
for i in range(1,n+1):
    difference=abs(dif[i]+dif[i-1])-abs(dif[i])-abs(dif[i-1])
    print(differ+difference)
### BUGGY CODE ###

import sys
#if sys.version_info[0]>=3:raw_input=input

from scipy.sparse import*
g=[]
n=int(raw_input())
for _ in xrange(n-1):
	a,b=map(int,raw_input().split())
	g+=[(a-1,b-1,1)]
	g+=[(b-1,a-1,1)]
z=[-1]*n
for _ in xrange(int(raw_input())):
	a,b=map(int,raw_input().split())
	g+=[(n,a-1,b)]
	z[a-1]=b
a,b,c=zip(*g)
a=map(int,csgraph.dijkstra(csr_matrix((c,(a,b)),[n+1]*2),1,n))
for i in xrange(n):
	if z[i]>=0 and z[i]!=a[i]:
		print('No')
		sys.exit()
for e in g:
	if e[0]<e[1] and abs(a[e[0]]-a[e[1]])!=1:
		print('No')
		sys.exit()
print('Yes')
print("\n".join(map(str,a[:n])))

### FIXED CODE ###

#!/usr/bin/python
def shortestPath(g,s,dist,prev):
	n = len(g)-1
	Q=[]
	heapq.heappush(Q,(0,-2,s))
	while Q:
		e = heapq.heappop(Q)
		if prev[e[2]]!=-1: continue
		prev[e[2]] = e[1]
		for f in g[e[2]]:
			if dist[f[2]] > e[0] + f[0]:
				dist[f[2]] = e[0] + f[0]
				heapq.heappush(Q,(e[0]+f[0],f[1],f[2]))

import sys,heapq
#if sys.version_info[0]>=3:raw_input=input

n=int(raw_input())
g=[[] for _ in range(n+1)]
for _ in xrange(n-1):
	a,b=map(int,raw_input().split())
	g[a-1]+=[(1,a-1,b-1)]
	g[b-1]+=[(1,b-1,a-1)]
z=[-1]*n
for _ in xrange(int(raw_input())):
	a,b=map(int,raw_input().split())
	g[n]+=[(b,n,a-1)]
	z[a-1]=b
a=[1e9]*n+[0]
shortestPath(g,n,a,[-1]*(n+1))
for i in xrange(n):
	if z[i]>=0 and z[i]!=a[i]:
		print('No')
		sys.exit()
for _ in g:
	for e in _:
		if e[1]<e[2] and abs(a[e[1]]-a[e[2]])!=1:
			print('No')
			sys.exit()
print('Yes')
print("\n".join(map(str,a[:n])))
### BUGGY CODE ###

class combnk_mod(object):
    # pが素数かつaとpが互いに素であるとき
    # フェルマーの小定理より以下が成り立つ.
    # 1 / a = a ** (p - 2) (mod p)
    # これを使って (1 / k!) mod p を計算する.
    def __init__(self, maxn, p):
        self.maxn = maxn
        self.p = p
        self.x = [1] # 分母にあたる数 1 / n! mod p
        self.y = [1] # 分子にあたる数. n! mod p
        for i in range(1, self.maxn + 1):
            self.x.append(self.x[-1] * pow(i, self.p - 2, self.p) % self.p)
            self.y.append(self.y[-1] * i % self.p)

    def combnk(self, n, k):
        if n < k:
            return 0
        return (self.x[n - k] * self.x[k] * self.y[n]) % self.p

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
MOD = 10 ** 9 + 7
combnk = combnk_mod(n, MOD)
ans = 0

if k == 2:
    for i in range(n - 1):
        ai = a[i]
        for j in range(i + 1, n):
            aj = a[j]
            ans += (aj - ai) % MOD
            ans %= MOD
elif k > 2:
    for i in range(n - 1):
        ai = a[i]
        for j in range(i + 1, n):
            aj = a[j]
            f = aj - ai
            m = j - i - 1
            if m >= k - 2:
                ans += f * combnk.combnk(m, k - 2) % MOD
                ans %= MOD
print(ans)


### FIXED CODE ###

class combnk_mod(object):
    # pが素数かつaとpが互いに素であるとき
    # フェルマーの小定理より以下が成り立つ.
    # 1 / a = a ** (p - 2) (mod p)
    # これを使って (1 / k!) mod p を計算する.
    def __init__(self, maxn, p):
        self.maxn = maxn
        self.p = p
        self.x = [1] # 分母にあたる数 1 / n! mod p
        self.y = [1] # 分子にあたる数. n! mod p
        for i in range(1, self.maxn + 1):
            self.x.append(self.x[-1] * pow(i, self.p - 2, self.p) % self.p)
            self.y.append(self.y[-1] * i % self.p)

    def combnk(self, n, k):
        if n < k:
            return 0
        return (self.x[n - k] * self.x[k] * self.y[n]) % self.p

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
MOD = 10 ** 9 + 7
combnk = combnk_mod(n, MOD)
ans = 0
if k == 1:
    print(0)
else:
    x = [0 for _ in range(n)]
    y = [combnk.combnk(i, k - 2) for i in range(n + 1)]
    ya = [0]
    for yi in y:
        ya.append(ya[-1] + yi)

    for i in range(n):
        end = i + k - 1
        x[i] = ya[i] - ya[max(0, n - i - 1)]
    for xi, ai in zip(x, a):
        ans += xi * ai % MOD
        ans %= MOD
    print(ans)
### BUGGY CODE ###

S = input()

char = S
last_len = 0
while len(char)!=last_len:
    last_len = len(char)
    char = char.replace("01","").replace("10","").replace("01","").replace("10","").replace("01","").replace("10","")
print(len(S)-len(char))

### FIXED CODE ###

from collections import Counter
C = Counter(list(input()))
print(C["0"]*2 if C["0"]<=C["1"] else C["1"]*2)
### BUGGY CODE ###

n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]

loop=set()
d=[-10**15 for _ in [0]*n]
d[0]=0
q=[[0,1]]
s=set()
l=[]
while q:
    item,depth=q.pop()
    if depth<=len(s):
        for _ in range(len(s)-depth+1):
            rmv=l.pop()
            s.remove(rmv)
    l.append(item)
    s.add(item)
    for i,dist in g[item]:
        if d[i]<d[item]+dist:
            if i in s:
                loop.add(i)
                continue
            d[i]=d[item]+dist
            q.append([i,depth+1])
  
c=[False for _ in [0]*n]
for x in loop:
    if c[x]==True:
        continue
    q=[x]
    c[x]=True
    while q:
        item=q.pop()
        for i,j in g[item]:
            if c[i]==False:
                c[i]=True
                q.append(i)
if c[n-1]==True:
    print("inf")
else:
    print(d[n-1])

### FIXED CODE ###

n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]

dist=[-10**15 for _ in [0]*n]
dist[0]=0
a,b=-10**15,-10**15

for _ in range(n):
    for p in range(n):
        for i,j in g[p]:
            dist[i]=max(dist[i],dist[p]+j)
    a,b=b,dist[n-1]

if a==b:
    print(a)
else:
    print("inf")
### BUGGY CODE ###

#input
N = int(input())
L = list(map(int, input().split()))

#output
import heapq

L = [-l for l in L]
heapq.heapify(L)

sum = 0
while len(L) > 2:
    target = heapq.heappop(L)
    for i in range(len(L)-1):
        for j in range(i+1, len(L)):
            if target > L[i] +  L[j]:
                sum += 1
        
print(sum)

### FIXED CODE ###

#input
N = int(input())
L = list(map(int, input().split()))

#output
import heapq
import bisect

L = [-l for l in L]
heapq.heapify(L)

sum = 0
while len(L) > 2:
    largest = heapq.heappop(L)
    L.sort()
    for i in range(len(L)-1):
        p = bisect.bisect_left(L, largest-L[i])
        if p-(i+1) >0:
            sum += p-(i+1)
        
print(sum)
### BUGGY CODE ###

A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]

T = [int(input()) for _ in range(B)]

X = [int(input()) for _ in range(Q)]

from bisect import bisect_left

for _ in range(Q):
    ans = 10**12
    x = X[_]
    idxs = bisect_left(S,x)
    idxt = bisect_left(T,x)

    if idxs < A and idxt < B:
        ans = min(ans, max(S[idxs],T[idxt])-x)
    if 0 <= idxs-1 and 0 <= idxt-1:
        ans = min(ans, x-min(S[idxs-1],T[idxt-1]))
    if idxs < A and 0 <= idxt-1:
        ans = min(ans, S[idxs]-T[idxt-1] + min(S[idxs]-x, x-T[idxt-1]))
    if idxt < B and 0 <= idxs-1:
        ans = min(ans, T[idxt]-S[idxs-1] + min(T[idxt]-x, x-S[idxs-1]))

    print(ans)



### FIXED CODE ###

A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]

T = [int(input()) for _ in range(B)]

from bisect import bisect_left

for _ in range(Q):
    ans = 10**12
    x = int(input())
    idxs = bisect_left(S,x)
    idxt = bisect_left(T,x)

    if idxs < A and idxt < B:
        ans = min(ans, max(S[idxs],T[idxt])-x)
    if 0 <= idxs-1 and 0 <= idxt-1:
        ans = min(ans, x-min(S[idxs-1],T[idxt-1]))
    if idxs < A and 0 <= idxt-1:
        ans = min(ans, S[idxs]-T[idxt-1] + min(S[idxs]-x, x-T[idxt-1]))
    if idxt < B and 0 <= idxs-1:
        ans = min(ans, T[idxt]-S[idxs-1] + min(T[idxt]-x, x-S[idxs-1]))
    print(ans)
### BUGGY CODE ###

import numpy as np

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

dp = np.zeros(N*2+2, dtype = int)
dp[1] = 1

for i in range(1, N+1):
    atai = dp[i]
    for LR in LRs:
#        p_array = ([atai] * (LR[1] - LR[0] + 1))
#        mae_zero = ([0] * (LR[0] + (i - 1) + 1))
#        usiro_zero = ([0] * (N*2 - (i - 1) - LR[1]))

        mae_zero = np.zeros(LR[0] + i , dtype = "int32")
        usiro_zero = np.zeros(N*2 - (i - 1) - LR[1], dtype = "int32")
        p_array = np.full((LR[1] - LR[0] + 1), atai, dtype = "int32")

        tasu_array = np.concatenate([mae_zero, p_array, usiro_zero])
        dp = (dp + tasu_array) % 998244353

print(dp[N] % 998244353)

### FIXED CODE ###

import numpy as np

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

dp = np.zeros(N+2, dtype = int)
dp[1] = 1
dp[2] = -1

atai = 0
for i in range(1, N+2):
    atai += dp[i]
    for LR in LRs:
        if(i+LR[0] <= N):
            dp[i+LR[0]] = (dp[i+LR[0]] + atai) % 998244353
        if(i+LR[1] <= N):
            dp[i+LR[1]+1] = (dp[i+LR[1]+1] -atai) % 998244353

#    print(dp)

#復元
ruisekiwa = [0]

for hoge in dp:
    ruisekiwa.append(ruisekiwa[-1]+hoge)
print(ruisekiwa[N+1] % 998244353)
### BUGGY CODE ###

s = input()
q = s.count('?')
res = 0
mod = 10**9+7

# 前処理
# ある地点(pivot)まで(から)のA(C),?の数
bp_A,bp_Q,ap_C,ap_Q = [0],[0],[0],[0]
for c in s:
    bp_A.append(bp_A[-1]+(c=='A'))
    bp_Q.append(bp_Q[-1]+(c=='?'))
for c in s[::-1]:
    ap_C.append(ap_C[-1]+(c=='C'))
    ap_Q.append(ap_Q[-1]+(c=='?'))
ap_C,ap_Q = ap_C[::-1][1:],ap_Q[::-1][1:]

def add(num):
    global res
    res += num
    res %= mod

for pivot in range(1,len(s)-1):
    if s[pivot]=='B' or s[pivot]=='?':
        tmp = q - (s[pivot]=='?')
        s1_a,s1_q = bp_A[pivot],bp_Q[pivot]
        s2_c,s2_q = ap_C[pivot],ap_Q[pivot]
        add(s1_a * s2_c * 3**tmp)           # A,C
        add(s1_a * s2_q * 3**(tmp-1))       # A,?
        add(s1_q * s2_c * 3**(tmp-1))       # ?,C
        add(s1_q * s2_q * 3**(tmp-2))       # ?,?

print(int(res))


### FIXED CODE ###

s = input()
q = s.count('?')
res = 0
mod = 10**9+7

""" 前処理 """
# ある地点(pivot)まで(から)のA(C),?の数
bp_A,bp_Q,ap_C,ap_Q = [0],[0],[0],[0]
for c in s:
    bp_A.append(bp_A[-1]+(c=='A'))
    bp_Q.append(bp_Q[-1]+(c=='?'))
for c in s[::-1]:
    ap_C.append(ap_C[-1]+(c=='C'))
    ap_Q.append(ap_Q[-1]+(c=='?'))
# 3の累乗のmod
three = [3]
i = 1
while i<q:
    three.append((three[-1]**2)%mod)
    i *= 2
""" ここまで """

# 3の累乗
def pow(num):
    if num<0:
        return 0
    elif num==0:
        return 1
    else:
        ans = 1
        for i,j in enumerate(three):
            if num&(1<<i):
                ans *= j
                ans %= mod
        return ans

for pivot in range(1,len(s)-1):
    if s[pivot]=='B' or s[pivot]=='?':
        tmp = q - (s[pivot]=='?')
        s1_a,s1_q = bp_A[pivot],bp_Q[pivot]
        s2_c,s2_q = ap_C[-pivot-2],ap_Q[-pivot-2]
        res += (s1_a*s2_c)%mod * pow(tmp)
        res += (s1_a*s2_q)%mod * pow(tmp-1)
        res += (s1_q*s2_c)%mod * pow(tmp-1)
        res += (s1_q*s2_q)%mod * pow(tmp-2)

print(int(res)%mod)
### BUGGY CODE ###

n=int(input())
cnt=0
for a in range(1,n+1):
  for b in range(1, n+1):
    if str(a)[0]==str(b)[-1] and str(a)[-1]==str(b)[0]: cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
cnt=0
# c(i,j)={先頭がiで末尾がjであるkの個数}
c=[[0 for _ in range(10)] for _ in range(10)]
for i in range(1,n+1):
  l=int(str(i)[0])
  r=int(str(i)[-1])
  c[l][r]+=1
'''
for i in range(10):
  for j in range(10):
    print(c[i][j], end=' ')
  print('')
'''
sum=0
for i in range(1,10):
  for j in range(1,10):
    sum+=c[i][j]*c[j][i]
print(sum)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun May 31 13:40:00 2020

@author: NEC-PCuser
"""
def fibonatch(a, N):
    #d[i][j]: iからjへの最短距離
    n1, n2 = 1, 1
    if N == 0:
        return 1
    elif N == 1:
        return 1
    else:
        for i in range(N - 1):
            if str(i) in a:
                n2 = 0
            if str(i + 1) in a:
                n1 = 0
            n1, n2 = n1 + n2, n1
        return (n1) % 1000000007



if __name__ == "__main__":
    N, M = map(int, input().split())
    a = []
    for i in range(M):
        a.append(input())
    
    print(fibonatch(a, N))


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun May 31 13:40:00 2020

@author: NEC-PCuser
"""
def fibonatch(a, N):
    #d[i][j]: iからjへの最短距離
    n1, n2 = 1, 1
    if N == 0:
        return 1
    elif N == 1:
        return 1
    else:
        for i in range(N - 1):
            if a[i] == 1:
                n1 = 0
            if a[i + 1] == 1:
                n2 = 0
            n1, n2 = n1 + n2, n1
        return (n1) % 1000000007



if __name__ == "__main__":
    N, M = map(int, input().split())
    a = [0] * N
    for i in range(M):
        a[int(input()) - 1] = 1
    
    print(fibonatch(a, N))
### BUGGY CODE ###

import math
n = int(input())
nn = int(math.sqrt(n))
while n%nn != 0: nn+=1
ans = len(str(nn))
print(ans)

### FIXED CODE ###

import math
n = int(input())
nn = int(math.sqrt(n))
while n%nn != 0: nn-=1
ans = len(str(n//nn))
print(ans)
### BUGGY CODE ###

from functools import lru_cache


@lru_cache(maxsize=None)
def get_dividers(n):
    """
    正の整数 n の約数を取得する
    """

    dividers = {i for i in range(1, int(n ** 0.5) + 1) if n % i == 0}
    return dividers | {n // d for d in dividers}


A, B = map(int, input().split(' '))

a_dividers = get_dividers(A)
b_dividers = get_dividers(B)
common_dividers = a_dividers & b_dividers
ans = []

for cd in sorted(common_dividers):
    dividers = get_dividers(cd) - {1}
    for d in ans:
        if d & dividers:
            break
    else:
        ans.append(dividers)

print(len(ans))


### FIXED CODE ###

from functools import lru_cache


@lru_cache(maxsize=None)
def get_dividers(n):
    """
    正の整数 n の約数を取得する
    """

    dividers = {i for i in range(1, int(n ** 0.5) + 1) if n % i == 0}
    return dividers | {n // d for d in dividers}


A, B = map(int, input().split(' '))

a_dividers = get_dividers(A)
b_dividers = get_dividers(B)
common_dividers = a_dividers & b_dividers
ans = []

for cd in sorted(common_dividers):
    dividers = get_dividers(cd) - {1}
    for d in ans:
        if d & dividers:
            break
    else:
        ans.append(dividers)

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

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

card_list = [1] * n

for i in range(m):
    l, r  = map(int, input().split())
    l -= 1
    r -= 1
    for j in range(n):
        if l <= j <= r:
            continue
        card_list[j] = 0
print(sum(card_list))


### FIXED CODE ###

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

card_list = [1] * n

minr = 10**9
maxl = 0

for i in range(m):
    l, r  = map(int, input().split())
    maxl = max(maxl, l)
    minr = min(minr, r)
print(max(minr - maxl + 1, 0))
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
mod = 10**9 + 7
# (N-1)!を求める
fac=1
for i in range(1,n):
  fac = fac*i
# 個数テーブルを準備する
cnt=[0]*n
for i in range(1,n):
  cnt[i] = fac // i
  cnt[i] = (cnt[i]+cnt[i-1])
# 計算
ans=0
for i in range(n-1):
  ans += (A[i+1]-A[i]) * cnt[i+1]

print(ans%mod)


### FIXED CODE ###

mod=10**9+7
# mod inverse(逆元)
# 今回はfermatの小定理で求める
def mod_inv(x):
  return pow(x,mod-2,mod)

n=int(input())
A=list(map(int,input().split()))
# (N-1)!を求める
fac=1
for i in range(1,n):
  fac = fac*i%mod
# 各区間の個数テーブルを先に求める
cnt=[0]*n
for i in range(1,n):
  cnt[i] = fac * mod_inv(i) % mod
  cnt[i] = (cnt[i]+cnt[i-1]) % mod
# 計算
ans=0
for i in range(n-1):
  ans += (A[i+1]-A[i]) * cnt[i+1]
  ans %= mod

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

def main():
  s=int(input())
  #while s%10==0:
  #    s//=10
  s=9**800000
  s=str(s)
  lens=len(s)

  d=int(s[0])
  p=11-int(s[0])

  for c in s[1:]:
      j=int(c)
      a=min(d+j,p+j)
      b=min(d+11-j,p+9-j)
      d,p=a,b

  print(min(d,p))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
  s=input()
  #while s%10==0:
  #    s//=10
  #s=9**100
  #s=str(s)
  lens=len(s)

  d=int(s[0])
  p=11-int(s[0])

  for c in s[1:]:
      j=int(c)
      a=min(d+j,p+j)
      b=min(d+11-j,p+9-j)
      d,p=a,b

  print(min(d,p))

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

from collections import defaultdict


memo = {}


def dfs(s):
    tuple_s = tuple(s)
    if tuple_s in memo:
        return memo[tuple_s]

    if s.count("B") == len(s) or s.count("W") == len(s):
        return 0

    ans = 10 ** 20
    stone = s[0]
    t = s[:]
    while t[0] == stone:
        t = t[1:]
    ans = min(ans, dfs(t) + 1)

    stone = s[-1]
    t = s[:]
    while t[-1] == stone:
        t = t[:-1]
    ans = min(ans, dfs(t) + 1)

    memo[tuple_s] = ans
    return ans


def main():
    s = input()
    print(dfs(list(s)))


if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    S = input()

    t = S[0]
    for i in range(1, len(S)):
        if t[-1] != S[i]:
            t += S[i]
    print(len(t) - 1)

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

def accumulate(li):
    ret = [0]
    for e in li:
        if e:
            ret.append(ret[-1] + 1)
        else:
            ret.append(0)

    return ret[1:]


def main():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]

    m = [[0 if e == "#" else 1 for e in s[i]] for i in range(h)]

    lr = [accumulate(m[i]) for i in range(h)]
    rl = [accumulate(m[i][::-1])[::-1] for i in range(h)]

    m_ud = []
    for i in range(w):
        tmp = []
        for j in range(h):
            tmp.append(m[j][i])
        m_ud.append(tmp)

    ud = [accumulate(m_ud[i]) for i in range(w)]
    du = [accumulate(m_ud[i][::-1])[::-1] for i in range(w)]

    ans = 0
    for i in range(h):
        for j in range(w):
            sm = lr[i][j] + rl[i][j] + ud[j][i] + du[j][i] - 3
            ans = max(ans, sm)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]

    m = [[0] + [0 if e == "#" else 1 for e in s[i]] + [0] for i in range(h)]
    m.append([0] * (w + 2))
    m.insert(0, [0] * (w + 2))

    m_t = [[m[i][j] for i in range(h+2)] for j in range(w+2)]

    lr = []
    for i in range(h + 2):
        sm = 0
        row = []
        for j in range(w + 2):
            if m[i][j]:
                sm += 1
            else:
                row += [sm] * sm + [0]
                sm = 0

        lr.append(row)

    ud = []
    for i in range(w + 2):
        sm = 0
        row = []
        for j in range(h + 2):
            if m_t[i][j]:
                sm += 1
            else:
                row += [sm] * sm + [0]
                sm = 0

        ud.append(row)

    ans = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            sm = lr[i][j] + ud[j][i] - 1
            ans = max(ans, sm)

    print(ans)


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

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

SUM=0

for i in range(N-1):
  for j in range(i+1,N):
    SUM = SUM+(A[i]^A[j])
    SUM %= 10**9+7

print(SUM%(10**9+7))

### FIXED CODE ###

import numpy as np
 
n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
ans = 0
 
for i in range(60):
    #一桁目が1か0か調べて1の個数をカウント
    c1 = np.count_nonzero(arr & 1) 
    #1の個数×0の個数(XORだから)
    ans += 2 ** i * c1 * (n - c1)
    #桁をシフト
    arr =arr >> 1

print(ans % mod)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
count = 0
for i in range(n):
    a = l[i]
    for j in range(i+1,n):
        b = l[j]
        for k in range(j+1,n):
            c = l[k]
            if a+b>c and a+c>b and b+c>a:
                count += 1
                
print(count)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
count = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        maxc = l[i]+l[j] #短い2辺の和
        index = bisect.bisect_left(l, maxc)
        if index > j:
            count += index-j-1
print(count)
### BUGGY CODE ###

S = input()
ans = 0

for i in range(len(S)):
    for j in range(i + 4, len(S)):
        if int(S[i:j + 1]) % 2019 == 0:
            ans += 1

print(ans)

### FIXED CODE ###

p=d=2019
z=[0]*p
for i,j in enumerate(input()[::-1]):
	d=d+int(j)*pow(10,i,p)
	z[d%p]+=1
r=z[0]
for i in z:
	r+=i*(i-1)//2
print(r)