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

import sys, copy
from collections import deque
n = int(input())
a = [deque(map(lambda x:int(x) - 1, input().split())) for _ in range(n)]
q = deque()
pre_q = deque()
day = 0


def check(p, q):
    if not len(a[p]) == 0:
        o = a[p][0]
        if a[o][0] == p:
            if p < o and not (p, o) in q:
                q.append((p, o))
            elif not (o, p) in q:
                q.append((o, p))

for p in range(n):
    check(p, q)

while len(q) > 0:
    day += 1
    pre_q = copy.deepcopy(q)
    q.clear()
    for (p, o) in pre_q:
        a[p].popleft()
        a[o].popleft()
        check(p, q)
        check(o, q)


for i in range(n):
    if not len(a[i]) == 0:
        print(-1)
        sys.exit()

print(day)


### FIXED CODE ###

from collections import deque
import copy, sys

input = sys.stdin.readline
n = int(input())
a = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
q = deque()
pre_q = deque()
day = 0

def check(p, q):
    if not len(a[p]):
        return
    o = a[p][0]
    if p == a[o][0]:
        if p > o: p, o = o, p
        if not (p, o) in q:
            q.append((p, o))

fin = []
for p in range(n):
    if not p in fin:
        o = a[p][0]
        if p == a[o][0]:
            q.append((p, o))
            fin += [p, o]

while q:
    day += 1
    pre_q = copy.copy(q)
    q.clear()
    for (p, o) in pre_q:
        a[p].popleft()
        a[o].popleft()
        check(p, q)
        check(o, q)

if all(map(len, a)):
    print(-1)
else:
    print(day)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
 
N = int(input())
S = input()
 
ans = 0
for i in range(1000):
    pw = "0"*(3-len(str(i)))+str(i)
 
    w1 = -1
    for j in range(N-2):
        if S[j] == pw[0]:
            w1 = j
            break
    if w1 == -1:
        continue
 
    w2 = -1
    for j in range(w1+1, N-1):
        if S[j] == pw[1]:
            w2 = j
            break
    if w2 == -1:
        continue
 
    w3 = -1
    for j in range(w2+1, N):
        if S[j] == pw[2]:
            w3 = j
            break
    if w3 == -1:
        continue
 
    ans += 1
 
print(ans)

### FIXED CODE ###

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

N = int(input())
S = list(input())

ans = 0
for i in range(1000):
    pw = list("{0:03d}".format(i))

    if pw[0] in S:
        w1 = S.index(pw[0])
        if pw[1] in S[w1+1:]:
            w2 = w1+1 + S[w1+1:].index(pw[1])
            if pw[2] in S[w2+1:]:
                ans += 1

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

from sys import stdin
from itertools import accumulate

def solve():
    N = int(stdin.readline())
    img = tuple(tuple(map(int, line.split())) for line in stdin)
    
    acc_row = tuple(tuple(accumulate(line)) + (0,) for line in img)
    acc_col = tuple(tuple(accumulate(line)) + (0,) for line in zip(*img))
    
    ans = 0
    for i, tpl_1 in enumerate(zip(img, acc_row)):
        img_i, acc_row_i = tpl_1
        for j, tpl_2 in enumerate(zip(img[i:], acc_row[i:]), start=i):
            img_j, acc_row_j = tpl_2
            
            if acc_row_i[j] - acc_row_i[i - 1] > ans:
                ans = acc_row_i[j] - acc_row_i[i - 1]
                
            if i == j:
                continue
            
            col = acc_col[0]
            col_max = col[j] - col[i - 1]
            
            for acc_col_k, img_i_k, img_j_k in zip(acc_col[1:], img_i[1:], img_j[1:]):
                col = acc_col_k[j] - acc_col_k[i - 1]
                
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + img_i_k + img_j_k
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()


### FIXED CODE ###

from sys import stdin
from itertools import accumulate

def solve():
    file_input = stdin
    
    N = int(file_input.readline())
    G = tuple(tuple(map(int, line.split())) for line in file_input)
    G1 = tuple(t[1:] for t in G)
    
    # accumulated rows
    ar = ((0,) + tuple(accumulate(line)) for line in G)
    
    # accumulated columns
    ac = ((0,) + tuple(accumulate(line)) for line in zip(*G))
    ac_1 = next(ac)
    ac = tuple(zip(*ac))
    
    ans = 0
    for i, t1 in enumerate(zip(G1, ar, ac, ac_1)):
        G_i, ar_i, ac_i, ac_1i = t1
        ar_ii = ar_i[i]
        for j, t2 in enumerate(zip(G1[i:], ar_i[i+1:], ac[i+1:], ac_1[i+1:]), start=i):
            G_j, ar_ij, ac_j, ac_1j = t2
            single_row = ar_ij - ar_ii
            if single_row > ans:
                ans = single_row
                
            if i == j:
                continue
            
            col_max = ac_1j - ac_1i
            
            for ac_jk, ac_ik, G_ik, G_jk in zip(ac_j, ac_i, G_i, G_j):
                col = ac_jk - ac_ik
                
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + G_ik + G_jk
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()
### BUGGY CODE ###

from fractions import gcd


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


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

l = 1
for a in A:
    l = lcm(l, a)

l %= MOD

ans = 0
for a in A:
    ans += l * pow(a, MOD-2, MOD)
    ans %= MOD

print(int(ans))


### FIXED CODE ###

from fractions import gcd

mod = 10 ** 9 + 7

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

lcm = 1
for s in A:
    lcm = s * lcm // gcd(lcm, s)

ans = lcm * sum([pow(s, mod - 2, mod) for s in A]) % mod

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

import copy

N, M = map(int, input().split())
reqs = []
for _ in range(M):
    a, b = map(int, input().split())
    reqs.append((a, b))

count = 0
while len(reqs) > 0:
    copied_req = copy.deepcopy(reqs)
    _, idx = map(min, zip(*copied_req))
    for req in reqs:
        if req[0] < idx:
            copied_req.remove(req)
    count += 1
    reqs = copied_req
print(count)

### FIXED CODE ###

N, M = map(int, input().split())
reqs = []
ans = 0
B = 0
for _ in range(M):
    a, b = map(int, input().split())
    reqs.append((a, b))
reqs = sorted(reqs, key=lambda x: x[1])
for i in range(M):
    a, b = reqs[i]
    if a >= B:
        B = b
        ans += 1
print(ans)
### BUGGY CODE ###

a, b = (int(i) for i in input().split())  

b_bin = bin(b)
b_bin_num = len(b_bin[2:])

count_1 = [0]*b_bin_num

for i in range(a,b+1):
    i_bin = bin(i)[2:][::-1]
    for j in range(len(i_bin)):
        if i_bin[j] == "1":
            count_1[j] += 1

x_bin = ""
for i in count_1[::-1]:
    if i % 2 == 0:
        x_bin += "0"
    else:
        x_bin += "1"

x = int("0b"+x_bin, 0)

print(x)

### FIXED CODE ###

a, b = (int(i) for i in input().split())  

def f(a, b):
    num_len = b-a+1

    if num_len == 1:
        return b

    one_check = num_len if a % 2 == 0 else num_len-1

    x = (one_check // 2) % 2
    y = b if one_check % 2 == 1 else 0
    z = 0 if a % 2 == 0 else a
    return x^y^z

print(f(a,b))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    a, b = map(int, input().split())
    print(S[a-1:b].count('AC'))
    


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
a = [0]*(N+1)
for i in range(N):
    if S[i:i+2] == 'AC':
        a[i+1] = a[i] + 1
    else:
        a[i+1] = a[i]
for _ in range(Q):
    b, c = map(int, input().split())
    print(a[c-1]-a[b-1])
### BUGGY CODE ###

N=int(input())
# N=7
A=list(map(int,input().split()))
# A=sorted(A)
B=[]
for i in range(N):
    B=[j for j in A if j-1==i]
    print(len(B))
    B=[]

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
counter=[0]*N
for i in A:
    counter[i-1]+=1
print(*counter,sep='\n')
### BUGGY CODE ###

from collections import Counter


def get_dividers(n):
    """
    正の整数 n の約数を取得する
    """

    dividers = {i for i in range(1, int(n ** 0.5) + 1) if n % i == 0}
    return dividers | {n // d for d in dividers}


def lcm(a, b):
    """
    aとbの最小公倍数を計算する
    """
    from math import gcd

    return a * b // gcd(a, b)


N = int(input())
A = tuple(map(int, input().split(' ')))

counter = Counter()
for a in A:
    for d in get_dividers(a):
        counter[d] += 1

ans = 1
candidates = []
for key, value in counter.items():
    if value == N:
        ans = lcm(ans, key)
    elif value == N - 1:
        candidates.append(key)

if candidates:
    ans = max([lcm(ans, c) for c in candidates])

print(ans)


### FIXED CODE ###

from collections import Counter
from functools import lru_cache


@lru_cache(maxsize=None)
def get_dividers(n):
    """
    正の整数 n の約数を取得する
    """

    dividers = {i for i in range(1, int(n ** 0.5) + 1) if n % i == 0}
    return dividers | {n // d for d in dividers}


@lru_cache(maxsize=None)
def lcm(a, b):
    """
    aとbの最小公倍数を計算する
    """
    from math import gcd

    return a * b // gcd(a, b)


N = int(input())
A = tuple(map(int, input().split(' ')))

counter = Counter()
for a in A:
    for d in get_dividers(a):
        counter[d] += 1

ans = 1
candidates = []
for key, value in counter.items():
    if value == N:
        ans = lcm(ans, key)
    elif value == N - 1:
        candidates.append(key)

if candidates:
    ans = max([lcm(ans, c) for c in candidates])

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

def uauau():
    N = int(input())
    aA=sorted(set(int(_) for _ in input().split()))
    N = len(aA)
    def ggg(i,j):
        i %= j
        if i == 0:
            return j
        else:
            return ggg(j,i)

    if len(aA) == 1:
        print(aA[0])
    else:
        iMin = aA[0]
        iMax = aA[-1]
        if iMin  == 1:
            print(1)
        else:
            if False:
                pass
            #if max(i % iMin for i in aA) == 0:
            #   print(iMin)
            #   exit()
            else:
                iM = iMax
                for i in range(N):
                    iA = aA[i]
                    for j in range(i+1,N):
                        iMt = ggg(aA[j],iA)
                        if 0 < iMt and iMt < iM:
                            iM = iMt
                    if iM == 1:
                        print(1)
                        exit()
                print(iM)
uauau()


### FIXED CODE ###

#gcdか....
def fgcd(a,b):
    while b:
        a,b = b,a%b
    return a

N = int(input())
aA = sorted(set(int(_) for _ in input().split()))
b = aA[0]
for a in aA[1:]:
    b = fgcd(a,b)
print(b)
### BUGGY CODE ###

from itertools import accumulate
from bisect import bisect_left
N = int(input())
A = list(map(int, input().split()))
A = list(accumulate(A))

ans = float('inf')
# 切る位置を全探索
for mid in range(2, N - 1):
    L, R = A[:mid], A[mid:]
    L_target, R_target = L[-1] / 2, (L[-1] + R[-1]) / 2
    L_index, R_index = bisect_left(L, L_target), bisect_left(R, R_target)

    if abs(L[L_index - 1] - L_target) < abs(L[L_index] - L_target):
        L_index -= 1
    if abs(R[R_index - 1] - R_target) < abs(R[R_index] - R_target):
        R_index -= 1

    P, Q, R, S = L[L_index], L[-1]-L[L_index], R[R_index]-L[-1], R[-1]-R[R_index]
    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))

print(ans)


### FIXED CODE ###

from itertools import accumulate
from bisect import bisect_left
N = int(input())
A = list(map(int, input().split()))

accSum = list(accumulate(A))
ans = float('inf')
for m in range(1, N):
    # 左
    Lm = accSum[m] // 2
    Lx = bisect_left(accSum, Lm)
    if abs(accSum[Lx] - Lm) > abs(accSum[Lx - 1] - Lm):
        Lx -= 1

    # 右
    Rm = (accSum[m] + accSum[-1]) // 2
    Rx = bisect_left(accSum, Rm)
    if abs(accSum[Rx] - Rm) > abs(accSum[Rx - 1] - Rm):
        Rx -= 1

    P, Q, R, S = accSum[Lx], accSum[m] - accSum[Lx], accSum[Rx] - accSum[m], accSum[-1] - accSum[Rx]
    ans = min(ans, max(P, Q, R, S) - min(P, Q, R, S))

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

s = str(input())
K = int(input())

s2 = ''.join(sorted(set(list(s))))

l = []

for i in range(len(s2)):
  for j in range(len(s)):
    if s2[i] == s[j]:
      for k in range(j+1, len(s)+1):
        l.append(s[j:k])
l = list(set(l))
l.sort()
print(l[K-1])

### FIXED CODE ###

s = str(input())
K = int(input())

s2 = ''.join(sorted(set(list(s))))

l = []

for i in range(len(s2)):
  if len(set(l)) >= K:
    #print(i)
    break
  else:
    for j in range(len(s)):
      if s2[i] == s[j]:
        for k in range(j+1, len(s)+1):
          if k-j > K:
            break
          else:
            l.append(s[j:k])
l = list(set(l))
l.sort()
#print(l)
print(l[K-1])
### BUGGY CODE ###

def lcs_len(x, y):
    ly = len(y)
    tcsl = [0 for i in range(ly + 1)]
    for x_i in x:
        pre_tcsl = list(tcsl)
        for j in range(ly):
            if x_i == y[j]:
                tcsl[j] = pre_tcsl[j - 1] + 1
            else:
                tcsl[j] = max(pre_tcsl[j], tcsl[j - 1])
    print(tcsl[j])


q = int(input())

for i in range(q):
    ax = input()
    ay = input()
    lcs_len(ax, ay)

### FIXED CODE ###

def lcs_len(x, y):
    indices = [0]
    for y_i in y:
        t_index = 0
        for i, index in enumerate(indices, 1):
            c_index = x.find(y_i, t_index) + 1
            if c_index:
                if i < len(indices):
                    t_index = indices[i]
                    indices[i] = min(c_index, t_index)
                else:
                    indices.append(c_index)
                    break
    print(len(indices) - 1)


q = int(input())

for i in range(q):
    ax = input()
    ay = input()
    lcs_len(ax, ay)
### BUGGY CODE ###

num = int(input())
power = 1

for i in range(1,num+1):
  power *= i
print(power % (pow(10,9) + 7))

### FIXED CODE ###

import math
num = int(input())
power = math.factorial(num)

print(power % (pow(10,9) + 7))
### 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 = [[0 if x == '.' else 1 for x in list(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] == 1:
        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 ###

n=int(input())
a = list(map(int, input().split()))
memo = {}
x = []
for i in a:
    xx = {}
    for j in range(2, int(i**.5)+2):
        if i%j==0:
            c=0
            while i%j==0:
                c += 1
                i //= j
            if j in memo:
                memo[j] = max(memo[j], c)
            else:
                memo[j] = c
            xx[j] = c
    if i!=1:
        xx[i]=1
        if i in memo:
            memo[i] = max(memo[i], 1)
        else:
            memo[i] = 1
    x.append(xx)
mod = 10**9+7
result = 0
for i in range(n):
    num = 1
    for s, t in memo.items():
        if s in x[i]:
            num *= pow(s, t-x[i][s])
        else:
            num *= pow(s,t)
    if result+num >= mod:
        result = (result+num)%mod
    else:
        result += num
print(result)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

mod = 10**9 + 7
memo = defaultdict(int)
base = 0
for i in a:
    base = (base+pow(i, mod-2, mod))%mod
    num = i
    for j in range(2, int(i**.5)+1):
        if num%j==0:
            c = 0
            while num%j==0:
                num //= j
                c += 1
            memo[j] = max(memo[j], c)
    if num != 1:
        memo[num] = max(memo[num], 1)
k = 1
for s, t in memo.items():
    k = (k*pow(s, t, mod))%mod

print((k*base)%mod)
### BUGGY CODE ###

N = int(input())
num_list = list(map(int, input().split()))
for i in num_list:
  count = num_list.count(i)
  if count >= 2:
    print('NO')
    exit()
print('YES')

### FIXED CODE ###

N = int(input())
num_list = list(map(int, input().split()))
num_list = sorted(num_list)

for i in range(len(num_list)):
  if i == N-1:
    print('YES')
  elif num_list[i] == num_list[i+1]:
    print('NO')
    exit()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)

def fuctorial(n):
    if n <1:
        return 1
    return n * fuctorial(n-1)

def combination(n, k):
    return fuctorial(n) // (fuctorial(n-k) * fuctorial(k))


N, K = map(int, input().split())
MOD = 10**9+7
for i in range(1,K+1):
    print(combination(N - K + 1, i) * combination(K - 1, i - 1) % MOD)


### FIXED CODE ###

def fuctorial(n):
    ret = 1
    while n > 0:
        ret *= n
        n -= 1
    return ret

def combination(n, k, MOD):
    return (fuctorial(n) // (fuctorial(n-k) * fuctorial(k)))%MOD


def main():
    N, K = map(int, input().split())
    MOD = 10**9+7
    for i in range(1, K + 1):
        if i > N - K + 1:
            print(0)
        else:
            print(combination(N - K + 1, i,MOD) * combination(K - 1, i - 1,MOD) % MOD)

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

n=int(input())
cnt=0
if n==1:
  print(0)
else:
  for i in range(1,n):
    cnt+=i%(i+1)
  print(cnt)

### FIXED CODE ###

n=int(input())
if n==1:
  print(0)
else:
  print(n*(n-1)//2)
### BUGGY CODE ###

from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7




def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    f = list(map(int, input().split()))
    a.sort()
    f = sorted(f,reverse=True)

    def ok(v):
        cnt = 0
        sa = 0
        for i in range(n):
            t = a[i]*f[i]
            if v - t >= 0:
                continue
            cnt += a[i] - (v // f[i])
            if cnt > k:
                break
        
        if cnt <= k:
            return True
        else:
            return False





    l, r = 0, 10 ** 19
    for i in range(200):
        m = (l + r) / 2
        if ok(m):
            r = m
        else:
            l = m
    print(int(m))

    
            
    

    

    

if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7




def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    f = list(map(int, input().split()))
    a.sort()
    f = sorted(f,reverse=True)

    def ok(v):
        cnt = 0
        sa = 0
        for i in range(n):
            t = a[i]*f[i]
            if v - t >= 0:
                continue
            cnt += a[i] - (v // f[i])
            if cnt > k:
                return False
        
        if cnt <= k:
            return True
        else:
            return False





    l, r = 0, 10 ** 18
    for i in range(80):
        m = (l + r) // 2
        if ok(m):
            r = m
        else:
            l = m
    print(r)

    
            
    

    

    

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

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

### FIXED CODE ###

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

N,K =map(int,input().split())
R,S,P = map(int,input().split())
T =input()
ans = 0
for i in range(len(T)):
    if T[i] == "r":
        ans += P
    elif T[i] == "s":
        ans += R
    else:
        ans += S
for i in range(len(T)-K):
    if T[i] == T[i+K] :
        if T[i] == "r":
            ans -= P
        elif T[i] == "s":
            ans -= R
        else:
            ans -= S
        T = T[:i+K] + "R" + T[i+K+1:]
print(ans)

### FIXED CODE ###

N,K =map(int,input().split())
R,S,P = map(int,input().split())
T =input()
ans = 0
chk_list = [0] * len(T)
for i in range(len(T)):
    if i < K:
        if T[i] == "r":
            ans += P
        elif T[i] == "s":
            ans += R
        else:
            ans += S
    else:
        if T[i] == T[i-K]:
            if chk_list[i-K] == 0:
                chk_list[i] =1
                continue
        if T[i] == "r":
            ans += P
        elif T[i] == "s":
            ans += R
        elif T[i] == "p":
            ans += S
print(ans)
### BUGGY CODE ###

N, C = map(int, input().split())
xs = []
vs = []
for i in range(N):
    x, v = map(int, input().split())
    xs += [x]
    vs += [v]

# 初手：時計回り
ans = 0
for i in range(N):
    ans1 = sum(vs[:i + 1]) - xs[i]

    # 2手目：反時計回り
    ans2 = 0
    for j in range(i + 1, N):
        ans2 = max(ans2, sum(vs[j:]) - (xs[i] + C - xs[j]))

    ans = max(ans, ans1 + ans2)

# 初手：反時計回り
for i in range(N):
    ans1 = sum(vs[i:]) - (C - xs[i])

    # 2手目：時計回り
    ans2 = 0
    for j in range(i):
        ans2 = max(ans2, sum(vs[:j + 1]) - (C - xs[i] + xs[j]))

    ans = max(ans, ans1 + ans2)

print(ans)


### FIXED CODE ###

N, C = map(int, input().split())
xs = []
vs = []
for i in range(N):
    x, v = map(int, input().split())
    xs += [x]
    vs += [v]


fAs = [0] * N
fAs[0] = vs[0]
for A in range(1, N):
    fAs[A] = fAs[A - 1] + vs[A]
for A in range(N):
    fAs[A] -= xs[A]

gAs = [0] * N
gAs[0] = 0
for A in range(1, N):
    gAs[A] = max(gAs[A - 1], fAs[A - 1])


fBs = [0] * N
fBs[N - 1] = vs[N - 1]
for B in range(0, N - 1)[::-1]:
    fBs[B] = fBs[B + 1] + vs[B]

for B in range(N):
    fBs[B] -= C - xs[B]

gBs = [0] * N
gBs[N - 1] = 0
for B in range(0, N - 1)[::-1]:
    gBs[B] = max(gBs[B + 1], fBs[B + 1])


ans = 0

# 初手：時計回り
for A in range(N):
    ans1 = fAs[A]

    # 2手目：反時計回り
    ans2 = max(0, gBs[A] - xs[A])

    ans = max(ans, ans1 + ans2)


# 初手：反時計回り
for B in range(N):
    ans1 = fBs[B]

    # 2手目：時計回り
    ans2 = max(0, gAs[B] - (C - xs[B]))

    ans = max(ans, ans1 + ans2)

print(ans)