Harryxun/stf_run huggingface dataset:
if __name__=="__main__":
    sum = 0
    x,y = map(int,input().split())
    c = [list(map(int,input().split())) for n in range(10)]
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if c[i][j]>c[i][k]+c[k][j]:
                    c[i][j] = c[i][k]+c[k][j]

    for i in range(x):
        a = list(map(int,input().split()))
        for j in range(y):
            if a[j]!=-1:
                sum+=c[j][1]

    print(sum)




### FIXED CODE ###

def dijkstra(graph,src):
    if graph is None:
        return None
    nodes = [i for i in range(len(graph))]
    visited=[]
    if src in nodes:
        visited.append(src)
        nodes.remove(src)
    else:
        return None
    distance={src:0}
    for i in nodes:
        distance[i]=int(graph[src][i])
    path={src:{src:[]}}
    k=pre=src
    while nodes:
        mid_distance=float('inf')
        for v in visited:
            for d in nodes:
                new_distance = int(graph[src][v])+int(graph[v][d])
                if new_distance < mid_distance:
                    mid_distance=new_distance
                    graph[src][d]=str(new_distance)
                    k=d
                    pre=v
        distance[k]=mid_distance
        path[src][k]=[i for i in path[src][pre]]
        path[src][k].append(k)
        visited.append(k)
        nodes.remove(k)
    return distance

if __name__=="__main__":
    sum = 0
    s = input().split(" ")
    x, y = s[0], s[1]
    c = [n for n in range(0,10)]
    d = []
    matrix =[i for i in range(0,int(x))]*int(y)
    c[0] = list(input().split(" "))
    c[1] = list(input().split(" "))
    c[2] = list(input().split(" "))
    c[3] = list(input().split(" "))
    c[4] = list(input().split(" "))
    c[5] = list(input().split(" "))
    c[6] = list(input().split(" "))
    c[7] = list(input().split(" "))
    c[8] = list(input().split(" "))
    c[9] = list(input().split(" "))
    for m in range(0,10):
        d.append(dijkstra(c,m))
    for i in range(0,int(x)):
        matrix[i] = input().split(" ")
        for j in range(0,int(y)):
            n = int(matrix[i][j])
            if n==-1:
                continue
            else:
                sum = sum + int(d[n][1])
    print(sum)
N = int(input())
S = input().rstrip('#').lstrip('.')
def count(_S):
    # _S = input().rstrip('#').lstrip('.')
    if len(_S) == 0 :
        return 0
    numSW = _S.count('.')
    numSB = _S.count('#')
    SR = _S.lstrip('#').rstrip('.')
    numSR = len(_S) - len(SR)
    if numSW <= numSB and numSW <= numSR:
        return numSW
    elif numSB <= numSW and numSB <= numSR:
        return numSB
    else:
        return numSR + count(SR)
print(count(S))

### FIXED CODE ###

_ = input()
S = input()
numc = S.count('.')
numcmin = numc
for s in S:
    if s == '#':
        numc = numc + 1
    else:
        numc = numc -1
        if numc < numcmin:
            numcmin = numc
print(numcmin)
T = ['Sunny','Cloudy','Rainy']
S = input()
print(T[1]) if S == T[0] elif print(T[2]) if S == T[1] else print(T[0])

### FIXED CODE ###

T = ['Sunny','Cloudy','Rainy']
S = input()
print(T[1]) if S == T[0] else print(T[2]) if S == T[1] else print(T[0])
import sys

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

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    distance = [len(order_F[i]) for i in range(len(order_F))]
    dp_len = max(distance)
    vert_DP = [False] * (dp_len + 1)
    side_DP = [False] * (dp_len + 1)
    vert_DP[0] = True
    side_DP[0] = True
    vert_sum = 0
    side_sum = 0
    x -= distance[0]
    for i in range(1, len(order_F)):
        if i % 2 == 0:
            side_sum += distance[i]
            for j in reversed(range(dp_len + 1 - distance[i])):
                if side_DP[j]:
                    side_DP[j + distance[i]] = True
        else:
            vert_sum += distance[i]
            for j in reversed(range(dp_len + 1 - distance[i])):
                if vert_DP[j]:
                    vert_DP[j + distance[i]] = True
    if side_sum < x or vert_sum < y:
        print("No")
    elif (side_sum - x) % 2 == 1 or (vert_sum - y) % 2 == 1:
        print("No")
    else:
        if side_DP[(side_sum - x)//2] and vert_DP[(vert_sum - y)//2]:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

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

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    vert_DP = [False] * 8001
    side_DP = [False] * 8001
    vert_DP[0] = True
    side_DP[0] = True
    vert_sum = 0
    side_sum = 0
    distance = [len(order_F[i]) for i in range(len(order_F))]
    order_len = len(order_F)
    x -= len(order_F[0])
    vert_last = 0
    side_last = 0
    for i in range(1, order_len):
        if i % 2 == 0:
            side_sum += distance[i]
            for j in reversed(range(side_last+1)):
                if side_DP[j]:
                    side_DP[j + distance[i]] = True
            side_last += distance[i]
        else:
            vert_sum += distance[i]
            for j in reversed(range(vert_last+1)):
                if vert_DP[j]:
                    vert_DP[j + distance[i]] = True
            vert_last += distance[i]
    if side_sum < x or vert_sum < y:
        print("No")
    elif (side_sum - x) % 2 == 1 or (vert_sum - y) % 2 == 1:
        print("No")
    else:
        if side_DP[(side_sum - x)//2] and vert_DP[(vert_sum - y)//2]:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()
x = input()
print(x **3 )

### FIXED CODE ###

x = int(input())

print(x ** 3)
n, *p = map( int, open(0).read().split())

cnt = 0
for i in range( 1, len( p )+1):
  p_2 = p[ : i ]
  print( p[i-1], p_2 )
  if p[i-1] == min( p_2 ):
    cnt += 1
print( cnt )


### FIXED CODE ###

n, *p = map( int, open(0).read().split())
 
cnt = 0
min_val = 1000000
for i in range( len( p )):
  if p[i] < min_val:
    cnt += 1
    min_val = p[i]

print( cnt )
s=list(input())
if s[-1]=='s':
    print(s+'es')
else:
    print(s+'s')

### FIXED CODE ###

s=input()
if s[-1]=='s':
    print(s,'es',sep='')
else:
    print(s,'s',sep='')
n = int(input())
 
if n%2 == 0:
    print(0.5)   
else:
    s = (n-1)/2   
    s /= n　　　
print(1-s)   

### FIXED CODE ###

n = int(input())

if n%2 == 0:
    print(0.5)
else:
    print(1-(n-1)/2/n)
n,k = map(int,input().split())
A = list(map(int,input().split()))
B = []
b = 1
ans = 1
while ans:
  a = b
  b = A[a-1]
  B.append(b)
  if len(B) == k:
    ans = 0
  if B[-1] == B[-2]:
    ans = 0
cnt = k % len(B)
print(B[cnt])


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
pos = 0
visit = [0] * N
move = []
roop = []
while visit[pos]!=2:
    if visit[pos]==0:
        move.append(pos)
    else:
        roop.append(pos)
    visit[pos] += 1
    pos = A[pos] - 1
if len(move)>K:
    print(move[K]+1)
else:
    print(roop[(K-(len(move)-len(roop)))%len(roop)]+1)
n = int(input())
h = [int(i) for i in input().split()]
a = 0
for i in range(len(h)):
    if h[i] >= max(h[0:i-1]):
        a += 1
print(a)

### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]
a = 0
for i in range(len(h)):
    if i == 0:
        a += 1
    else:
        if h[i] >= max(h[0:i]):
            a += 1
print(a)
input()
T,A = map(int,input().split())
a = list(map(int,input().split()))
min_val = T-A
for i in range(len(a)):
    print("min_val={}".format(min_val))
    if abs(T-0.006*a[i]-A) <= min_val:
        min_val = abs(T-0.006*a[i]-A)
        min_num = i
print(min_num+1)

### FIXED CODE ###

N = int(input())
T,A = map(int,input().split())
H = list(map(int,input().split()))
 
x = 100000
ans = 0
 
for i in range(N):
    temp = abs(A -(T - H[i]*0.006))
    if abs(A -(T - H[i]*0.006)) < x:
        x = abs(A -(T - H[i]*0.006))
        ans = i
 
print(ans+1)
from collections import defaultdict


class Graph:
    def __init__(self, N):
        self.in_degree = [0] * (N+1)
        self.dist = [0] * (N+1)
        self.visited = [False] * (N+1)
        self.edges = defaultdict(list)
        self.N = N

    def add_edge(self, x, y):
        self.edges[x].append(y)
        self.in_degree[y] += 1

    def dfs(self, x):
        self.visited[x] = True
        for y in self.edges[x]:
            self.dist[y] = max(self.dist[y], self.dist[x] + 1)
            self.in_degree[y] -= 1
            if self.in_degree[y] == 0:
                self.dfs(y)

    def longest_path(self):
        for i in range(1, self.N+1):
            if not self.visited[i] and self.in_degree[i] == 0:
                self.dfs(i)

        ans = 0
        for i in range(1, self.N+1):
            ans = max(ans, self.dist[i])

        return ans


def main():
    N, M = map(int, input().split())
    graph = Graph(N)
    for _ in range(M):
        x, y = map(int, input().split())
        graph.add_edge(x, y)

    ans = graph.longest_path()
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

from collections import defaultdict



class Graph:

    def __init__(self, N):
        self.graph = defaultdict(list)
        self.N = N
        self.memo = [-1] * (N+1)
        self.tovisit = set(range(1, N+1))

    def add_edge(self, x, y):
        self.graph[x].append(y)

    def _longest_path(self, node):
        if self.memo[node] == -1:
            res = 0
            for y in self.graph[node]:
                res = max(res, 1 + self._longest_path(y))

            self.memo[node] = res
            self.tovisit.discard(node)

        return self.memo[node]

    def longest_path(self):
        while self.tovisit:
            self._longest_path(self.tovisit.pop())

        res = 0
        for i in range(1, self.N+1):
            res = max(res, self.memo[i])

        return res


def main():

    N, M = map(int, input().split())
    graph = Graph(N)
    for _ in range(M):
        x, y = map(int, input().split())
        graph.add_edge(x, y)

    ans = graph.longest_path()
    print(ans)


if __name__ == "__main__":
    main()
import math

A,B,C,D = map(int,input().split())
count = 0

QC = 0 #Cで割り切れる
QD = 0 #Dで割り切れる
QCD = 0 #CとDで割り切れる

CD = int(C * D / math.gcd(C, D)) #最大公約数
print(CD)

#約数の個数を求める
QC = (B // C) - (A // C)
if A % C == 0:
        QC += 1

QD = (B // D) - (A // D)
if A % D == 0:
        QD += 1

QCD = (B // CD) - (A // CD)
if A % CD == 0:
        QCD += 1

N = B-A+1
CorD = QC+QD-QCD

print(N-CorD)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd (a, b)

A,B,C,D = map(int,input().split())
count = 0

QC = 0 #Cで割り切れる
QD = 0 #Dで割り切れる
QCD = 0 #CとDで割り切れる

CD = lcm(C,D) #最大公約数

#約数の個数を求める
QC = (B // C) - (A // C)
if A % C == 0:
        QC += 1

QD = (B // D) - (A // D)
if A % D == 0:
        QD += 1

QCD = (B // CD) - (A // CD)
if A % CD == 0:
        QCD += 1

N = B-A+1
CorD = QC+QD-QCD

print(N-CorD)
N = int(input())
S = input()
def count(_S):
    _S = _S.rstrip('#').lstrip('.')
    if len(_S) == 0 :
        return 0
    numSW = _S.count('.')
    numSB = _S.count('#')
    SR = _S.lstrip('#').rstrip('.')
    numSR = len(_S) - len(SR)
    if numSW <= numSB and numSW <= numSR:
        return numSW
    elif numSB <= numSW and numSB <= numSR:
        return numSB
    else:
        return numSR + count(SR)
print(count(S))

### FIXED CODE ###

_ = input()
S = input()
numc = S.count('.')
numcmin = numc
for s in S:
    if s == '#':
        numc = numc + 1
    else:
        numc = numc -1
        if numc < numcmin:
            numcmin = numc
print(numcmin)
# coding: utf-8

import math
import sys
input = sys.stdin.readline

def gccd(num):
    if len(num) == 1:
        return num[0]
    else:
        return math.gcd(gccd(num[0:1]), gccd(num[1:]))

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

print(gccd(A))



### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

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

first_gcd = A[0]
for i in range(len(A)):
    first_gcd = gcd(first_gcd, A[i])

print(first_gcd)
s=input()

cnt=0

for i in range(4):
	if s[i]=='+':
	cnt+=1

res=2*i-4

print(res)

### FIXED CODE ###

s=input()
 
cnt=0
 
for i in range(4):
	if s[i]=='+':
		cnt+=1

res=cnt*2-4
 
print(res)
s=str(input())
s=list(s)
s=list(set(s))
s.sort()
if s[0]=="a" and s[1]=="b" and s[2]=="c":
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s=str(input())
s=list(s)
s=list(set(s))
s.sort()
if len(s)>=3:
  if s[0]=="a" and s[1]=="b" and s[2]=="c":
    print("Yes")
  else:
    print("No")
else:
  print("No")
x=input()
print x**3

### FIXED CODE ###

import sys

x = int( sys.stdin.readline() )
print( "{}".format( x**3 ) )
A = list((int(input().split())))
 
if sum(A) > 21:
  print('bust')
else:
  print('win')

### FIXED CODE ###

a = input()
b = a.split()

if int(b[0]) + int(b[1]) + int(b[2]) >= 22:
    print('bust')
    
else:
    print('win')
tmp = int(input())
#tmp = 100000

input_num = tmp

lst = []
while tmp > 0:
    lst.append(tmp % 10)  # 余りが入るから右の桁から処理される。　例 345/10 % = 5
    tmp //= 10  # 必須
lst.reverse()

# print(lst)

# print(input_num)

ketasuu = len(lst)
ans = 0
flag = 0
tmp = 0

kazoeru = ketasuu - 1

# 桁数が偶数のとき
if ketasuu % 2 == 0:
    for keta_num in reversed(range(kazoeru)):

        if flag == 0:
            tmp = (10 ** keta_num) * 9
            ans = ans + tmp
            # print("{} {}".format(ans,tmp))
            flag = 1
        else:
            flag = 0

elif ketasuu == 1:
    ans = input_num

# 桁数が奇数のとき
else:
    # print((10**ketasuu) * lst[0])
    ans = input_num - ((10 ** kazoeru) * lst[0])
    ans = ans + 1

    for keta_num in reversed(range(kazoeru - 1)):

        if flag == 0:
            tmp = (10 ** keta_num) * 9
            ans = ans + tmp
            # print("{} {}".format(ans,tmp))
            flag = 1
        else:
            flag = 0

print(ans)

### FIXED CODE ###

a, b, c = map(int, input().split())
x = a - b
ans = c - x
if ans <= 0:
    print(0)
else:
    print(ans)
# ？？？？？？？？？？？？？？？？？？？？？？？？？？

n = int(input())
# たしかpythonの辞書は順番も守ってくれた気がするのでソートしとく
a = sorted(list(map(int, input().split())))
d = {}
for av in a:
    if av not in d:
        d[av] = 1
    else:
        d[av] += 1

# if a[0] != 0 or d[0] != 1 or len(set(d.keys())) != a[-1] + 1: もしかしてこれの最後の条件のせい？？？？？？？？？？？？
# いやおかしいだろ 0から最大値まで揃ってなきゃ構築できねぇだろうが
if a[0] != 0 or d[0] != 1:
    print(0)
    exit()
MOD = 998244353
ans = 1
for i in range(2, a[-1] + 1):
    ans *= pow(d[i - 1], d[i], MOD)
print(ans % MOD)

### FIXED CODE ###

# ？？？？？？？？？？？？？？？？？？？？？？？？？？
# ケース12と13、完全にバグとしか思えないのですが?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

# もしかして：頂点1は必ず0？

n = int(input())
a = list(map(int, input().split()))
if a[0] != 0:
    print(0)
    exit()
a = sorted(a)
d = {}
for av in a:
    if av not in d:
        d[av] = 1
    else:
        d[av] += 1

if a[0] != 0 or d[0] != 1 or len(set(d.keys())) != a[-1] + 1:
    print(0)
    exit()
MOD = 998244353
ans = 1
for i in range(2, a[-1] + 1):
    ans *= pow(d[i - 1], d[i], MOD)
print(ans % MOD)
#
# abc071 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """6
3 1 2 4 2 1"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4
1 2 3 4"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10
3 3 3 3 4 4 4 5 5 5"""
        output = """20"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    A = list(map(int, input().split()))

    Num = [0] * N
    for a in A:
        Num[a-1] += 1

    l1 = l2 = 0
    for i in range(len(Num)-1, -1, -1):
        if l1 == 0:
            if Num[i] >= 2:
                l1 = i+1
            if Num[i] >= 4:
                l2 = i+1
                break
        else:
            if Num[i] >= 2:
                l2 = i+1
                break

    print(l1*l2)


if __name__ == "__main__":
    # unittest.main()
    resolve()


### FIXED CODE ###

#
# abc071 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """6
3 1 2 4 2 1"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4
1 2 3 4"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10
3 3 3 3 4 4 4 5 5 5"""
        output = """20"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    A = list(map(int, input().split()))

    A.sort(reverse=True)
    l1 = l2 = 0
    for i in range(1, N):
        if l1 == 0:
            if A[i] == A[i-1]:
                l1 = A[i-1]
        else:
            if i < N-1 and A[i+1] == A[i]:
                l2 = A[i]
                break

    print(l1*l2)


if __name__ == "__main__":
    # unittest.main()
    resolve()
cards = []
for suit in ('S','H','C','D'):
    for num in range(1,14):
        cards.append(suit+' '+str(num))

N = raw_input()

for n in range(N):
    suit, number = raw_input().split()
    cards.remove(suit+' '+y)


for card in cards:
    print card

### FIXED CODE ###

cards = []
for suit in ('S','H','C','D'):
    for num in range(1,14):
        cards.append(suit+' '+str(num))

N = int(raw_input())

for n in xrange(N):
    suit, number = raw_input().split()
    cards.remove(suit+' '+number)


for card in cards:
    print card
S = input()
s = len(S)
T = input()
t = len(T)
key = 0
for i in range(0,s-t+1):
    for j,k in enumerate(S[i:i+t]):
        if k == T[j] or k =="?":
            pass
        else:
            break
    else:
        key = i
        break
    key = 100
if key == 100:
    print("UNRESTORABLE")
else:
    ans = S[0:i]+T+S[i+t:]
    ans = ans.replace("?","a")
    print(ans)

### FIXED CODE ###

S = input()
s = len(S)
T = input()
t = len(T)

key = 0
for i in range(s-t,-1,-1):
    for j,k in enumerate(S[i:i+t]):
        if k == T[j] or k =="?":
            pass
        else:
            break
    else:
        key = i
        break
    key = 100
if key == 100 or s<t:
    print("UNRESTORABLE")
else:
    ans = S[0:i]+T+S[i+t:]
    ans = ans.replace("?","a")
    print(ans)
input()
s = list(map(int, input().split()))

cnt = 0
while True:
    if len(n for n in s if n % 2 != 0) != 0:
        print (cnt)
        break
    else:
        s = map(lambda n: n / 2, s)



### FIXED CODE ###

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

cnt = 0
while True:
    if len([n for n in s if n % 2 != 0]) != 0:
        print (cnt)
        break
    else:
        s = list(map(lambda n: n / 2, s))
        cnt = cnt + 1
# F - LIS on Tree
import bisect
import sys
sys.setrecursionlimit = 10**10

INF = 10**10

n = int(input())
a = list(int(x) for x in input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    #print(dp)
    #print('now',now)
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        #print('i',i)
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * (n+1)
dfs(0,-1)
for a in ans:
    print(a)

### FIXED CODE ###

# F - LIS on Tree
import bisect
import sys
sys.setrecursionlimit(10**7)

INF = 10**18

n = int(input())
a = list(int(x) for x in input().split())
g = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * n
dfs(0, -1)
for a in ans:
    print(a)
max_c = 0

for i in range(N):
#    print("------")
#    print(i)
    c = 0
    x_tmp = x_list.copy()
    v_tmp = v_list.copy()
    for j in range(i):
        c += v_tmp[j]
#        print(v_tmp[j],"を食べた")
        c -= x_tmp[j+1] - x_tmp[j]
#        print(c)
        if max_c < c:
            max_c = c
    
    x_tmp = x_tmp[i:]
    v_tmp = v_tmp[i:]
    
    v_tmp = v_tmp[::-1]
    
    x_tmp = [x_tmp[0]+C] + x_tmp[1:][::-1]
    
#    print(x_tmp)
#    print(v_tmp)
    
    for j in range(N - i):
        c += v_tmp[j]
#        print(v_tmp[j],"を食べた")
        c -= x_tmp[j] - x_tmp[j+1]
#        print(c)
        if max_c < c:
            max_c = c

### FIXED CODE ###

# kopipe
from numpy import array as n

N, C = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(N)]
r1, r2, l1, l2 = [0],[0],[0],[0]
sum = 0
for x, cal in xy:
    sum += cal
    r1.append(max(r1[-1], sum-x))
    r2.append(max(r2[-1], sum-2*x))
sum = 0
for x, cal in xy[::-1]:
    sum += cal
    l1.append(max(l1[-1], sum-C+x))
    l2.append(max(l2[-1], sum-2*(C-x)))
a = max(n(r1)+n(l2[::-1]))
b = max(n(r2)+n(l1[::-1]))
print(max(a,b))
ny = input()
n, y = [int(x) for x in ny.split(" ")]
min_y_1000 = y % 5000
min_n_1000 = math.floor(min_y_1000 / 1000)
match = [-1,-1,-1]
if y % 1000 == 0:
    for n_1000 in range(min_n_1000,max_n_1000 + 1, 5):
        y_2 = y - 1000 * n_1000
        n_2 = n - n_1000
        n_10000_n_5000_comb = calc_10000_5000_comb(n_2,y_2)
        if n_10000_n_5000_comb:
            match = n_10000_n_5000_comb + [n_1000]
            break
print(" ".join(map(str,match)))

### FIXED CODE ###

import math
def calc_10000_5000_comb(n2,y2):
    max_10000 = min(math.floor(y2 / 10000), n2)
    for n_10000 in range(max_10000 + 1)[::-1]:
        y5000 = y2 - 10000 * n_10000
        n_5000 = math.floor(y5000 / 5000)
        if n_5000 + n_10000 == n2:
            return [n_10000, n_5000]
        if n2 < n_5000 + n_10000:
            break
    return []
ny = input()
n, y = [int(x) for x in ny.split(" ")]
min_y_1000 = y % 5000
min_n_1000 = math.floor(min_y_1000 / 1000)
max_n_1000 = n
match = [-1,-1,-1]
if y % 1000 == 0:
    for n_1000 in range(min_n_1000,max_n_1000 + 1, 5):
        y_2 = y - 1000 * n_1000
        n_2 = n - n_1000
        n_10000_n_5000_comb = calc_10000_5000_comb(n_2,y_2)
        if n_10000_n_5000_comb:
            match = n_10000_n_5000_comb + [n_1000]
            break
print(" ".join(map(str,match)))
import math
N=int(input())
m=int(len(str(N)))
for j in range(2,math.int(sqrt(N))+1):
  a=j
  b=N//j
  m1=len(str(max(a,b)))
  m=min(m,m1)
print(m)

### FIXED CODE ###

import math
N=int(input())
m=int(len(str(N)))
for j in range(1,int(math.sqrt(N))+2):
    if N%j==0:
        a=j
        b=N//j
        m1=len(str(max(a,b)))
        m=min(m,m1)
print(m)