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

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
n = int(input())
s = str(n)

INF = float('inf')
dp = [[INF,INF] for _ in range(len(s)+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(len(s)):
    num = int(s[i])
    dp[i+1][0] = min(dp[i][0]+num, dp[i][1]+min(10-num,num+1))
    dp[i+1][1] = min(dp[i][0]+num+1,dp[i][1]+10-num-1)

print(dp[-1][0])


### FIXED CODE ###

s = input()
l = len(s)

INF = float('inf')
dp = [[INF]*2 for _ in range(l+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(l):
    num = int(s[i])
    dp0 = dp[i][0]
    dp1 = dp[i][1]
    dp[i+1][0] = min(dp0+num, dp1+min(10-num,num+1))
    dp[i+1][1] = min(dp0+num+1,dp1+10-num-1)

print(dp[-1][0])
### BUGGY CODE ###

l,r=map(int,input().split())

ans=float('inf')
for i in range(l,r):
    for j in range(i+1,r+1):
        ans=min(ans,i*j%2019)
        if ans==0:
            break
                
print(ans)

### FIXED CODE ###

l,r=map(int,input().split())

ans=2020
if r-l>=2019:
    ans=0
else:
    for i in range(l,r+1):
        for j in range(i+1,r+1):
            ans = min(ans,i*j%2019)
print(ans)
### BUGGY CODE ###

x = int(input())
A = [i for i in range(1, x//2+1)]
if sum(A) < x: print(x//2 + 1)
else: print(x//2)


### FIXED CODE ###

import math
x = int(input())
for i in range(1, x+1):
    if i*(i+1)//2 >= x:
        print(i)
        exit()
### BUGGY CODE ###

S=raw_input()
N=len(S)
mod=10**9+7

num=[ [ 0 for i in range(4) ] for j in range(N) ]		# i=0 A, i=1 B, i=2 C, i=3 ?

for i in range(N):
	if i==0:
		if S[i]=="A":  num[i][0]=1
		elif S[i]=="B":  num[i][1]=1		
		elif S[i]=="C":  num[i][2]=1
		elif S[i]=="?":  num[i][3]=1
	else:
		for j in range(4):
			num[i][j]=num[i-1][j]
			
		if S[i]=="A":  num[i][0]+=1
		elif S[i]=="B":  num[i][1]+=1		
		elif S[i]=="C":  num[i][2]+=1
		elif S[i]=="?":  num[i][3]+=1		

ans=0

for i in range(1,N):
	if S[i]=="B" or S[i]=="?":
		a=num[i-1][0]
		c=num[N-1][2]-num[i][2]
		ql=num[i-1][3]
		qr=num[N-1][3]-num[i][3]

		#ABC
		ans+=a*(3**ql)*c*(3**qr)%mod

		#AB?
		if qr>0:
			ans+=a*qr*(3**ql)*(3**(qr-1) )%mod

		#?BC
		if ql>0:
			ans+=(3**(ql-1) )*ql*c*(3**qr)%mod

		#?B?
		if ql>0 and qr>0:
			ans+=ql*(3**(ql-1) )*qr*(3**(qr-1) )%mod

print ans%mod



### FIXED CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M
### BUGGY CODE ###

import numpy as np

n,m = map(int,input().split())
a = np.array(list(map(int,input().split())))

for _ in range(m):
    idx = a.argmax()
    a[idx] = np.floor(a[idx]/2)
print(np.sum(a))

### FIXED CODE ###

import heapq

n,m = map(int,input().split())
a = list(map(lambda x:int(x)*(-1),input().split()))

heapq.heapify(a)

for _ in range(m):
    x = heapq.heappop(a) * -1
    x //= 2
    heapq.heappush(a,-1*x)
print(-sum(a))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
md = len(bin(max(a)))
ans = 0
for d in range(md):
    cnt1 = sum([1 for i in a if ((i>>d)&1)]) # a内の全ての要素の d bit目の1の個数を数える
    ans += cnt1 * (n-cnt1) * (1<<d)          # 求めるべきは (0の個数)*(1の個数)をd bit目にそのまま収めたものを足し合わせたもの (?)
    ans %= mod                               # mod 取っておく
    
print(ans%mod)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
import numpy as np
a=np.array(a)
mod = 10**9+7
md = len(bin(max(a)))
ans = 0
for d in range(md):
    cnt1 = np.count_nonzero((a>>d)&1)# a内の全ての要素の d bit目の1の個数を数える
    ans += cnt1 * (n-cnt1) * (1<<d)          # 求めるべきは (0の個数)*(1の個数)をd bit目にそのまま収めたものを足し合わせたもの (?)
    ans %= mod                               # mod 取っておく
    
print(ans%mod)
### BUGGY CODE ###

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

for i in range(1, n+1):
    ans = a.count(i)
    print(ans)

### FIXED CODE ###

n = int(input())
a = [-1, 1] + list(map(int, input().split()))
cnt = [0] * (n+1)

for i in range(2, n+1):
    cnt[a[i]] += 1

for i in range(1, n+1):
    print(cnt[i])
### BUGGY CODE ###

import re
number=input()
number=number.replace("?",".",100000)
length=len(number)
i=0
sumnum=0
while True:
    checknum=str(13*i+5)
    checklength=len(checknum)
    if checklength<length:
        while len(checknum)!=length:
            checknum="0"+checknum
 
    if len(checknum)==length:
        m=re.match(number,checknum)
        if m:
            sumnum+=1
            sumnum=sumnum%1000000007
    
            
    if len(checknum)>length:
        break
    i+=1
    
print(sumnum)

### FIXED CODE ###

#数字はnumberに格納
number=input()
length=len(number)


#調整のための数字
sizemin=1000000007

#まずはからのDPリストを用意
dp=[[0 for i in range(13)] for j in range(length)]

#1桁目の情報を入力
if number[-1]=="?":
    for i in range(10):
        dp[0][i]=1
else:
    dp[0][int(number[-1])]=1

#１０〜９０の、13modリストを作る
modlist=[(i*10)%13 for i in range(10)]


        
#二桁目からの情報を更新していく。
for n in range(length-1):
    #n桁目の情報があれば、次のようにn+1行目を更新。

    #n+1のくらいの数をchecknumとする
    checknum=number[-1*(n+1)-1]
#     print(checknum)

    #n+1の位が整数であれば
    if checknum!="?":
        
        #n[m]の値をn+1[m+(その整数)]にすればいい
        for m in range(13):
            dp[n+1][(m+modlist[int(checknum)])%13]=dp[n][m]
#         print(dp)
        
        
        
        
        
    #n+1のくらいが？の時
    else:
    #？が０〜９までの可能性を全て試す  
    
        for checknum in range(10):
            for m in range(13):
                dp[n+1][(m+modlist[int(checknum)])%13]=(dp[n+1][(m+modlist[int(checknum)])%13]+dp[n][m])%sizemin
#             print(dp)

    #modlistを更新
    modlist=[(j*10)%13 for j in modlist]


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

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import itertools
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N,K = MI()

A = LI()

multi = {}

start = 1
for k in range(0,K):
    start = start * A[k]

for j in range(K, N+1):
    if j == K:
        multi[j] = start
        continue
    start = start // A[j-K-1] * A[j-1]
    multi[j] = start

    if j-1 in multi:
        if multi[j] > multi[j-1]:
            print("Yes")
        else:
            print("No")



### FIXED CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import itertools
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N,K = MI()

A = LI()

for j in range(K, N+1):
    if j == K:
        continue
    if A[j-K-1] < A[j-1]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

(N, K) = list(map(int,input().split()))
P = list(map(int, input().split()))

def max_expected(L, K):
  length = len(L)
  if (length < K):
    return -1
  if (length == K):
    return (sum(L) + K) / 2
  mid = length // 2
  s_left = max_expected(L[0:mid], K)
  s_right = max_expected(L[mid:], K)
  offset = 0

  if (mid - K + 1 < 0):
    offset = - (mid - K + 1)
  end_offset = 0
  if (mid + K - 1 >= length):
    end_offset = mid + K - 1 - length
  max_p = sum(L[mid - K + 1 + offset:mid + 1 + offset])
  for i in range(mid - K + 1 + offset + 1, mid - end_offset):
    j = sum(L[i:(i + K)])
    if max_p < j:
      max_p = j
  
  return max((max_p + K) / 2, s_left, s_right)
print("{}".format(max_expected(P, K)))

### FIXED CODE ###

(N, K) = list(map(int,input().split()))
P = list(map(int, input().split()))

def max_expected(L, K):
  length = len(L)
  if (length < K):
    return -1
  if (length == K):
    return (sum(L) + K) / 2
  mid = length // 2
  s_left = max_expected(L[0:mid], K)
  s_right = max_expected(L[mid:], K)
  offset = 0

  if (mid - K + 1 < 0):
    offset = - (mid - K + 1)
  end_offset = 0
  if (mid + K - 1 >= length):
    end_offset = mid + K - 1 - length
  max_p = sum(L[mid - K + 1 + offset:mid + 1 + offset])
  prev = max_p
  for i in range(mid - K + 1 + offset + 1, mid - end_offset):
    prev = prev - L[i - 1] + L[i + K - 1]
    if max_p < prev:
      max_p = prev
  
  return max((max_p + K) / 2, s_left, s_right)
print("{}".format(max_expected(P, K)))
### BUGGY CODE ###

import copy
from collections import deque
n, q = map(int, input().split())
ab = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]

ad_list = [deque([]) for _ in range(n)]
for a, b in ab:
  ad_list[a].append(b)

count = [0 for _ in range(n)]

def dfs(v, x, ad):
  count[v] += x
  while ad[v]:
    if len(ad[v]) == 0:
      break
    ad_v = ad[v].pop()
    dfs(ad_v, x, ad)
    
for p, x in px:
  ad = copy.deepcopy(ad_list)
  dfs(p-1, x, ad)

print(*count)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.buffer.readline
def dfs(G,v,p):
    for nv in G[v]:
        if(nv==p):
            continue
        point[nv]+=point[v]
        dfs(G,nv,v)

N,Q=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
point=[0]*N
for i in range(Q):
    p,x=map(int,input().split())
    point[p-1]+=x
dfs(G,0,-1)
print(*point)
### BUGGY CODE ###

from collections import deque
import sys

def main():
    s = sys.stdin.readline().strip()
    qn = int(sys.stdin.readline().strip())
    qs = [input().split() for _ in range(qn)]

    c = cn = 0
    s = deque(s)

    for q in qs:
        if len(q) == 1:
            cn+=1
        else:
            if cn%2 == 1:
                s.reverse()
            cn = 0

        if len(q) == 3:
            if q[1] == '1':
                s.appendleft(q[2])
            else:
                s.append(q[2])
        c+=1

    if cn%2 == 1:
        s.reverse()
    print('%s' % ''.join(s))

if __name__ == "__main__":

    main()

### FIXED CODE ###

from collections import deque
import sys

def main():
    s = sys.stdin.readline().strip()
    qn = int(sys.stdin.readline().strip())
    qs = [input().split() for _ in range(qn)]

    s = deque(s)
    r = 1
    for q in qs:
        if len(q) == 1:
            r = r * -1

        else:
            if q[1] == '1':
                if r == 1:
                    s.appendleft(q[2])
                else:
                    s.append(q[2])
            else:
                if r == 1:
                    s.append(q[2])
                else:
                    s.appendleft(q[2])

    if r == 1:
        print(''.join(s))
    else:
        s.reverse()
        print(''.join(s))

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

n = int(input())
p = list(map(int, input().split())) 
count=0
for i in range(len(p)):
    if min(p[:(1+i)])==p[i]:
      count+=1
print(count)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split())) 
count=0
minmin=100000000
for i in range(len(p)):
  if p[i]<minmin:
    count+=1
    minmin=p[i]
print(count)
### BUGGY CODE ###

n, k, q = map(int, input().split())
L = [k]*n
for i in range(q):
  a = int(input())
  for j in range(n):
    L[j] -= 1
  L[a-1] += 1
    
for i in range(n):
  if L[i] > 0:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n, k, q = map(int, input().split())
L = [0]*n
for i in range(q):
  a = int(input())
  L[a-1] += 1
    
for i in range(n):
  if k - q + L[i] > 0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import queue
import copy
q = queue.Queue()
h, w = map(int, input().split())
a = [list('#'+input()+'#') for _ in range(h)]
a = [['#']*(w+2)]+a+[['#']*(w+2)]
a1 = copy.deepcopy(a)
ans = []
        
for i in range(1, h+1):
    for j in range(1, w+1):
        a = copy.deepcopy(a1)
        if a[i][j] == '#':
            continue        
        q.put([i, j, 0])
        while not q.empty():
            now = q.get()
            if a[now[0]][now[1]] == '.':
                ans.append(now[2])
                a[now[0]][now[1]] = '#'
            if a[now[0]+1][now[1]] != '#':
                q.put([now[0]+1, now[1], now[2]+1])
            if a[now[0]-1][now[1]] != '#':
                q.put([now[0]-1, now[1], now[2]+1])
            if a[now[0]][now[1]+1] != '#':
                q.put([now[0], now[1]+1, now[2]+1])
            if a[now[0]][now[1]-1] != '#':
                q.put([now[0], now[1]-1, now[2]+1])
        a1[i][j] == '#'
print(max(ans))


### FIXED CODE ###

import queue
import copy
q = queue.Queue()
h, w = map(int, input().split())
a = [list('#'+input()+'#') for _ in range(h)]
a = [['#']*(w+2)]+a+[['#']*(w+2)]
a1 = copy.deepcopy(a)
ans = []
        
for i in range(1, h+1):
    for j in range(1, w+1):
        a = copy.deepcopy(a1)
        if a[i][j] == '#':
            continue        
        q.put([i, j, 0])
        while not q.empty():
            now = q.get()
            
            if a[now[0]][now[1]] == '.':
                ans.append(now[2])
                a[now[0]][now[1]] = '#'
            else:
                continue
                
            if a[now[0]+1][now[1]] != '#':
                q.put([now[0]+1, now[1], now[2]+1])
            if a[now[0]-1][now[1]] != '#':
                q.put([now[0]-1, now[1], now[2]+1])
            if a[now[0]][now[1]+1] != '#':
                q.put([now[0], now[1]+1, now[2]+1])
            if a[now[0]][now[1]-1] != '#':
                q.put([now[0], now[1]-1, now[2]+1])
        a1[i][j] == '#'
print(max(ans))
### BUGGY CODE ###

from bisect import bisect_right
def inv_number(A):
    cnt = 0
    left = []
    for i, a in enumerate(A):
        j = bisect_right(left, a)
        cnt += i - j
        left.insert(j, a)
    return cnt
n = int(input())
print(inv_number(list(map(int, input().split()))))


### FIXED CODE ###

n = int(input())
A = [(i + 1, int(j)) for i, j in enumerate(input().split())]
A.sort(key=lambda x: -x[1])

class BIT:
    def __init__(self, n):
        self.data = [0] * (n + 1)
    def add(self, i, x):
        while i <= n:
            self.data[i] += x
            # 区間の長さ
            i += i & -i

    def get(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= i & -i
        return s

b = BIT(n)
ans = 0
for i, j in A:
    ans += b.get(i)
    b.add(i, 1)
print(ans)
### BUGGY CODE ###

N = int(input())
list_S = []
for i in range(N):
  list_S.append(str(input()))

list_get = []
for i in range(len(list_S)):
  if not list_S[i] in list_get:
    list_get.append(list_S[i])

print(len(list_get))

### FIXED CODE ###

N = int(input())
list_S = [str(input()) for i in range(N)]
print(len(list(set(list_S))))
### BUGGY CODE ###

S=list(input())

dp=[(i,0) for i in range(13)]
dp=dict(dp)
dp[0]=1

i=0
for k in reversed(S):
    dpcopy=dp.copy()
    dp=dict([(i,0) for i in range(13)])
    if k=='?':
        for s in range(10):
            p=(s * 10**(i))%13
            for j in range(13):               
                dp[(p + j) % 13] += dpcopy[j]%(10**9+7)
    else:
        k=int(k)
        p=(k * 10**(i))%13
        for j in range(13):
            dp[(p + j) % 13] += dpcopy[j]%(10**9+7)
    i += 1


print(dp[5]%(10**9+7))

### FIXED CODE ###

S = [int(x) if x != '?' else - 1 for x in input()]
le=len(S)

dp = [[0]*13 for i in range(le+1)]
dp[0][0] = 1

i=0
for k in S:
    if k==-1:
        for s in range(10):
            for j in range(13):
                dp[i + 1][(s + j*10) % 13] += dp[i][j]%(10**9+7)

    else:
        k=int(k)
        for j in range(13):
            dp[i + 1][(j *10 + k) % 13] += dp[i][j]%(10**9+7)
        
    i += 1


print(dp[le][5]%(10**9+7))
### BUGGY CODE ###

n = int(input())
mod = 10**9 + 7
lcm = 1
a_map = list(map(int, input().split()))
for a in a_map:
  p, q = lcm, a
  r = p % q
  while r > 0:
    p, q = q, r
    r = p % q
  lcm = lcm * a // q
b_sum = 0
for a in a_map:
  b_sum += lcm // a
  b_sum %= mod
print(b_sum)

### FIXED CODE ###

from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7

lcm = 1
for i in range(n):
  lcm = lcm * a[i] // gcd(lcm, a[i])
lcm %= mod

sum_b = 0
for i in range(n):
  sum_b = (sum_b + lcm * pow(a[i], mod - 2, mod)) % mod
print(sum_b)
### BUGGY CODE ###

N, W = map(int, input().split())
A = []
V = []
for i in range(N):
  a, v = map(int, input().split())
  A.append(a)
  V.append(v)

dp = [[0] * (W+1)]
for i in range(N)[::-1]:
  a = []
  for w in range(W+1):
    if A[i] > w:
      a.append(dp[-1][w])
    else:
      a.append(
        dp[-1][w]
        if dp[-1][w] > dp[-1][w-A[i]] + V[i]
        else dp[-1][w-A[i]] + V[i]
      )
  dp.append(a)

print(dp[-1][W])

### FIXED CODE ###

N, W = map(int, input().split())
A = []
V = []
for i in range(N):
  a, v = map(int, input().split())
  A.append(a)
  V.append(v)

dp = [0] * (W+1)
for i in range(N)[::-1]:
  a = dp[:]
  for w in range(W+1):
    if A[i] <= w and a[w] < dp[w-A[i]] + V[i]:
      a[w] = dp[w-A[i]] + V[i]
  dp = a

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

R,C,K=map(int,input().split())

Value=[[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r,c,v=map(int,input().split())
    Value[r][c]=v

DP=[[[0,0,0,0] for _ in range(C+1) ] for __ in range(R+1)]

for y in range(1,R+1):
    for x in range(1,C+1):
        #右に移動
        for k in range(0,3+1):
            DP[y][x][k]=DP[y][x-1][k]

        for k in range(1,3+1):
            DP[y][x][k]=max(DP[y][x][k],DP[y][x-1][k-1]+Value[y][x])

        #下に移動
        G=max(DP[y-1][x])
        DP[y][x][0]=max(DP[y][x][0],G)

        DP[y][x][1]=max(DP[y][x][1],DP[y][x][0]+Value[y][x])


print(max(DP[-1][-1]))

### FIXED CODE ###

R,C,K=map(int,input().split())

Value=[[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r,c,v=map(int,input().split())
    Value[r][c]=v

DP=[[0,0,0,0] for _ in range(C+1) ]

for y in range(1,R+1):
    #下に移動
    for x in range(1,C+1):
        DP[x][0]=max(DP[x])
        DP[x][1]=DP[x][0]+Value[y][x]
        DP[x][2]=DP[x][3]=0

    #右に移動
    for x in range(1,C+1):
        for k in range(0,3+1):
            DP[x][k]=max(DP[x][k],DP[x-1][k])

        for k in range(1,3+1):
            DP[x][k]=max(DP[x][k],DP[x-1][k-1]+Value[y][x])

print(max(DP[-1]))
### BUGGY CODE ###

import math
from functools import reduce

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

k = int(input())
sum = 0

for a in range(k):
    for b in range(k):
        for c in range(k):
            # print(a+1, b+1, c+1)
            sum += gcd(a+1, b+1, c+1)

print(sum)

### FIXED CODE ###

import math

k = int(input())
sum = 0

for a in range(k):
    for b in range(k):
        aandb = math.gcd(a+1, b+1)
        for c in range(k):
            sum += math.gcd(aandb, c+1)

print(sum)
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))

cnt = 0
for i in range(len(li) - 1):
    for j in range(i + 1, len(li)):
        if j - i == li[i] + li[j]:
            cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
li2 = [0] * n
li3 = [0] * n
cnt = 0
for i in range(len(li)):
    if i + li[i] < len(li):
        li2[i + li[i]] += 1
    if i - li[i] >= 0:
        li3[i - li[i]] += 1

for i in range(len(li)):
    if li2[i] > 0 and li3[i] > 0:
        cnt += li2[i] * li3[i]

print(cnt)
### BUGGY CODE ###

import sys
from heapq import heappush, heappop
from collections import defaultdict

N=input()
nl=[ [ float("inf") for j in range(N+1) ] for i in range(N+1) ] 

hq=[]
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	for j in range(i+1,N):
		heappush( hq, (L[j],i+1,j+1) )


ans=0
for n in range(N-1):
	cost,x,y,=heappop( hq )
	nl[x][y]=cost
	nl[y][x]=cost
	ans+=cost

def dij(start,end):
	d=defaultdict(lambda: float("inf")) 
	d[start]=0
	q=[]
	heappush( q, start )	#u: chouten

	while q:
		fro=heappop(q)
		for to in range(1,N+1):
			alt=d[fro]+nl[fro][to]
			if d[to]>alt:
				d[to]=alt
				heappush(q,to)
	return d[end]


while hq:
	cost,x,y,=heappop( hq )
	d=dij(x,y)

	if d<cost:
		print -1
		quit()
	elif cost<d:
		ans+=cost
	nl[x][y]=cost
	nl[y][x]=cost


print ans


### FIXED CODE ###

import numpy as np
N = input()
A = [np.array(map(int,raw_input().split()), dtype=np.int64) for _ in [0]*N]
inf = 10**10
for i in range(N):
    A[i][i] = inf
#print A


result = 0
for i in range(N-1):
    for j, d1 in enumerate(A[i][i+1:], start=i+1):
	#print i,j,A[i], A[j], np.min(A[i]+A[j]),d1
        d2 = np.min(A[i]+A[j])
        if d1 >= d2:
            if d1 > d2:
                print(-1)
                exit()
        else:
            result += d1
print(result)
### BUGGY CODE ###

n = int(input())
l = sorted(list(map(int,input().split())))

check_i = 0
check_j = 0
count = 0 

for i in reversed(range(0,n)):
    if l[i] == check_i:
        check_i = l[i]
        continue
    
    for j in reversed(range(1,i)):
        
        if l[j] == check_j:
            check_j = l[j]
            continue
        
        if l[i] - l[j] >= l[j-1]:
            continue
        
        low = 0
        high = j-1
        
        while low < high:
            
            mid = (low + high)//2
            
            if l[i] - l[j] >= l[mid]:
                
                low = mid +1
            
            else:    
                
                high = mid
        else:
            
            count += len(set(l[low:j]))
print(count)            

### FIXED CODE ###

from bisect import bisect_left

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

L.sort()
result = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        result += bisect_left(L, L[i] + L[j]) - j - 1
print(result)
### BUGGY CODE ###

n,m=map(int,input().split())
l=[[0] for _ in range(n+1)]
vi=[-1 for _ in range(n+1)]
vi[0]=1
for i in range (m):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
st=[[1,0]]

def bfs(x,i):
  if vi[x]==-1:
    vi[x]=i
    for k in l[x]:
      if vi[k]==-1:
        st.append([k,x])
  return

while st:
  x,i=st.pop(0)
  bfs(x,i)

print("Yes")
for m in vi[2:]:
  print(m)
  
  

### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
l=[[0] for _ in range(n+1)]
vi=[0 for _ in range(n+1)]
vi[1]=-1

for i in range (m):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
st=deque([1])
e=set()
f=set()


while st:
    x=st.popleft()
    if x not in e:
      e.add(x)
      for k in l[x]:
        if k not in f:
          st.append(k)
          f.add(k)
          vi[k]=x   
  
print("Yes")
for m in vi[2:]:
  print(m)
### BUGGY CODE ###

s = input()
import re
cnt = 0

while '01' in s or '10' in s:
    s = re.sub(r'01|10','', s, 1)
    cnt += 2
    continue

print(cnt)


### FIXED CODE ###

s = input()
leng = len(s)
zero = s.count('0')
one = s.count('1')
print(2*min(zero, one))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,W=map(int,input().split())
dp=[0]*(W+1)
for i in range(N):
  wi,vi=map(int,input().split())
  for w in range(W,wi-1,-1):
    dp[w]=max(dp[w],dp[w-wi]+vi)
print(dp[W])

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=np.int)
for n in range(1,N+1):
  wn, vn = map(int, input().split())
  dp[wn:]=np.maximum(dp[wn:], dp[:-wn]+vn)
print(dp[W])