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

#!/usr/bin/env python3
import sys
MOD = 1000000007  

def permutations_count(n, r):
    if r>n or r<0:
        return 0
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret %= MOD
    return ret

def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    matrix = [[] for _ in range(N+1)]
    for i in range(N-1):
        matrix[a[i]].append(b[i])
        matrix[b[i]].append(a[i])
    
    visited = [0]*(N+1)

    from collections import deque
    queue = deque()
    visited[1]=1
    answer = K
    answer *= permutations_count(K-1,len(matrix[1]))
    for node in matrix[1]:
        queue.append(node)

    while queue:
        q = queue.popleft()
        if visited[q] == 0:
            answer *= permutations_count(K-2,len(matrix[q])-1) #親ノード引いてる
        else:
            continue
        visited[q] = 1

        for child_node in matrix[q]:
            if child_node != q:
                queue.append(child_node)

    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
MOD = 1000000007  

def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    matrix = [[] for _ in range(N+1)]
    for i in range(N-1):
        matrix[a[i]].append(b[i])
        matrix[b[i]].append(a[i])
    
    visited = [0]*(N+1)

    from collections import deque
    queue = deque()
    visited[1]=1
    answer = K
    num = K-1
    for node in matrix[1]:
        answer *= num
        answer %= MOD

        num -= 1
        queue.append(node)

    while queue:
        q = queue.popleft()
        if visited[q] != 0:
            continue
        visited[q] = 1

        num = K-2
        for child_node in matrix[q]:
            if visited[child_node] == 0:
                answer *= num
                answer %= MOD
                num -= 1
                queue.append(child_node)
        answer %= MOD

    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)

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

def main():
    import bisect
    import numpy as np
    n,k = map(int,input().split())
    l = list(map(int,input().split()))
    l.sort()
    l1 = np.array(l)
    def bise(x):
        y = np.searchsorted(l1,x-l1)
        return n*n-y.sum()

    left = -1
    right = l[-1]*2+1

    while right > left+1:
        mid = (right+left)//2
        
        if bise(mid) > k:
            left = mid
        else:
            right = mid
    ans = []
    for i in l:
        for j in l:
            if i+j >= left:
                ans.append(i+j)
    ans.sort(reverse=True)
    
    print(sum(ans[0:k]))
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import bisect
    import numpy as np
    n,k = map(int,input().split())
    l = list(map(int,input().split()))
    l.sort()
    l1 = np.array(l)
    def bise(x):
        y = np.searchsorted(l1,x-l1)
        return n*n-y.sum()

    left = -1
    right = l[-1]*2+1

    while right > left+1:
        mid = (right+left)//2
        
        if bise(mid) >= k:
            left = mid
        else:
            right = mid
    ans = 0
    count = 0
    acc = [0]
    for i in l:
        acc.append(acc[-1]+i)
    for i in l:
        index = bisect.bisect_left(l,right-i)
        ans += i*(n-index) + acc[n]-acc[index]
        count += n-index

    print(ans-(count-k)*left)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n,k = map(int,input().split())
s = input()
li = []
count = 1
max1 = 0

for i in range(len(s)-1):
    if s[i] == s[i+1]:
        count += 1
    else:
        li.append(count)
        count = 1
li.append(count)

m = len(li)

if s[0] == '1':
    t = int(m/2) # ０の塊の数
    if k >= t:
        print(sum(li))
    else:
        for i in range(t-k+1):
            a = sum(li[2*i:2*(i+k)+1])
            max1 = max(a,max1)
        print(max1)
else:
    t = int(m/2+1)
    if k >= t:
        print(sum(li))
    else:
        max1 = max(max1,sum(li[:2*k]))
        for i in range(t-k):
            a = sum(li[2*i+1:2*(i+k)+2])
            max1 = max(max1,a)
        print(max1)


### FIXED CODE ###

n,k = map(int,input().split())
s = input()
li = [0]
count = 1

for i in range(n-1):
    if s[i] != s[i+1]:
        li.append(count)
    count += 1
li.append(count)

m = len(li)

if s[0] == '1':
    li.append(li[-1])
    li.append(li[-1])
    t = int(m/2-1)
    if k >= t:
        print(n)
    else:
        max1 = 0
        for i in range(t-k+2):
            max1 = max(li[2*(i+k)+1] - li[2*i],max1)
        print(max1)
else:
    li.append(li[-1])
    t = int(m/2)
    if k >= t:
        print(n)
    else:
        max1 = li[2*k]
        for i in range(t-k):
            max1 = max(li[2*(i+k+1)] - li[2*i+1],max1)
        print(max1)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(N):
  ans += i
print(ans)

### FIXED CODE ###

N = int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
n = h*w


def to_v(i, j):
    return i*w+j


init_vs = []
for i in range(h):
    for j, x in enumerate(input()):
        if x == '#':
            init_vs.append(to_v(i, j))


INF = 10**18
dist = [INF]*n
for v in init_vs:
    dist[v] = 0


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def bfs(init_v):
    next_v = deque([init_v])
    while next_v:
        v = next_v.popleft()
        for v2 in generate_v2(v):
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)


for v in init_vs:
    bfs(v)

print(max(dist))


### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
n = h*w


def to_v(i, j):
    return i*w+j


init_vs = []
for i in range(h):
    for j, x in enumerate(input()):
        if x == '#':
            init_vs.append(to_v(i, j))


INF = 10**18
dist = [INF]*n
for v in init_vs:
    dist[v] = 0


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def bfs(init_vs):
    next_v = deque([*init_vs])
    while next_v:
        v = next_v.popleft()
        for v2 in generate_v2(v):
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)


bfs(init_vs)
print(max(dist))
### BUGGY CODE ###

import math
import sys
sys.setrecursionlimit(1000000)

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

memo = {}
def sub_max(n, m):
    if((n, m) in memo):
        return memo[(n, m)]
    
    if(m == 1 and n>=1):
        memo[(n, m)] = max(A[-n:])
        return memo[(n, m)]

    if(m >= n):
        memo[(n, m)] = -float('inf')
        return -float('inf')
    
    res = -float('inf')
    for i in range(math.ceil(n/2)):
        res = max(res, A[-n + i] + sub_max(n - i - 2, m - 1))
    memo[(n, m)] = res
    return res

print(sub_max(N, N//2))

### FIXED CODE ###

import math
import sys
sys.setrecursionlimit(1000000)

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

memo = {}
def sub_max(n, m):
    if((n, m) in memo):
        return memo[(n, m)]
    
    if(m == 1 and n >= 1):
        memo[(n, m)] = max(A[-n:])
        return memo[(n, m)]

    if(m > math.ceil(n/2)):
        memo[(n, m)] = -float('inf')
        return -float('inf')
    
    res = -float('inf')
    for i in range(3):
        res = max(res, A[-n + i] + sub_max(n - i - 2, m - 1))
    memo[(n, m)] = res
    return res

print(sub_max(N, N//2))
# print(memo)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n, q = list(map(int, input().split()))
trees =  [ [] for i in range(n) ]
for i in range(n-1):
    a, b = list(map(int, input().split()))
    trees[a-1].append(b-1)
    trees[b-1].append(a-1)

values = [ 0 for i in range(n) ]
for i in range(q):
    p, x = list(map(int, input().split()))
    values[p-1] += x
#print(values)

def dfs2(i, parent):
    for j in trees[i]:
        if j == parent: continue
        values[j] += values[i]
        dfs2(j, i)

dfs2(0, -1)
print(*values)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
 
ki = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    ki[a].append(b)
    ki[b].append(a)
# print(ki)
 
cnt = [0] * (n + 1)
for i in range(q):
    p, x = map(int, input().split())
    cnt[p] += x
 
 
# print(cnt)
 
 
def d(y, parent):
    for i in ki[y]:
        if i == parent:
            continue
        cnt[i] += cnt[y]
        d(i, y)
 
 
d(1, -1)
print(*cnt[1:])
### BUGGY CODE ###

import math
def main():

    N = int(input())

    d = [0 for _ in range(N+1)]

    v = int(math.sqrt(N))
    for i in range(1, v+1):
        for j in range(i, N+1, i):
            d[j] += 1
            if j//i > v: d[j] += 1

    ans = 0
    for i in range(1, N+1):
        ans += i * d[i]
    return ans

if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import math
import collections
def main():

    N = int(input())
    d = dict()
    for i in range(1, N+1):
        d[i] = 0

    ans = 0
    for i in range(1, N+1):
        p = N//i
        ans += p * (p+1)//2 * i
    return ans

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

import random
def score(D,c,s,t):
    v=list()
    last=[0]*26
    legacy=0
    for i in range(D):
        minus=0
        v.append(legacy)
        v[i]+=s[i][t[i]-1]
        last[t[i]-1]=i+1
        for j in range(26):
            minus+=c[j]*(i+1-last[j])
        v[i]-=minus
        legacy=v[i]
    return v[D-1]
s=list()
t=list()
D=int(input())
c=list(map(int,input().split()))
for i in range(D):
    s.append(list(map(int,input().split())))
t=[random.randint(1,26)]*D
for i in range(10000):
    d=random.randint(1,D)
    q=random.randint(1,26)
    old=t[d-1]
    oldscore=score(D,c,s,t)
    t[d-1]=q
    if score(D,c,s,t)<oldscore:
        t[d-1]=old
for i in range(D):
    print(t[i])

### FIXED CODE ###

import random
def score(D,c,s,t):
    v=list()
    last=[0]*26
    legacy=0
    for i in range(D):
        minus=0
        v.append(legacy)
        v[i]+=s[i][t[i]-1]
        last[t[i]-1]=i+1
        for j in range(26):
            minus+=c[j]*(i+1-last[j])
        v[i]-=minus
        legacy=v[i]
    return v[D-1]
s=list()
t=list()
D=int(input())
c=list(map(int,input().split()))
for i in range(D):
    s.append(list(map(int,input().split())))
t=[random.randint(1,26)]*D
for i in range(100):
    d=random.randint(1,D)
    q=random.randint(1,26)
    old=t[d-1]
    oldscore=score(D,c,s,t)
    t[d-1]=q
    if score(D,c,s,t)<oldscore:
        t[d-1]=old
for i in range(D):
    print(t[i])
### BUGGY CODE ###

import bisect

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

ans = 0

if k * 3 == s:
    print(1)
    exit(0)
else:
    for v in range(k + 1):
        for x in range(k + 1):
            if v + x > s:
                continue
            else:
                targ = s - v - x
                hoge = bisect.bisect_left([i for i in range(k + 1)], targ)
                if hoge < 0 or hoge > k:
                    pass
                else:
                    ans += 1
                    
print(ans)




### FIXED CODE ###

# import bisect

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

ans = 0

if k * 3 == s:
    print(1)
    exit(0)
else:
    for v in range(k + 1):
        # bisect.bisect_left([i for i in range(2 * k + 1)], s - v)
        for x in range(k + 1):
            if v + x > s:
                continue
            else:
                targ = s - v - x
                # hoge = bisect.bisect_left([i for i in range(k + 1)], targ)
                if targ < 0 or targ > k:
                    pass
                else:
                    ans += 1

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


import collections as col


n,x,y = map(int,input().split())
dist = []
for i in range(1,n+1):
    for j in range(i+1,n+1):
        a = abs(i - j)
        b = abs(i - x) + 1 + abs(j - y)
        c = abs(i - y) + 1 + abs(j - x)
        dist.append(min(a,b,c))

cnt = col.Counter(dist)
for i in range(1,n): print(cnt[i])


### FIXED CODE ###

import collections as col


n,x,y = map(int,input().split())
dist = []
for i in range(1,n+1):
    for j in range(i+1,n+1):
        a = abs(i - j)
        b = abs(i - x) + 1 + abs(j - y)
        c = abs(i - y) + 1 + abs(j - x)
        dist.append(min(a,b,c))

cnt = col.Counter(dist)
for i in range(1,n): print(cnt[i])
### BUGGY CODE ###

n = int(input())
cnt = 0
for a in range(1,n):
    i = 1
    while a * i < n:
        cnt += 1
        i += 1
    
print(cnt)

### FIXED CODE ###

n = int(input())
cnt = 0
for a in range(1,n):
    cnt += (n-1) // a
    
print(cnt)
### BUGGY CODE ###

s = list(input())
x = list(map(int, s))
i = 0
ans = 0
k = 0
if len(x) == 1:
    print(0)
else:
    while(True):
        if x[i] + x[i + 1] == 1:
            k += 1
            del x[i + 1], x[i]
        if i + 2 >= len(x):
            ans += k
            if k == 0 or len(x) <= 1:
                break
            k = 0
            i = 0
        else:
            i += 1
    print(ans * 2)


### FIXED CODE ###

s = list(input())
x = list(map(int, s))
k = 0
for i in range(len(x)):
    if x[i] == 0:
        k += 1
print(2 * min(k, len(x) - k))
### BUGGY CODE ###

import sys

s = input()
K = int(input())
subs=[]
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        subs.append(s[i:j])

subset = set(subs)
subset = sorted(subset)
print(subset[K-1])


### FIXED CODE ###

import sys

s = input()
K = int(input())
subs=[]
for i in range(len(s)):
    for j in range(i+1,min(len(s)+1,i+K+1)):
        subs.append(s[i:j])

subset = set(subs)
subset = sorted(subset)
print(subset[K-1])
### BUGGY CODE ###

def func(line):
    lp = 0
    res = ""
    while lp + 1 < len(line):
        if line[lp] != line[lp + 1]:
            lp += 2
        else:
            res += line[lp]
            lp += 1
    if lp == len(line) - 1:
        res += line[-1]
    return res


def main():
    line = input()
    startsize = len(line)
    while True:
        next = func(line)
        if len(line) == len(next):
            break
        line = next
    lastsize = len(line)
    print(startsize - lastsize)


if __name__ == "__main__":
    main()



### FIXED CODE ###

def func(line):
    lp = 0
    res = []
    while lp < len(line):
        while len(res) > 0 and lp < len(line) and res[-1] != line[lp]:
            res.pop()
            lp += 1
        if lp < len(line):
            res.append(line[lp])
            lp += 1
    return res


def main():
    line = [i for i in input()]
    startsize = len(line)
    line = func(line)
    lastsize = len(line)
    print(startsize - lastsize)


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

S = input()
Q = int(input())
count = 0
left = ''
right = ''
for i in range(Q):
    arr = list(input().split())
    if len(arr) == 1:
        left,right=right[::-1],left[::-1]
        count += 1
    else:
        if arr[1] == '1':
            left = arr[2] + left
        else:
            right = right + arr[2]
if count%2 == 0:
    print(left+S+right)
else:
    print(left+S[::-1]+right)

### FIXED CODE ###

S = input()
Q = int(input())
count = 0
right = ''
left = ''
for i in range(Q):
    arr = list(input().split())
    if len(arr) == 1:
        count += 1
    else:
        if arr[1] == '1':
            if count%2==0:
                left = arr[2] + left
            else:
                right = right + arr[2]
        else:
            if count%2!=0:
                left = arr[2] + left
            else:
                right = right + arr[2]
S = left + S + right
if count%2 == 0:
    print(S)
else:
    print(S[::-1])
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline


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

table = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
#    print(a,b)
    table[a].append(b)
    table[b].append(a)

visited = [0]*N
visited[0] = 1
H = deque()
H.append(0)
ans = 0
c = 1

while H:
    ans = max(ans,c)
    x = H.popleft()
#    print("x:",x,"c:",c)
#    print(visited)
    for y in table[x]:
        if visited[y] == 0:
            H.append(y)
            visited[y] = 1
#            print(y,"added")
            c += 1
    if not H:
        for i in range(N):
            if visited[i] == 0:
                H.append(i)
                visited[i] = 1
                c = 1
                break

print(ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
        self._size = [1]*N
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_sama(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
            self._size[rb] += self._size[ra]
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]:
                self.rank[ra] += 1
            self._size[ra] += self._size[rb]
        self.count += 1
    def print_info(self):
        print("parent", self.parent)
        print("rank", self.rank)
        print("count", self.count)
        print("size", self._size)
    def size(self,a):
        return self._size[self.root(a)]

N, M = map(int,input().split())
uf = UnionFind(N)
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.unite(a,b)
ans = 0
for i in range(N):
    ans = max(ans,uf.size(i))
print(ans)
### BUGGY CODE ###

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

for i in range(n):
    b.append(a[i])
    b = b[::-1]
print(' '.join(map(str,b)))


### FIXED CODE ###

from collections import deque

n = int(input())
a = list(map(int,input().split()))
b = deque([a[0]])

for i in range(1,n):
    if i%2==(n-1)%2:
        b.appendleft(a[i])
    else:
        b.append(a[i])
    
print(' '.join(map(str,b)))
### BUGGY CODE ###

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

# スペース区切りの整数の入力
h, w, m = map(int, input().split())

h_list = [0]*h
w_list = [0]*w

h_w_list = [[0 for j in range(w)] for i in range(h)]
# h_w_list = []

for zzz in range(m):
  # print("---")
  bom_h, bom_w = map(int, input().split())
  # print(bom_h, bom_w)
  h_list[bom_h-1] += 1
  w_list[bom_w-1] += 1

  h_w_list[bom_h-1][bom_w-1] = "target"
  # h_w_list.append((bom_h, bom_w))

mh = max(h_list)
mw = max(w_list)
h_max_indexs = [i for i, v in enumerate(h_list) if v == mh]
w_max_indexs = [i for i, v in enumerate(w_list) if v == mw]

double_chance = False
# print("---")
for h_index in h_max_indexs:
  if double_chance:
    break
  for w_index in w_max_indexs:
    if double_chance:
      break
    chance = h_w_list[h_index][w_index] != "target"

    # print(h_index, w_index, chance)
    if chance:
      double_chance = True


if double_chance:
  result = h_list[h_index] + w_list[w_index]
else:
  result = h_list[h_index] + w_list[w_index] -1

print(result)


### FIXED CODE ###

H,W,M = map(int,input().split())
listh = [0] * H
listw = [0] * W
s = set()
for i in range(M):
    hm,wm = map(int,input().split())
    listh[hm-1] += 1
    listw[wm-1] += 1
    s.add((hm-1,wm-1))
mh = max(listh)
mw = max(listw)
maxh = [i for i,v in enumerate(listh) if v == mh]
maxw = [i for i,v in enumerate(listw) if v == mw]

import sys
for i in maxh:
    for j in maxw:
        if (i,j) not in s:
            print(mh + mw)
            sys.exit()
print(mh + mw - 1)
### BUGGY CODE ###

import sys

rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')

n, m, k = rm()
a = rl()
b = rl()

cnt = 0
lena = len(a)
lenb = len(b)
dp = [[inf]*(lenb + 1) for _ in range(lena + 1)]
dp[0][0] = 0
dp[0][1] = b[0]
dp[1][0] = a[0]

for i in range(lena):
    for j in range(lenb):
        dp[i][j+1] = dp[i][j] + b[j]
        dp[i+1][j] = dp[i][j] + a[i]
        if dp[i][j+1] <= k or dp[i+1][j] <= k:
            cnt = max(i+j+1, cnt)
else:
    if dp[lena][lenb-1] + b[lenb-1] <= k:
        cnt += 1
print(cnt)











### FIXED CODE ###

import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n, m, k = rm()
a = rl()
b = list(itertools.accumulate(rl()))
if a[0] > k:
    ans = 0
else:
    left = 0
    right = m
    while right - left > 1:
        j = (left + right) // 2
        if b[j] > k:
            right = j
        else:
            left = j
    ans = left + 1
t = 0
b0 = b[0]
for cnt, i in enumerate(a, 1):
    t += i
    if t > k:
        break
    if b0 > k-t:
        ans = max(ans, cnt)
        continue
    left = 0
    right = m
    while right - left > 1:
        j = (left + right) // 2
        if b[j] > k-t:
            right = j
        else:
            left = j
    ans = max(ans, cnt + left + 1)
print(ans)
### BUGGY CODE ###

def solve_dp(s):
    n = len(s)
    s = [int(c) for c in s]
    inf = 10**9

    dp = [[inf] * 2 for _ in range(n)]

    d0 = s[0]
    dp[0][0] = d0
    dp[0][1] = d0+1

    for i in range(1, n):
        d = s[i]
        for k in range(10):
            if d + k >= 10:
                dp[i][0] = min(dp[i][0], dp[i-1][1] + 2*k + d - 10)
            else:
                dp[i][0] = min(dp[i][0], dp[i-1][0] + 2*k + d)
        d += 1
        for k in range(10):
            if d + k >= 10:
                dp[i][1] = min(dp[i][1], dp[i-1][1] + 2*k + d - 10)
            else:
                dp[i][1] = min(dp[i][1], dp[i-1][0] + 2*k + d)

    return dp[n-1][0]

if __name__ == '__main__':
    s = input()
    s = "0"+ s
    print(solve_dp(s))

### FIXED CODE ###

Z = [0,1,2,3,4,5,6,7,8,9,10]
C = [0,1,2,3,4,5,6,7,8,9]
X = [0,1,2,3,4,5,6,7,8,9]

def solve_dp(s):
    n = len(s)
    s = [int(c) for c in s]
    inf = 10**9

    dp = [[inf] * 2 for _ in range(n)]

    d0 = s[0]
    dp[0][0] = Z[d0]
    dp[0][1] = Z[d0+1]

    for i in range(1, n):
        for j in range(2):
            d = s[i] + j
            for k in range(10):
                if d + C[k] >= 10:
                    dp[i][j] = min(dp[i][j], dp[i-1][1] + X[k] + Z[d + C[k] - 10])
                else:
                    dp[i][j] = min(dp[i][j], dp[i-1][0] + X[k] + Z[d + C[k]])

    return dp[n-1][0]

if __name__ == '__main__':
    s = input()
    s = "0"+ s
    print(solve_dp(s))