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

if __name__ == '__main__':
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(n)]
    ab = sorted(ab, key=lambda x: x[1], reverse=True)

    free_day = set(list(range(m + 1)))
    answer = 0
    for i in range(n):
        a = ab[i][0]
        b = ab[i][1]
        work_days = {day for day in free_day if m-day >= a}
        if len(work_days) != 0:
            free_day.remove(max(work_days))
            answer += b
    print(answer)


### FIXED CODE ###

from heapq import heappush, heappop


#  https://atcoder.jp/contests/abc137/submissions/6840855 を参考にした。
q = []
if __name__ == '__main__':
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(n)]
    ab = sorted(ab, reverse=True)

    q = []
    answer = 0
    for i in range(m-1, -1, -1):
        while ab and i + ab[-1][0] <= m:
            (a, b) = ab.pop()
            heappush(q, -b)

        if q:
            answer -= heappop(q)

    print(answer)
### BUGGY CODE ###

import itertools

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

matrix = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    l, r = map(int, input().split())
    matrix[l][r] += 1

totals = [[0] * (n + 1) for _ in range(n + 1)]
for i, j in itertools.product(range(1, n + 1), repeat=2):
    totals[i][j] += totals[i][j - 1] + matrix[i][j]

for _ in range(q):
    p, q = map(int, input().split())
    print(sum(totals[i][q] - totals[i][p - 1] for i in range(p, q + 1)))



### FIXED CODE ###

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

matrix = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    l, r = map(int, input().split())
    matrix[l][r] += 1

totals = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        totals[i][j] += totals[i][j - 1] + matrix[i][j]

answers = []
for _ in range(q):
    p, q = map(int, input().split())
    answer = sum(totals[i][q] - totals[i][p - 1] for i in range(p, q + 1))
    answers.append(answer)

for answer in answers:
    print(answer)
### BUGGY CODE ###

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

total = 0
blue = 0

for i in range(int(10e100)):
    if i % 2 == 0:  # blue
        total += a
        blue += a
        if total >= n:
            mod = total - n
            print(blue - mod)
            break
    else:  # red
        total += b
        if total >= n:
            print(blue)
            break

### FIXED CODE ###

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

x, mod = divmod(n, a + b)

if x == 0:
    print(min(a, n))
else:
    print(a * x + min(mod, a))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
#########入力系####################################################
"""
s =input()
s=list(input())
a=int(input())
x,y = map(int,input().split())	
li = input().split()	
li = list(map(int,input().split()))	
li = input().split('T')	
"""
##################################################################
N = int(input())
A = []
A  = list(map(int,input().split()))	
ans = 1
for i in A:
    ans = ans*i
if ans > 1000000000000000000:
    print("-1")
else:

    print(ans)
    

### FIXED CODE ###

N = int(input())
A = []
A  = list(map(int,input().split()))	
if A.count(0)!=0:
    print("0")
    exit()
ans = 1
for i in A:
    ans = ans*i
    if ans > 1000000000000000000:
        print("-1")
        exit()
print(ans)
### BUGGY CODE ###

from heapq import heappop, heappush
def main():
    H, W = map(int, input().split())
    sh,sw = map(int, input().split())
    gh,gw = map(int, input().split())
    gh,gw = gh-1,gw-1
    field = [list(input()) for _ in range(H)]

    q = [(0, sh-1, sw-1)]
    visited = set()
    while q:
        cnt, h, w = heappop(q)
        visited.add((h, w))
        if h == gh and w == gw: return cnt
        for i in range(-2, 3):
            for j in range(-2, 3):
                if h+i < 0 or w+j < 0: continue
                if h+i >= H or w+j >= W: continue
                if field[h+i][w+j]  == "#": continue
                if (h+i, w+j) in visited: continue
                if (i, j) in ((1,0),(0,1),(-1,0),(0,-1)):
                    heappush(q, (cnt, h+i, w+j))
                else:
                    heappush(q, (cnt+1, h+i, w+j))
    return -1

print(main())


### FIXED CODE ###

from collections import deque
def main():
    H, W = map(int, input().split())
    sh,sw = map(int, input().split())
    gh,gw = map(int, input().split())
    gh,gw = gh-1,gw-1
    field = [list(input()) for _ in range(H)]
    q = deque()
    q.append((0, sh-1, sw-1))
    INF = 10 ** 30
    dist = [[INF] * W for _ in range(H)]
    dist[sh-1][sw-1] = 0
    while q:
        cnt, h, w = deque.popleft(q)
        if dist[h][w] < cnt: continue
        if h == gh and w == gw: return cnt
        for i in range(-2, 3):
            for j in range(-2, 3):
                nh = h+i
                nw = w+j
                if nh < 0 or nw < 0: continue
                if nh >= H or nw >= W: continue
                if field[nh][nw]  == "#": continue
                if (i, j) in ((1,0),(0,1),(-1,0),(0,-1)):
                    if dist[nh][nw] <= cnt: continue
                    dist[nh][nw] = cnt
                    deque.appendleft(q, (cnt, nh, nw))
                else:
                    if dist[nh][nw] <= cnt+1: continue
                    dist[nh][nw] = cnt+1
                    deque.append(q, (cnt+1, nh, nw))
    return -1

print(main())
### BUGGY CODE ###

s = input()
n = int(input())
c = 0
left_l = ['', '']
right_l = ['', '']
s_l = [s, s[::-1]]
for _ in range(n):
  lst = [i for i in input().split()]
  if lst[0] == '1':
    if c == 1:
      s_l[0], s_l[1] = s_l[1], s_l[0]
      #print(s)
    else:
      s_l = [right_l[1] + s_l[1] + left_l[1], left_l[0] + s_l[0] + right_l[0]]
      left_l = ['', '']
      right_l = ['', '']
      c = 1
      #print(s)
  elif lst[0] == '2':
    c = 0
    if lst[1] == '1':
      left_l = [lst[2] + left_l[0], left_l[1] + lst[2]]
    elif lst[1] == '2':
      right_l = [right_l[0] + lst[2], lst[2] + right_l[1]]
w = left_l[0] + s_l[0] + right_l[0]
print(w)


### FIXED CODE ###

s = input()
n = int(input())
c = 0
left_l = ['', '']
right_l = ['', '']
s_l = [s, s[::-1]]
for _ in range(n):
  lst = [i for i in input().split()]
  if lst[0] == '1':
    if c == 1:
      s_l[0], s_l[1] = s_l[1], s_l[0]
      #print(s)
    else:
      s_l = [right_l[1] + s_l[1] + left_l[1], left_l[0] + s_l[0] + right_l[0]]
      left_l[0], left_l[1] = '', ''
      right_l[0], right_l[1] = '', ''
      c = 1
      #print(s)
  elif lst[0] == '2':
    c = 0
    if lst[1] == '1':
      left_l[0] = lst[2] + left_l[0]
      left_l[1] = left_l[1] + lst[2]
    elif lst[1] == '2':
      right_l[0] = right_l[0] + lst[2]
      right_l[1] = lst[2] + right_l[1]
w = left_l[0] + s_l[0] + right_l[0]
print(w)
### BUGGY CODE ###



H,N=map(int,input().split())
weight=[]
value=[]
for i in range(N):
    Ai,Bi=map(int,input().split())
    weight.append(Ai)
    value.append(Bi)
INF=100000001
#print(weight)
#print(value)


dp=[INF for i in range(H+1)]
dp[0]=0
for i in range(N):
    a=weight[i]
    b=value[i]
    for j in range(H+1):
        nj=min(j+a,H)
        dp[nj]=min(dp[nj],dp[j]+b)
print(dp[H])


### FIXED CODE ###


#import numpy as np

H,N=map(int,input().split())
weights=[list(map(int,input().split())) for _ in range(N)]
INF=100100101
#print(weight)
#print(value)

#print(weights)
dp=[INF]*(H+1)
for i in range(H+1):
    if i==0:
        dp[i]=0
    else:
        for j in weights:
            a=j[0]
            b=j[1]
            piv=max(0,i-a)  #use i-a's dp[] value as a pivot (if not exits(i-a<0), return dp[0])
            dp[i]=min(dp[i],dp[piv]+b) #the part which forcely treated as piv=0, returns min([weights]), other is treated as normal dp
    #print(dp)

print(dp[H])
### BUGGY CODE ###

n = input()
array = []
for i in range(n):
	inst = raw_input().split()
	if inst[0] == "insert":
		array.insert(0,inst[1])
	if inst[0] == "delete" and inst[1] in array:
		array.remove(inst[1])
	if inst[0] == "deleteFirst":
		del array[0]
	if inst[0] == "deleteLast":
		del array[len(array)-1]
print " ".join(i for i in array)

### FIXED CODE ###

n = input()
array = []
base = 0
for i in xrange(n):
    inst = raw_input().split()
    if inst[0][0] == 'i':
        array.append(int(inst[1]))
    elif inst[0] == "delete":
        if int(inst[1]) in array:
            x = array[::-1].index(int(inst[1]))
            if x != -1 and int(inst[1]):
                del array[-x-1]
    elif inst[0][6] == 'F':
        array.pop()
    else:
        base += 1
print (" ".join(map(str,array[base:][::-1])))
### BUGGY CODE ###

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

### FIXED CODE ###

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

import bisect
import numpy as np
n = int(input())
l_list = list(map(int,input().split()))
l_list = np.sort(l_list)
ans = 0
for i in range(n-2):
    for j in range(i+1 , n-1):
        ans += bisect.bisect_left(l_list,l_list[i] + l_list[j]) -j -1
        
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l_list = list(map(int,input().split()))
l_list.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1 , n-1):
        ans += bisect.bisect_left(l_list,l_list[i] + l_list[j]) -j -1
        
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def prison():
    N, M = (int(_) for _ in input().split())
    id_l = set(range(1, N+1))
    for _ in range(M):
        L, R = (int(_) for _ in input().split())
        id_l = id_l & set(range(L, R+1))
    return len(id_l)


print(prison())

### FIXED CODE ###

def prison():
    N, M = (int(i) for i in input().split())
    L_max = 0
    R_min = float("inf")
    for _ in range(M):
        L, R = (int(i) for i in input().split())
        L_max = max(L, L_max)
        R_min = min(R, R_min)
        result = max(R_min - L_max + 1, 0)
    return result


print(prison())
### BUGGY CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
 
i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

n,x,y = i_l()
x -= 1
y -= 1
a = []

for i in range(n):
    for j in range(i+1, n):
        a.append(min(abs(i-j), abs(x-i)+1+abs(y-j), abs(y-j)+1+abs(y-i)))
for i in range(1, n):
    count = a.count(i)
    if count>0:
        print(count)
    else:
        print(0)

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
 
i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

n,x,y = i_l()
x -= 1
y -= 1
a = [0]*n

for i in range(n):
    for j in range(i+1, n):
        b = min(abs(i-j), abs(x-i)+1+abs(y-j), abs(y-j)+1+abs(y-i))
        a[b] += 1
        
for i in a[1:]:
    print(i)
### BUGGY CODE ###

import string


def str2dic(str):
  dic = {c:0 for c in string.ascii_lowercase}
  for c in str:
    dic[c] += 1
  return dic

def is_anaglam(a, b):
  if a == b:
    return True
  return False


n = int(input().rstrip())
s = [str2dic(input().rstrip()) for _ in range(n)]

ans = 0
for i in range(n):
  for j in range(i+1, n):
    if is_anaglam(s[i], s[j]):
      ans += 1
print(ans)

### FIXED CODE ###

def sort_str(str):
  return ''.join(sorted(list(str)))

n = int(input().rstrip())
s = [sort_str(input().rstrip()) for _ in range(n)]

ans = 0
pool = {}
for i in range(n):
  if not s[i] in pool.keys():
    pool[s[i]] = 0
  else:
    pool[s[i]] += 1
    ans += pool[s[i]]
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[2]:


import copy


# In[10]:


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


# In[11]:


for i in range(N):
    x_copy = copy.deepcopy(X)
    del x_copy[i]
    ans = sorted(x_copy)[N//2-1]
    print(ans)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[25]:


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


# In[26]:


x1 = sorted(X)[N//2-1]
x2 = sorted(X)[N//2]
for i in range(N):
    if X[i] >= x2:
        print(x1)
    else:
        print(x2)


# In[ ]:
### BUGGY CODE ###

import itertools
N,K = map(int,input().split())
A = map(int,input().split())
t = list(list(itertools.combinations(A,K)))
ans = sum(t[0])
for i in t:
    ans = min(ans,sum(i))
print(ans)


### FIXED CODE ###

N,K = map(int,input().split())
A = sorted(map(int,input().split()))
print(sum(A[:K]))
### BUGGY CODE ###

n, p = map(int, input().split())
out=1
tm = int(pow(p, 1/n))
for i in range(2,tm+1):
    if i==2:
        while p%(i**n)==0:
            p = p//(i**n)
            out *= i
    elif i==3:
        while p%(i**n)==0:
            p = p//(i**n)
            out *= i
    elif i%2!=0 and i%3!=0:
        while p%(i**n)==0:
            p = p//(i**n)
            out *= i
        if p < i**n:
            break
print(out)

### FIXED CODE ###

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

if n==1:
    print(p)
else:
    out=1
    tm = int(pow(p, 1/n))
    for i in range(2,tm+1):
        while p%(i**n)==0:
            p = p//(i**n)
            out *= i
        if p < i**n:
            break
    print(out)
### BUGGY CODE ###

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

for i in range(k + 1):
    for j in range(k + 1):
        if s - i - j in range(k + 1):
            count += 1

print(count)


### FIXED CODE ###

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

for i in range(k + 1):
    for j in range(k + 1):
        if 0 <= s - i - j <= k:
            count += 1

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

from collections import deque

H, W = [int(i) for i in input().split()]
S = [input() for _ in range(H)]

white = sum(s.count(".") for s in S)

visited = [[False for _ in range(W)] for _ in range(H)]

Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

    visited[h][w] = True

    for nh, nw in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
        if not (0 <= nh < H and 0 <= nw < W):
            continue
        if S[nh][nw] != "#" and not visited[nh][nw]:
            Q.append((nh, nw, count + 1))
print(-1)



### FIXED CODE ###

from collections import deque

H, W = [int(i) for i in input().split()]
S = [list(input()) for _ in range(H)]

white = sum(s.count(".") for s in S)

S[0][0] = "_"
Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

    for nh, nw in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            S[nh][nw] = "_"
            Q.append((nh, nw, count + 1))
print(-1)
### BUGGY CODE ###

def main():
    n = int(input())
    ss = list(input())

    ans = float("inf")
    for i in range(n):
        ans_temp = 0
        for j in range(n):
            if j < i and ss[j] == 'W':
                ans_temp += 1
            if j > i and ss[j] == 'E':
                ans_temp += 1
            if ans_temp >= ans:
                break
        ans = min(ans, ans_temp)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    ss = list(input())

    ans = float("inf")
    ans = [0] * n
    cum_sum_w = [0] * (n+1)
    cum_sum_e = [0] * (n+1)
    for i in range(n):
        if ss[i] == 'W':
            add = 1
        else:
            add = 0
        cum_sum_w[i+1] = cum_sum_w[i] + add
    for i in range(n):
        if ss[i] == 'E':
            add = 1
        else:
            add = 0
        cum_sum_e[i+1] = cum_sum_e[i] + add
    for i in range(n):
        ans[i] = cum_sum_w[i] + (cum_sum_e[n] - cum_sum_e[i+1])
    print(min(ans))


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

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, W = map(int, input().split())

S = [input() for _ in range(H)]
NUM = [[[None] * 2 for _ in range(W)] for _ in range(H)]


def cntDot(r, c, vertical, cnt):
    #print("Input", r, c, vertical, cnt)
    if S[r][c] == '#':
        NUM[r][c][vertical] = 0
        return cnt
    else:
        cnt += 1

    # x軸
    if vertical == 0:
        if c < W - 1:
            t = cntDot(r, c + 1, vertical, cnt)
            NUM[r][c][vertical] = t
            return t
        else:
            NUM[r][c][vertical] = cnt
            return cnt

    # y軸
    if vertical == 1:
        if r < H - 1:
            t = cntDot(r + 1, c, vertical, cnt)
            NUM[r][c][vertical] = t
            return t
        else:
            NUM[r][c][vertical] = cnt
            return cnt

    return 0


for r in range(H):
    for c in range(W):
        # x軸
        if NUM[r][c][0] == None:
            NUM[r][c][0] = cntDot(r, c, 0, 0)
        # y軸
        if NUM[r][c][1] == None:
            NUM[r][c][1] = cntDot(r, c, 1, 0)

#print(NUM)

ans = 1
for r in range(H):
    for c in range(W):
        ans = max(NUM[r][c][0] + NUM[r][c][1] - 1, ans)

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# TLE
# O(HW(H+W)) で10^8になるので無理

H, W = map(int, input().split())

S = [input() for _ in range(H)]
NUM = [[0] * (W) for _ in range(H)]

for r in range(H):
    cnt = 0
    for c in range(W):
        if S[r][c] == '#':
            cnt = 0
        else:
            cnt += 1
            NUM[r][c] += cnt

    cnt = 0
    for c in range(W - 1, -1, -1):
        if S[r][c] == '#':
            cnt = 0
        else:
            cnt += 1
            NUM[r][c] += cnt

for c in range(W):
    cnt = 0
    for r in range(H):
        if S[r][c] == '#':
            cnt = 0
        else:
            cnt += 1
            NUM[r][c] += cnt

    cnt = 0
    for r in range(H - 1, -1, -1):
        if S[r][c] == '#':
            cnt = 0
        else:
            cnt += 1
            NUM[r][c] += cnt

ans = 4
for i in range(H):
    t = max(NUM[i])
    ans = max(ans, t)

print(ans-3)
### BUGGY CODE ###

import sys
import heapq

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

input = sys.stdin.readline
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
A = heapsort(A)

for _ in range(M):
    A[N-1] //= 2
    A = heapsort(A)

print(sum(A))

### FIXED CODE ###

import sys
import heapq

input = sys.stdin.readline
N, M = map(int, input().split())

A = []
for x in input().split():
    heapq.heappush(A, int(x) * (-1))

for _ in range(M):
    max_n = heapq.heappop(A) * (-1)
    heapq.heappush(A, (max_n // 2) * (-1))
    
print(sum(A) * (-1))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

def xor(a, b):
  return a^b

ans = 0
for i in range(N-1):
  for j in range(i + 1, N):
    ans += (xor(A[i] , A[j])) % MOD

print(ans%MOD)


### FIXED CODE ###

import numpy as np
n = int(input())
A = np.array(list(map(int, input().split())))
mod = 10 ** 9 + 7

ans = 0
for i in range(64):
    tmp = (A >> i) & 1
    #print(tmp)
    x = np.count_nonzero(tmp)
    x *= n - x
    ans += pow(2, i, mod) * x % mod

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

def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        # NG = 0
        a = j - i + 1 - K
        for m in XY[i:j + 1]:
            if y_min <= m[1] <= y_max:
                OK += 1
        if OK >= K:
            return True
        return False

    ans = 10 ** 20
    for i in range(N - 1):
        a = XY[i][0]
        for j in range(i + K - 1, N):
            b = XY[j][0]
            e = b - a
            for k in range(N):
                c = XY[k][1]
                for l in range(N):
                    d = XY[l][1]
                    if c < d:
                        if count(a, b, c, d, i, j):
                            # print ('A')
                            ans = min(ans, e * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

#PythonだとTLEする
N, K = map(int, input().split())
X = [0] * N
Y = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y

def count(x_min, x_max, y_min, y_max):
    cnt = 0
    for i in range(N):
        if x_min <= X[i] <= x_max and y_min <= Y[i] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                # print ('i, j , k, l = ', i, j, k, l)
                if X[i] < X[j] and Y[k] < Y[l]:
                    if count(X[i], X[j], Y[k], Y[l]) >= K:
                        # print ('A')
                        ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
print (ans)
### BUGGY CODE ###

def nCk(n,k,mod=10**9+7):
    if n<k or k<0 or n<0:return 0
    return fact[n]/fact[n-k]%mod * pow(fact[k],mod-2,mod) % mod

mod = 10**9+7
n=int(raw_input())
a=map(int,raw_input().split())
cnt=[0]*(n+1)
for i in xrange(n+1):
    cnt[a[i]]+=1
dnum=0
for i in xrange(n+1):
    if cnt[i]==2:
        dnum=i
        break
idx=[]
fact=[0]*(n+5)
fact[0]=1
for i in xrange(n+1):
    fact[i+1] = (i+1)*fact[i]
for i in xrange(n+1):
    if dnum==a[i]:
        idx.append(i)

y=n-idx[1]
x=idx[0]

for i in xrange(n+1):
    #print nCk(y,i)
    print (nCk(n+1, i+1) - nCk(y,i)-x*nCk(y,i-1)%mod)%mod


### FIXED CODE ###

from math import factorial
def nCk(n,k,mod=10**9+7):
    if n<k or k<0 or n<0:return 0
    return fact[n]*inv[n-k]*inv[k] % mod

mod = 10**9+7
n=int(raw_input())
a=map(int,raw_input().split())
cnt=[0]*(n+1)
for i in xrange(n+1):
    cnt[a[i]]+=1
dnum=0
for i in xrange(n+1):
    if cnt[i]==2:
        dnum=i
        break
idx=[]
fact=[0]*(n+5)
fact[0]=1
inv=[0]*(n+5)
inv[n+1]=pow(factorial(n+1), mod - 2, mod)
for i in xrange(n+1):
    fact[i+1] = (i+1)*fact[i]%mod
for i in xrange(n, -1, -1):
    inv[i] = inv[i+1]*(i+1)%mod
for i in xrange(n+1):
    if dnum==a[i]:
        idx.append(i)

y=n-idx[1]
x=idx[0]

for i in xrange(n+1):
    #print nCk(y,i)
    print (nCk(n+1, i+1) - nCk(x+y,i))%mod
### BUGGY CODE ###

s=int(input())
d=min(10**9,s)
while True:
  if s%d==0:
    break
  else:
    d-=1
print(0,0,d,0,0,s//d)

### FIXED CODE ###

s=int(input())
t=10**9
if s%t==0:
  print(0,0,1,t,s//t,0)
else:
  print(0,0,1,t,s//t+1,t-(s%t))
### BUGGY CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
li = list(int(stdin.readline().rstrip()) for _ in range(n))
one = max(li)
two = sorted(li)[-2]
for i in range(n):
    if max(li) == li[i]:
        print(two)
    else:
        print(one)

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
a_m = max(a)
a_i = a.index(a_m)
a.sort()
for i in range(len(a)):
  if i == a_i:
    print(a[-2])
  else:
    print(a_m)
### BUGGY CODE ###

# 解説放送

def main():
    inf = 18 * (10 ** 6 + 1)

    s = input()
    s = '0' + s

    n = len(s)

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

    for i, c in enumerate(s[::-1]):
        for j in range(2):
            for a in range(10):
                ni = i + 1
                nj = 0  # unpackをやめた
                x = int(c) + j
                b = a - x
                if b < 0:
                    nj = 1
                    b += 10
                dp[ni][nj] = min(dp[ni][nj], dp[i][j] + a + b)

    print(dp[n][0])


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 解説放送
# 写経

def main():
    inf = 18 * (10 ** 6 + 1)

    s = input()
    s = '0' + s

    n = len(s)

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

    for i, c in enumerate(s[::-1]):
        for j in range(2):
            x = int(c) + j
            if x < 10:
                dp[i + 1][0] = min(dp[i + 1][0], dp[i][j] + x)  # a=x,b=0
            if x > 0:
                dp[i + 1][1] = min(dp[i + 1][1], dp[i][j] + (10 - x))  # a=0,bに繰り下がり

    print(dp[n][0])


if __name__ == '__main__':
    main()