Harryxun/stf_run huggingface dataset:
import sys
def input():
	return sys.stdin.readline()[:-1]
	
class BellmanFord():
	def __init__(self, adj, start, size):
		self.adj = adj
		self.start = start
		self.size = len(adj)
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0

	def solve(self):
		for _ in range(self.size-1):
			for x, y, w in self.adj:
				if self.dist[y] > self.dist[x] + w:
					self.dist[y] = self.dist[x] + w
		return

	#負閉路のせいでgoalへの距離が-infになるか
	def NegativeCycleToGoal(self, goal):
		res = self.dist[goal]
		for _ in range(self.size):
			for x, y, w in self.adj:
				if self.dist[y] > self.dist[x] + w:
					self.dist[y] = 10**30
		if self.dist[goal] > 10**20:
			return True
		return False

	def GetDistance(self, goal):
		return self.dist[goal]

n, m, p = map(int, input().split())
adj = []
for _ in range(m):
	a, b, c = map(int, input().split())
	adj.append((a-1, b-1, -c+p))

bf = BellmanFord(adj, 0, n)
bf.solve()
if bf.NegativeCycleToGoal(n-1):
	print(-1)
else:
	print(max(-bf.GetDistance(n-1), 0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**4)
def input():
	return sys.stdin.readline()[:-1]

class BellmanFord():
	def __init__(self, adj, start, size):
		self.adj = adj
		self.start = start
		self.size = size
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0

	def solve(self):
		for _ in range(self.size-1):
			for x in range(self.size):
				for y, w in self.adj[x]:
					if s_reachable[x] and s_reachable[y] and g_reachable[x] and g_reachable[y]:
						if self.dist[y] > self.dist[x] + w:
							self.dist[y] = self.dist[x] + w
		for x in range(self.size):
			for y, w in self.adj[x]:
				if s_reachable[x] and s_reachable[y] and g_reachable[x] and g_reachable[y]:
					if self.dist[y] > self.dist[x] + w:
						return False

		return True

	def GetDistance(self, goal):
		return self.dist[goal]

n, m, p = map(int, input().split())
adj = [[] for _ in range(n)]
adj_rev = [[] for _ in range(n)]

for _ in range(m):
	a, b, c = map(int, input().split())
	adj[a-1].append((b-1, -c+p))
	adj_rev[b-1].append(a-1)

s_reachable = [False for _ in range(n)]
s_reachable[0] = True
g_reachable = [False for _ in range(n)]
g_reachable[n-1] = True

def dfs_s(x):
	for v, w in adj[x]:
		if not s_reachable[v]:
			s_reachable[v] = True
			dfs_s(v)
	return

def dfs_g(x):
	for v in adj_rev[x]:
		if not g_reachable[v]:
			g_reachable[v] = True
			dfs_g(v)
	return

dfs_s(0)
dfs_g(n-1)

bf = BellmanFord(adj, 0, n)
if not bf.solve():
	print(-1)
else:
	print(max(-bf.GetDistance(n-1), 0))
def fun(N,V):
    cnt = 0

    for i in range(5):
        cnt += V // (5-i)
        V = V % 5
        if V == 0:
            break

    if cnt<=N:
        flag = False
        print(1)
    
    return flag

X = int(input())

flag = True
N = X//100
V = X-N*100

while flag:
    if N >= V/5:
        flag = fun(N,V)
        N -= 1
        V += 100
    else:
        flag = False
        print(0)

### FIXED CODE ###

def fun(N,V):
    cnt = 0

    for i in range(5):
        cnt += V // (5-i)
        V = V % (5-i)
        if V == 0:
            break

    if cnt<=N and V==0:
        flag = False
        print(1)
    else:
        flag = True
    
    return flag

def main():
    X = int(input())

    flag = True
    N = X//100
    V = X-N*100

    while flag:
        if N >= V/5:
            flag = fun(N,V)
            N -= 1
            V += 100
        else:
            flag = False
            print(0)

if __name__=='__main__':
    main()
s = input()
flag = False
for n in s :
	m = s.find(n)
	if s[m] == s[m+1] == s[m+2] :
		flag = True
		break
print("Yes" if flag else "No")

### FIXED CODE ###

s = input()
flag = False
for n in s :
	m = s.find(n)
	if m < len(s)-2 and s[m] == s[m+1] == s[m+2] :
		flag = True
		break
print("Yes" if flag else "No")
N = int(input())

gcd = lambda a, b: gcd(b, a % b)

lcm = lambda a, b: a * b // math.gcd(a, b)

lcm(2, N)

### FIXED CODE ###

N = int(input())

if N % 2 == 0:
    print(N)
else:
    print(2*N)
a, p, b = map(int, input().split())

if p == "+":
  print(a + b)
else:
  print(a - b)

### FIXED CODE ###

a, p, b = map(str, input().split())
a = int(a)
b = int(b)

if p == "+":
  print(a + b)
else:
  print(a - b)
n=ini(input())
h=[int(i) for i input().split()]
j=0
ans=0
while True:
  if h[0]>j:
    ans+=1
  for i in range(1,n):
    if h[i-1]<=j and h [i]>j:
      ans+=1
  j+=1
  if j==max(h):
    break
print(ans) 

### FIXED CODE ###

n=int(input())
h=[int(i) for i in input().split()]
j=0
ans=0
while j<max(h):
  if h[0]>j:
    ans+=1
  for i in range(1,n):
    if h[i-1]<=j and h [i]>j:
      ans+=1
  j+=1
print(ans)
I,O,_,J,L,_,_ = map(int,input().split())
ans1 = O + I-I%2 + J-J%2 + L-L%2
ans2 = 0
if I and J and K:
    I,J,K = I-1,J-1,K-1
    ans2 = 3 + O + I-I%2 + J-J%2 + L-L%2
print(max(ans1,ans2))

### FIXED CODE ###

I,O,T,J,L,S,Z = map(int,input().split())
p = 2*(I//2 + J//2 + L//2)
if I and J and L:
    p = max(p, 2*((I-1)//2 + (J-1)//2 + (L-1)//2) + 3)
print(O + p)
while True:
 x, y = map(int, input().split)
 if x == 0 and y == 0:
  brake
 
 elif x <= y:
  print(x, y)
 elif x >= y:
  print(y, x) 

### FIXED CODE ###

while True:
    x,y = map(int, input().split())
    if x == 0 and y == 0:
        break
    elif x <= y:
        print (x,y)
    else:
        print (y,x)
from itertools import combinations 
n,k=map(int,input().split())
m = (n-1)*(n-2)//2
if k>m:
    print(-1)
else:
    es = []
    for i in range(2,n+1):
        es.append(f'1 {i}')
        
    idx = 0
    for i,j in combinations(range(2,n+1),2):
        if idx == m-k:
            break
        es.append(f'{i} {j}')
        idx +=1
    print(len(es))
    print(*es,sep="\n")

### FIXED CODE ###

from itertools import combinations 
n,k=map(int,input().split())
m = (n-1)*(n-2)//2
if k>m:
    print(-1)
else:
    es = []
    for i in range(2,n+1):
        es.append((1,i))
        
    idx = 0
    for i,j in combinations(range(2,n+1),2):
        if idx == m-k:
            break
        es.append((i,j))
        idx +=1
    print(len(es))
    for i,j in es:
        print(i,j)
import sys
A,B=map(int,input().split())
if A<B:
  A,B=B,A
if B%A==0:
  print(A)
  sys.exit()
L=[]
for i in range(A/2):
  if A%i==0 and B%i==0:
    L.append(i)
print((a*b)/L[-1])

### FIXED CODE ###

import fractions as f
A,B=map(int,input().split())
print(int((A*B)/f.gcd(A,B)))
a, b, c, x = map(int, [input() for i in range(4)])
ans = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if i * 500 + j * 100 + k * 50 == x:
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
list = [int(x)  for x in input().split()]
ans = float('inf')
for a in list:
    ans = min(ans, len(bin(a))-bin(a).rfind('1')-1 )
print(ans)
import sys


def main(n: int, s: str):
    if n//2 != 0:
        print('No')

    if s[0:n/2] == s[n/2:]:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    args = [input() for i in range(2)]
    main(int(args[0]), args[1])


### FIXED CODE ###

import sys


def main(n: int, s: str):
    if n % 2 != 0:
        print('No')
        return

    p = int(n / 2)
    if s[:p] == s[p:]:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    args = [input() for i in range(2)]
    main(int(args[0]), args[1])
import math
def is_anagram(string1, string2):
  for a in string1:
    if a not in string2:
      return False
    string2 = string2.replace(a, "", 1)
  if len(string2) == 0:
    return True
  else:
    return False

N = int(input())
strings = [input() for i in range(N)]
ans = 0

for i in range(len(strings)-1):
  anagrams_index = []
  anagrams_num = 0
  for j in range(i+1, len(strings)):
    if i > len(strings) or j > len(strings):
      break
    if is_anagram(strings[i], strings[j]):
      anagrams_num += 1
      strings.pop(j)
  
  if anagrams_num == 1:
    ans +=1
  elif anagrams_num > 1:
    ans += int(math.factorial(anagrams_num+1)/math.factorial(anagrams_num)) 
print(ans) 

### FIXED CODE ###

import math
def is_anagram(string1, string2):
  for a in string1:
    if a not in string2:
      return False
    string2 = string2.replace(a, "", 1)
  if len(string2) == 0:
    return True
  else:
    return False

from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N = int(input())
anagrams = {}
for i in range(N):
  string = ''.join(sorted(input()))
  if string in anagrams:
    anagrams[string] += 1
  else:
    anagrams[string] = 0

ans = 0
for anagram_num in anagrams.values():
  if anagram_num> 0:
    ans += int(cmb(anagram_num+1,2)) 
print(ans)
n, m = map(int, input().split())
n_l = []
ans = [0, 0, 0]

for _ in range(n):
    l = list(map(int, input().split()))
    n_l.append(l)
for x in range(m):
    p = int(input())
    n_l[:][:][x]
for i in n_l:
    print(sum(i))


### FIXED CODE ###

n, m = map(int, input().split())
n_l = []
ans = [0, 0, 0]

for _ in range(n):
    l = list(map(int, input().split()))
    n_l.append(l)
for x in range(m):
    p = int(input())
    for o in range(n):
        n_l[o][x] *= p
for i in n_l:
    print(sum(i))
import sys

a = []

for line in sys.stdin:
    a.append(str(line))
for i in line:
    b = i.split()
    b = map(float, b)

    b_a = b[0]
    b_d = b[3]

    tmp_for_calc = b_a/b_d
    b_e = b[4] * tmp_for_calc
    b_f = b[5] * tmp_for_calc

    x = (b[2] - b_f)/(b[1] - b_e)

    y = (b[2] - b[1] * x)/b[0]

    print round(x, 3)
    print round(y, 3)

### FIXED CODE ###

while 1:
    def solver(a, b, c, d, e, f):
        answer = []

        if d == 0:
            y = f / e
            x = (c - b * y)/a

        else:
            m = a / d

            d = d * m
            e = e * m
            f = f * m

            y = (c - f)/(b - e)

            x = (c - b * y)/a

            if x == -0:
                x = 0
            if y == -0:
                y = 0

        answer.append(x)
        answer.append(y)
        return answer

    try:
        p_1, p_2, p_3, p_4, p_5, p_6 = map(float, raw_input().split())

        ans = []
        ans = solver(p_1, p_2, p_3, p_4, p_5, p_6)

        print "%.3f %.3f" % (ans[0], ans[1])

    except:
        break
a = int(input())
b = int(input())
c = int(input())
d = a + b
if c + d <= 21:
  print("win")
else:
  print("bust")

### FIXED CODE ###

a1, a2, a3 = map(int, input().split())
if a1 + a2 + a3 <= 21:
  print("win")
else:
  print("bust")
n=int(input())
v=[int(i) for i in input().split()]
v.sort()
mid=(v[0]+v[1])/2
for i in v[2,n]:
  mid=(mid+i)/2
print(mid)


### FIXED CODE ###

n=int(input())
v=[int(i) for i in input().split()]
v.sort()
mid=(v[0]+v[1])/2
for i in range(2,n):
  mid=(mid+v[i])/2
print(mid)
import numpy as np
import bisect

def bs(A, n):
    l=0
    r=len(A)
    while l<r:
        mid=int((l+r)/2)
        if A[mid]==n:
            return mid
        else:
            if n<A[mid]:
                r=mid
            else:
                l=mid+1

    return -1

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

T=int(input())
B=[int(j) for j in input().split()]

A.sort()

cnt=0
for i in range(T):
    x=bs(A,B[i])
    if x!=(-1):
        cnt=cnt+1

print(cnt)



### FIXED CODE ###


def bs(A, n):
    l=0
    r=len(A)
    while l<r:
        mid=int((l+r)/2)
        if A[mid]==n:
            return mid
        else:
            if n<A[mid]:
                r=mid
            else:
                l=mid+1

    return -1

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

T=int(input())
B=[int(j) for j in input().split()]

A.sort()

cnt=0
for i in range(T):
    x=bs(A,B[i])
    if x!=(-1):
        cnt=cnt+1

print(cnt)
input()
y = input().split()
y = [ int(x) for x in y]
sum_go = []
sum_back = []
for i in range(1, num):
    sum_go.append(sum(y[0:i] ))
    sum_back.append(sum(y[i:] ))
result = []
for i in range(len(sum_go)):
    result.append( abs(sum_go[i] - sum_back[i]) )
print(min(result))

### FIXED CODE ###

y = input()
y = input().split()
y = [ int(x) for x in y]
sum_go = []
sum_back = []
for i in range(1, len(y)):
    sum_go.append(sum(y[0:i] ))
    sum_back.append(sum(y[i:] ))
#print(sum_go)
#print(sum_back)
result = []
for i in range(len(sum_go)):
    result.append( abs(sum_go[i] - sum_back[i]) )
print(min(result))
n = int(input())
a = list(map(str,input().split()))
a.sort()
ans = 'YES'
for i in range(n):
    if a[i] == a[i+1]:
        ans = 'NO'
        break
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(str,input().split()))
a.sort()
ans = 'YES'
for i in range(n-1):
    if a[i] == a[i+1]:
        ans = 'NO'
        break
print(ans)
N=int(input().strip())
a=[0]*(N-1) # # of lines
b=[0]*(N-1)
#to=[[] for j in range(N-1)] # points
ans=[0]*(N-1)

class data:
    def __init__(self):
        self.to=[[] for j in range(N)] # N points
        self.id=[[] for j in range(N)] # N points

data=data()
for i in range(len(a)):
    a,b=list(map(int,input().strip().split()))
    a-=1
    b-=1
    data.to[a].append(b)
    data.id[a].append(i) # index of the line
    data.to[b].append(a)
    data.id[b].append(i)

#print(data.to)
def dfs(v,p,c_p): # vertices & parent idx & color from parent
    lst=data.to[v] # children list
    c=1
    for i,child in enumerate(lst):
        if child==p:
            continue
#        print('vertices=',v)
#        print('child=',child)
#        print('parent=',p)
        if c_p==c:
            c+=1
        ans[data.id[v][i]]=c
        c+=1
        dfs(child,v,c-1)
        

dfs(0,-1,-1)
print(max(ans))
for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

import sys #追加
sys.setrecursionlimit(500*500) #追加

N=int(input().strip())
a=[0]*(N-1) # # of lines
b=[0]*(N-1)
#to=[[] for j in range(N-1)] # points
ans=[0]*(N-1)

class data:
    def __init__(self):
        self.to=[[] for j in range(N)] # N points
        self.id=[[] for j in range(N)] # N points

def dfs(v,p,c_p): # vertices & parent idx & color from parent
    lst=data.to[v] # children list
    c=1
    for i,child in enumerate(lst):
        if child==p:
            continue
        if c_p==c:
            c+=1
        ans[data.id[v][i]]=c
        c+=1
        dfs(child,v,c-1)

data=data()
for i in range(len(a)):
    a,b=list(map(int,input().strip().split()))
    a-=1
    b-=1
    data.to[a].append(b)
    data.id[a].append(i) # index of the line
    data.to[b].append(a)
    data.id[b].append(i)

#print(data.to)

dfs(0,-1,-1)
print(max(ans))
for i in range(len(ans)):
    print(ans[i])
N = int(input())
D = list(map(int, input().split()))

ans = 0
for i in range(0, N):
    for j in range(i, N+1):
        ans += (D[i] * D[j])
print(ans)


### FIXED CODE ###

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

ans = 0
for i in range(0, N):
    for j in range(i+1, N):
        ans += (D[i] * D[j])
print(ans)
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    n = int(input())
    A = [int(input()) for _ in range(n)]
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)

### FIXED CODE ###

def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    import sys
    n = int(sys.stdin.readline())
    A = []
    for _ in range(n):
        A.append(int(sys.stdin.readline()))
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)
input_n=input()
input_s=input()
tmp=0
x = 0
for i in input_s:
  if i == "I":
    x=x+1
  else:
    x=x-1
  tmp=max(tmp,x)

print(tmp

### FIXED CODE ###

input_n=input()
input_s=input()
tmp=0
x = 0
for i in input_s:
  if i == "I":
    x=x+1
  else:
    x=x-1
  tmp=max(tmp,x)

print(tmp)
from collections import deque
n, m = map(int, input().split())
INF = 100000000

to = [] * m
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
print('Yes')
q = deque([])
dist = [INF] * n
pre = [-1] * n
dist[0] = 0
q.append(0)

while len(q) > 0:
    v = q.popleft()
    for i in to[v]:
        if dist[i] != INF:
            continue
        dist[i] = dist[v+1]
        pre[i] = v
        q.append(i)

for i in range(n):
    ans = pre[i]
    ans += 1
    print(ans)


### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
INF = 100000000

to = [[] for _ in range(100005)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
print('Yes')
q = deque([])
dist = [INF] * n
pre = [-1] * n
dist[0] = 0
q.append(0)

while len(q) > 0:
    v = q.popleft()
    for i in to[v]:
        if dist[i] != INF:
            continue
        dist[i] = dist[v] + 1
        pre[i] = v
        q.append(i)

for i in range(1, n):
    ans = pre[i]
    ans += 1
    print(ans)
S = list(input())

count = 0
for i,s in enumerate(S):
    if i!=0:
        if S[i-1] == s:
            count += 1
            if s == "0":
                S[i] = "1"
            else:
                S[i] = "0"
            print(S)
print(count)



### FIXED CODE ###

S = list(input())

count = 0
for i,s in enumerate(S):
    if i!=0:
        if S[i-1] == s:
            count += 1
            if s == "0":
                S[i] = "1"
            else:
                S[i] = "0"
print(count)
s = input()
if s[2] == s[3] and s[4] == s[5]:
  return "Yes"
else:
  return "No"

### FIXED CODE ###

s = input()
if s[2] == s[3] and s[4] == s[5]:
  print ("Yes")
else:
  print ("No")
import collections

N = int(input())
a = list(map(int,input()))

b = a[::2]
c = a[1::2]

b_ =collections.Counter(b)
c_ =collections.Counter(c)

baa = b_.most_common(b_)
caa = c_.most_common(c_)

baa.append([0,0])
caa.append([0,0])

if baa[0][0] != caa[0][0]:
    print(N - baa[0][1] - caa[0][1])
else:
    print(max(N - baa[0][1] - caa[1][1],N - caa[0][1] - baa[1][1]))


### FIXED CODE ###

import collections

N = int(input())
a = list(int(i) for i in input().split())

b = a[::2]
c = a[1::2]

b_ =collections.Counter(b)
c_ =collections.Counter(c)

baa = b_.most_common()
caa = c_.most_common()

baa.append([0,0])
caa.append([0,0])

if baa[0][0] != caa[0][0]:
    print(N - baa[0][1] - caa[0][1])
else:
    print(min(N - baa[0][1] - caa[1][1],N - caa[0][1] - baa[1][1]))
def main():
    n = [int(i) for i in input().split()]
    bridge = set()
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    
    preset = 0
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge = []
            counter += 1
        for j in range(preset, len(reqs)):
            if reqs[j][0] == i:
                bridge.add(reqs[j][1])
            else:
                preset = j
                break
    
    print(counter)

main()


### FIXED CODE ###

def main():
    cost_list = input().split()
    for i in range(len(cost_list)):
        cost_list[i] = int(cost_list[i])
    cost_list.sort()
    counter = 0
    for i in range(len(cost_list) - 1):
        counter += cost_list[i+1] - cost_list[i]
    print(counter)

main()
import sys
input = sys.stdin.readline

n=int(input())
l=[list(map(int,input().split())) for _ in [0]*(n-1)]
q,k=map(int,input().split())
L=[list(map(int,input().split())) for _ in [0]*q]

neighbor=[[] for _ in range(n+1)]
for i in range(n-1):
    neighbor[l[i][0]].append([l[i][1],l[i][2]])
    neighbor[l[i][1]].append([l[i][0],l[i][2]])

cost=[-1]*(n+1)
cost[k]=0
c=0

def sol(i,p,d):
    cost[i]=d
    for x in neighbor[i]:
        if x[0]!=p:
            sol(x[0],i,d+x[1])
sol(k,-1,0)

for i in range(q):
    print(cost[L[i][0]]+cost[L[i][1]])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n=int(input())
l=[list(map(int,input().split())) for _ in [0]*(n-1)]
q,k=map(int,input().split())
L=[list(map(int,input().split())) for _ in [0]*q]

neighbor=[[] for _ in range(n+1)]
for i in range(n-1):
    neighbor[l[i][0]].append([l[i][1],l[i][2]])
    neighbor[l[i][1]].append([l[i][0],l[i][2]])

cost=[-1]*(n+1)
cost[k]=0
c=0

def sol(i,p,d):
    global cost
    cost[i]=d
    for x in neighbor[i]:
        if x[0]!=p:
            sol(x[0],i,d+x[1])
sol(k,-1,0)

for i in range(q):
    print(cost[L[i][0]]+cost[L[i][1]])
n = int(input())

if n>400: exit()

l = [0]*n
r = [0]*n

for i in range(n):
    l[i], r[i] = list(map(int, input().split()))

N = 400+1
dp = [[0 for i in range(N)] for j in range(n)]

# 一番上のブロックを動かした時のコスト
for i in range(N):
    if r[0] < i: d = i-r[0]
    elif i < l[0]: d = l[0]-i
    else: d = 0
    dp[0][i] = d

# 順番にコストを計算していく
for ni in range(1,n+1):
    for i in range(N):
        if r[ni] < i: d = i-r[ni]
        elif i < l[ni]: d = l[ni]-i
        else: d = 0
        dp[ni][i] = d + dp[ni-1][i]
print(min(dp[n-1]))

### FIXED CODE ###

N = int(input())
P = [list(map(int, input().split())) for i in range(N)]
 
INF = 10**18
 
from heapq import heappush, heappop
 
l0, r0 = P[0]
 
L = [-l0+1]
R = [l0-1]
s = t = 0
 
res = 0
for i in range(N-1):
    l0, r0 = P[i]
    l1, r1 = P[i+1]
    s += (r1 - l1); t += (r0 - l0)
    if -s-L[0] <= l1-1 <= t+R[0]:
        heappush(L, -l1+1-s)
        heappush(R, l1-1-t)
    elif l1-1 < -s-L[0]:
        heappush(L, -l1+1-s)
        heappush(L, -l1+1-s)
        p = -heappop(L)-s
        heappush(R, p-t)
        res += (p - (l1-1))
    elif t+R[0] < l1-1:
        heappush(R, l1-1-t)
        heappush(R, l1-1-t)
        p = heappop(R) + t
        heappush(L, -p-s)
        res += (l1-1 - p)
print(res)
n,x=map(int,input().split())
a=list(int(input() for i in range(n)))
a_sort=sorted(a)
count=0
sum=0
for i in a_sort:
    if sum+i<=x:
        sum=sum+i
        count+=1
    else:
        break
print(count)

### FIXED CODE ###

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

count=0
if x==sum(a):
    print(n)
elif x>sum(a):
    print(n-1)
else:
    for i in range(n):
        if x>=a[i]:
            count+=1
            x-=a[i]
        else:
            break
    print(count)
N = int(input())

for i in range(math.ceil(math.sqrt(N)), 0, -1):
    if N % i == 0:
        print(len(str(N//i)))
        break

### FIXED CODE ###

import math
N = int(input())

for i in range(int(math.sqrt(N)), 0, -1):
    if N % i == 0:
        print(len(str(N//i)))
        break
a,p,b = list(map(int, input().split()))
if p == '+':
  print(a+b)
else:
  print(a-b)

### FIXED CODE ###

a,p,b = input().split()
a = int(a)
b = int(b)
if p == '+':
  print(a+b)
else:
  print(a-b)
S = input()
S[3] = '8'
print(S)

### FIXED CODE ###

S = list(input())
S[3] = '8'
a = ''.join(S)
print(a)