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

k = int(input())
s = input()

# nCr(n, r, m)
mod = 1000000007
n = len(s) + k

fac = [1,1] # 階乗 n!
inv = [0,1] # 逆元 1/n
finv = [1,1] # 逆元の階乗 (n^-1)! = (1/n)!

for i in range(2, n+1):
    fac.append( (fac[-1] * i ) % mod )
    inv.append( (-inv[mod%i] * (mod//i)) % mod )
    finv.append( (finv[-1] * inv[-1]) % mod )

def nCr(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m

i25, i26 = [1], [1]
for _ in range(k+1):
    i25.append(i25[-1] * 25 % mod)
    i26.append(i26[-1] * 26 % mod)

n = len(s)
ans = 0
for i in range(k+1):
    ans += i25[i] * i26[k-i] * nCr(i+n-1, n-1, mod)
    ans %= mod
print(ans)


### FIXED CODE ###

k = int(input())
s = input()

# nCr(n, r, m)
mod = 1000000007
n = len(s) + k

fac = [1,1] # 階乗 n!
inv = [0,1] # 逆元 1/n
finv = [1,1] # 逆元の階乗 (n^-1)! = (1/n)!

for i in range(2, n+1):
    fac.append( (fac[-1] * i ) % mod )
    inv.append( (-inv[mod%i] * (mod//i)) % mod )
    finv.append( (finv[-1] * inv[-1]) % mod )

def nCr(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m

# a^n mod m
def modpow(a, n, m):
    x = 1
    while n > 0:
        if n & 1: x *= a
        a *= a; a %= m
        n >>= 1
    return x

n = len(s)
ans = 0
for i in range(k+1):
    a = modpow(25, i, mod)
    b = modpow(26, k-i, mod)
    c = nCr(n-1+i, n-1, mod)
    ans += a * b * c
    ans %= mod
print(ans)
### BUGGY CODE ###

N = int(input())
L = [int(_) for _ in input().split()]

memo = [[0] * (N+1) for _ in range(N+1)]
for i in range(N - 1):
    for j in range(i + 1, N):
        memo[i][j] = (abs(L[i] - L[j]), L[i] + L[j])

ans = set()
for i in range(N - 2):
    l1 = L[i]
    for j in range(i + 1, N - 1):
        l2 = L[j]
        for k in range(j + 1, N):
            l3 = L[k]
            if memo[j][k][0] < l1 < memo[j][k][1]:
                ans.add(tuple(sorted([l1, l2, l3])))

print(len(ans))

### FIXED CODE ###

import bisect

N = int(input())
L = [int(_) for _ in input().split()]
L.sort()

ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        r = L[i] + L[j]
        # 同じ長さでも違う棒はOK
        ri = bisect.bisect_left(L, r, lo=j)
        ans += ri - j - 1

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

s = input()
old_count = 1
s = list(s)
new_count = 0
while old_count != new_count:
    old_count = new_count
    for i in range(len(s)-1, 0, -1):
        if s[i] == 'W' and s[i-1] == 'B':
            s[i-1] = 'W'
            s[i] = 'B'
            new_count += 1
print(new_count)


### FIXED CODE ###

s = input()
s = list(s)
count_b = [0] * len(s)
for i in range(len(s)):
    if s[i] == 'B':
        if i == 0:
            count_b[i] = 1
        else:
            count_b[i] = count_b[i-1] + 1
    else:
        if i > 0:
            count_b[i] = count_b[i-1]
count = 0
for i in range(len(s)):
    if s[i] == 'W':
        count += count_b[i]
print(count)
### BUGGY CODE ###

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

dp=[0 for i in range(N)]
dp[1]=abs(H[1]-H[0])

for i in range(1,N):
    dp[i]=min(dp[i-j]+abs(H[i-j]-H[i]) for j in range(1,min(K+1,i+1)))
        
print(dp[N-1])

### FIXED CODE ###

def main():
    N,K=map(int,input().split())
    h=list(map(int,input().split()))

    ans=[0]*N
    ans[1]=abs(h[1]-h[0])


    for i in range(2,N):
        ans[i] = min(abs(h[i] - h[j]) + ans[j] for j in range(max(0,i-K),i))
    print(ans[N-1])
    
main()
### BUGGY CODE ###

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

min_ans = pow(10,15)
for b in reversed(range(-max(A), 0)):
    ans = 0
    for i in range(len(A)):
        #print(A[i], b, i, abs(A[i] - (b + i + 1)))
        ans += abs(A[i] - (b + i + 1))
    #print("ans", b, ans)
    if min_ans >= ans: min_ans = ans
    else: break


min_ans_b = pow(10,15)
for b in range(0, max(A)):
    ans = 0
    for i in range(len(A)):
        ans += abs(A[i] - (b + i + 1))
    #print("ans", b, ans)
    if min_ans_b >= ans: min_ans_b = ans
    else: break


if min_ans_b < min_ans:
    min_ans = min_ans_b

print(min_ans)

### FIXED CODE ###

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

for i in range(N):
    A[i] -= i + 1

A = sorted(A)
b = A[N//2]
sad = 0
for i in A:
    sad += abs(i - b)

print(sad)
### BUGGY CODE ###

from itertools import combinations

n = int(input())
S = [int(input()) for _ in range(n)]

ans = 0
for i in range(1, n + 1):
    for tpl in combinations(S, i):
        s = sum(tpl)
        if s % 10 != 0:
            ans = max(ans, s)
print(ans)

### FIXED CODE ###

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

ans = sum(s)
if ans % 10 != 0:
    print(ans)
else:
    if all([i % 10 == 0 for i in s]):
        print(0)
    else:
        print(ans - min([i for i in s if i % 10 != 0]))
### BUGGY CODE ###

n,q=map(int, input().split())
s=input()
t=s.replace("AC","11")
u=[0 if i!="1" else 1 for i in t]
for i in range(q):
    l,r=map(int, input().split())
    ans=sum(u[l-1:r])
    if s[l-1]=="C" and s[r-1]=="A":
        print(ans//2-1)
    else:
        print(ans//2)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
t=[0]*len(s)
for i in range(len(s)-1):
    if s[i]=="A" and s[i+1]=="C":
        t[i+1]=t[i]+1
    else:
        t[i+1]=t[i]+0
for i in range(q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

import heapq
import copy
N = int(input())
A = []
for _ in range(N):
    A.append((-1) * int(input()))

for i in range(N):
    list = copy.deepcopy(A)
    del list[i]
    heapq.heapify(list)
    print((-1) * heapq.heappop(list))

### FIXED CODE ###

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))
list = A
list = sorted(list)
max = list[-1]
second_max = list[-2]
cnt = A.count(max)
for i in range(N):
    if A[i] == max and  cnt == 1:
        print(second_max)
    else:
        print(max)
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
import sys
import bisect
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7

ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def keta(n):
    if n < 10:
        return 1
    return math.floor(math.log10(n - 1)) + 1


def check(A, B, X, n):
    return A * n + B * keta(n) <= X


def p(tt, parent):
    children = tt[parent]
    for i in range(len(children)):
        if children[i][0] == parent:
            children.remove(children[i])
            break

    res = {parent: children}
    for c, ii in children:
        tt[c].remove((parent, ii))
        res.update(p(tt, c))
    return res


def main():
    N = int(input())
    ab = [[int(a) - 1 for a in input().split()] for _ in range(N - 1)]

    tt = defaultdict(list)

    for i, (a, b) in enumerate(ab):
        aa = tt[a]
        aa.append((b, i))
        tt[a] = aa
        a, b = b, a
        aa = tt[a]
        aa.append((b, i))
        tt[a] = aa

    tree = p(tt, 0)
    # print(tree)

    colors = len(tree[0])
    for k, v in tree.items():
        if k == 0:
            continue
        colors = max(colors, len(v) + 1)

    print(colors)

    res = [None] * (N - 1)

    def solve(pos, parentcol):
        children = tt[pos]
        for iii, (c, i) in enumerate(children):
            res[i] = (parentcol + 1 + iii) % colors
            solve(c, res[i])

    solve(0, -1)

    for i in range(N - 1):
        print(res[i] + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, deque, Counter
import sys
import bisect
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7

ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def keta(n):
    if n < 10:
        return 1
    return math.floor(math.log10(n - 1)) + 1


def check(A, B, X, n):
    return A * n + B * keta(n) <= X


def main():
    N = int(input())
    ab = [[int(a) - 1 for a in input().split()] for _ in range(N - 1)]

    tree = defaultdict(list)
    # res = {}

    for i, (a, b) in enumerate(ab):
        # aa = tt[a]
        # aa.append((b, i))
        # tt[a] = aa
        if a not in tree:
            tree[a] = []
        tree[a].append((b, i))

    # def p(tt, parent):
    #     children = tt[parent]
    #     res[parent]=children
    #     # res = {parent: children}
    #     for c, ii in children:
    #         p(tt, c)
    #     return res
    #
    #
    # tree = p(tt, 0)

    colors = len(tree[0])
    for k, v in tree.items():
        if k == 0:
            continue
        colors = max(colors, len(v) + 1)

    print(colors)

    res = [None] * (N - 1)

    def solve(pos, parentcol):
        children = tree[pos]
        for iii, (c, i) in enumerate(children):
            res[i] = (parentcol + 1 + iii) % colors
            solve(c, res[i])

    solve(0, -1)

    for i in range(N - 1):
        print(res[i] + 1)


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

n = int(input())
list = []
ans = 0
for x in range(n):
  list.append(sorted(input()))
for i in range(len(list)-1):
  for j in range(i+1, n):
    if list[i] == list[j]:
      ans +=1
print(ans)

### FIXED CODE ###

import sys
n = int(sys.stdin.readline().strip())
list = [''.join(sorted(sys.stdin.readline().strip())) for i in range(n)]
d = {}
ans = 0
for x in list:
  if x in d:
    ans += d[x]
    d[x] += 1
  else:
    d[x] = 1
print(ans)
### BUGGY CODE ###

a,b=map(int,input().split())
ans=a
for i in range(1,b-a+1):
  ans^=(a+i)
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
a-=1

def allx(n):
    ans=0
    for i in range(40):
        if i==0:
            if n%4==2 or n%4==1:
                ans+=1
                continue
        c= pow(2,i+1)
        k=n% c
        
        if k>=c//2 and k%2==0:
          ans+=pow(2,i)
    return ans

print(allx(b)^allx(a))
### BUGGY CODE ###

from sys import stdin
def input():
    return stdin.readline().strip()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
ch += 1
cw += 1
dh, dw = map(int, input().split())
dh += 1
dw += 1
g = ['#' * (w + 4)] * 2 
for _ in range(h):
    g.append('##' + input() + '##')
g.append('#' * (w + 4))
g.append('#' * (w + 4))

d1 = [(-1, 0), (0, -1), (0, 1), (1, 0)]
d2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1),
(-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2),
(2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

import heapq
# Dijkstra
d = [-2, -1, 0, 1, 2]
seen = [[-1] * (w+2) for _ in range(h+2)]
todo = [(0, ch, cw)]
heapq.heapify(todo)
while len(todo) > 0:
    cost, x, y = heapq.heappop(todo)
    if seen[x][y] == -1:
        if x == dh and y == dw:
            print(cost)
            exit()
        seen[x][y] = cost

    for i in range(4):
        dx, dy = d1[i]
        if g[x+dx][y+dy] == '.' and seen[x+dx][y+dy] == -1:
            heapq.heappush(todo, (cost, x+dx, y+dy))
    for i in range(20):
        dx, dy = d2[i]
        if g[x+dx][y+dy] == '.' and seen[x+dx][y+dy] == -1:
            heapq.heappush(todo, (cost+1, x+dx, y+dy))

print(-1)

### FIXED CODE ###

from sys import stdin
def input():
    return stdin.readline().strip()

h, w = map(int, input().split())
ch, cw = map(int, input().split())
ch += 1
cw += 1
dh, dw = map(int, input().split())
dh += 1
dw += 1
g = ['#' * (w + 4)] * 2 
for _ in range(h):
    g.append('##' + input() + '##')
g.append('#' * (w + 4))
g.append('#' * (w + 4))

d1 = [(-1, 0), (0, -1), (0, 1), (1, 0)]
d2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1),
(-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2),
(2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

from collections import deque
# BFS BFS
seen = [[-1] * (w+2) for _ in range(h+2)]
todo = deque([(0, ch, cw)])
while len(todo) > 0:
    history = []
    while len(todo) > 0:
        cost, x, y = todo.popleft()
        if seen[x][y] == -1:
            if x == dh and y == dw:
                print(cost)
                exit()
            seen[x][y] = cost
            history.append((cost, x, y))
        else:
            continue

        for i in range(4):
            dx, dy = d1[i]
            if g[x+dx][y+dy] == '.' and seen[x+dx][y+dy] == -1:
                todo.append((cost, x+dx, y+dy))

    for j in history:
        cost, x, y = j
        for i in range(20):
            dx, dy = d2[i]
            if g[x+dx][y+dy] == '.' and seen[x+dx][y+dy] == -1:
                todo.append((cost+1, x+dx, y+dy))

print(-1)
### BUGGY CODE ###

# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(tuple(map(int, args[1].split())), int)

    cur = A
    for _ in range(k):
        prev = cur
        cur = np.zeros(n, int)
        for x, p in enumerate(prev):
            cur[max(0, x-p)] += 1
            if x+p+1 < n:
                cur[x+p+1] -= 1
        cur = cur.cumsum()
        if all(cur == n):
            break
    return ' '.join(map(str, cur))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = list(map(int, args[1].split()))

    cur = A
    for _ in range(k):
        prev = cur.copy()
        cur = [0]*n
        for x, p in enumerate(prev):
            cur[max(0, x-p)] += 1
            if x+p+1 < n:
                cur[x+p+1] -= 1

        satulated = True
        for i in range(1, n):
            cur[i] += cur[i-1]
            satulated &= cur[i] == n
        if satulated:
            break

    return ' '.join(map(str, cur))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###


from collections import deque


def resolve():
    drc4 = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    H, W = map(int, input().split())
    sy, sx = map(lambda x: int(x) - 1, input().split())
    gy, gx = map(lambda x: int(x) - 1, input().split())
    G = [input() for _ in range(H)]

    INF = 10 ** 12
    ans = [[INF] * W for _ in range(H)]

    q = deque()
    q.append((sy, sx, 0))
    ans[sy][sx] = 0

    while q:
        sy, sx, cost = q.popleft()
        for dy, dx in drc4:
            ny = dy + sy
            nx = dx + sx
            if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                ans[ny][nx] = cost
                q.append((ny, nx, cost))

        for dy8, dx8 in warp:
            ny8 = dy8 + sy
            nx8 = dx8 + sx
            if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                ans[ny8][nx8] = cost + 1
                q.append((ny8, nx8, cost + 1))

    res = ans[gy][gx] if ans[gy][gx] < INF else -1
    print(res)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###


from collections import deque
def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

    ans = path[Dh][Dw] if path[Dh][Dw] < INF else -1
    print(ans)


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

a, b, x = map(int, input().split())
ans = 0
for i in range(a, b + 1):
    if i % x == 0:
        ans += 1
print(ans)

### FIXED CODE ###

a, b, x = map(int, input().split())
print((b // x) - (a - 1) // x)
### BUGGY CODE ###

import math
n = int(input())
ans = 0
for i in range(1, int(math.sqrt(n))+1):
    if n % i == 0:
        j = 1
        while True:
            m = (n//i)/(10**j)
            if m>=1 and m<10:
                ans = j+1
                break
            j+=1
print(ans)

### FIXED CODE ###

import math
n = int(input())
if n < 10:
    print(1)
else:
    a = 0
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            a = i
    b = n//a
    j = 1
    while True:
        m = b / (10**j)
        if m>=1 and m<10:
            ans = j+1
            break
        j+=1

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

def InsertionSort(A, N, g):
    global cnt
    for i in range(g, N):
        key = A[i]
        j = i-g
        while j >= 0 and A[j] > key:
            A[j+g] = A[j]
            j = j-g
            cnt += 1    
        A[j+g] = key
    return A

def ShellSort(A, N):
    G = [len(A)]
    i = 0
    while True:
        if G[i]//4 == 0:
            break
        G.append(G[i]//4)
        i += 1

    
    if 1 not in G:
        G.append(1)
    for i in range(len(G)):
        InsertionSort(A, N, G[i])
    return G

N = int(input())
A = []
cnt = 0
for i in range(N):
    A.append(int(input()))
ShellSort(A,N)
print(len(ShellSort(A,N)))
print(*ShellSort(A,N))
print(cnt)
print(*A, sep='\n')

### FIXED CODE ###

import math
def InsertionSort(A, N, g):
    global cnt
    for i in range(g, N):
        key = A[i]
        j = i-g
        while j >= 0 and A[j] > key:
            A[j+g] = A[j]
            j = j-g
            cnt += 1    
        A[j+g] = key
    return A

def ShellSort(A, N):
    G = []
    i = 1
    while True:
        if  3**i -1 > N*2:
            break
        G.insert(0, int((3**i-1)/2))
        i += 1


    for i in range(len(G)):
        InsertionSort(A, N, G[i])
    return G

N = int(input())
A = []
cnt = 0
for i in range(N):
    A.append(int(input()))
ShellSort(A,N)
print(len(ShellSort(A,N)))
print(*ShellSort(A,N))
print(cnt)
print(*A, sep='\n')
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
hi = -1
lo = n
while lo-hi>1:
  mid = (lo+hi)//2
  if a[mid] >= k:
    hi = mid
  else:
    lo = mid
ng = hi
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  dp = [False]*(k+1)
  dp[0] = True
  for j in range(n):
    if j == mid:
      continue
    w = a[j]
    for i in range(k,w-1,-1):
      dp[i] |= dp[i-w]
  if any(dp[k-a[mid]:k]):
    ng = mid
  else:
    ok = mid
print(n-ok)

### FIXED CODE ###

n, k = map(int,input().split())
a = [k+1 if x > k else x for x in map(int,input().split())]
a.sort()
lef = [1]*n
rig = [1]*n
mask = (1 << (k+1)) - 1
for i in range(n-1):
  lef[i+1] = lef[i] | (lef[i] << a[i]) & mask
  rig[-i-2] = rig[-i-1] | (rig[-i-1] << a[-i-1]) & mask
ok = -1
ng = n
while ng - ok > 1:
  mid = (ng + ok) // 2
  if a[mid] >= k:
      ng = mid
      continue
  lc = lef[mid]
  rc = rig[mid]
  cov = ((1 << k) - 1) ^ ((1 << (k - a[mid])) - 1)
  for i in range(k):
    if lc & 1 and rc & cov:
      ng = mid
      break
    lc >>= 1
    cov >>= 1
  else:
    ok = mid
print(ok + 1)
### BUGGY CODE ###

N = int(input())

num = []
for i in range(N):
  num.append(int(input()))
  
num = sorted(num)
ans = [num[0]]
num.pop(0)

for i in range(len(num)-1):
  if i % 4 == 0:
    ans.append(num[-1])
    num.pop(-1)
  elif i % 4 == 1:
    ans = [num[-1]] + ans
    num.pop(-1)
  elif i % 4 == 2:
    ans.append(num[0])
    num.pop(0)
  else:
    ans = [num[0]] + ans
    num.pop(0)

answer = max(abs(num[0]-ans[0]), abs(num[0]-ans[-1]))
for i in range(len(ans)-1):
  answer += abs(ans[i] - ans[i+1])
  
print(answer)

### FIXED CODE ###

from collections import deque
N = int(input())
 
num = []
for i in range(N):
  num.append(int(input()))
  
num = deque(sorted(num))
ans = deque([num.popleft()])
 
for i in range(N-2):
  if i % 4 == 0:
    ans.append(num.pop())
  elif i % 4 == 1:
    ans.appendleft(num.pop())
  elif i % 4 == 2:
    ans.append(num.popleft())
  else:
    ans.appendleft(num.popleft())

answer = max(abs(num[0]-ans[0]), abs(num[0]-ans[-1]))
for i in range(len(ans)-1):
  answer += abs(ans[i] - ans[i+1])
  
print(answer)
### BUGGY CODE ###

import random


def slv(N, C, X, V):
    # cal_l = 0
    # move = 0
    # for x, v in zip(X, V):
    #     if x-move > v:
    #         break
    #     cal_l += v
    #     move = x
    # cal_l -= move

    # cal_r = 0
    # move = 0
    # tmp =list(zip(X, V))
    # for x, v in tmp[::-1]:
    #     if (C-x)-move > v:
    #         break
    #     cal_r += v
    #     move = C - x
    # cal_r -= move

    # print(cal_l, cal_r)

    ans_l = [(0, 0)]
    for x, v in zip(X, V):
        ans_l.append((x, ans_l[-1][1] + v))

    ans_r = [(0, 0)]
    for x, v in list(zip(X, V))[::-1]:
        ans_r.append((C-x, ans_r[-1][1] + v))


    ans_l_r = []
    for i, a in enumerate(ans_l):
        tmp = 0
        for b in ans_r[:-i]:
            c = a[1] + b[1] - 2*a[0] - b[0]
            tmp = max(tmp, c)
        ans_l_r.append( tmp)
    ans_r_l = []
    for i, a in enumerate(ans_r):
        tmp = 0
        for b in ans_l[:-i]:
            c = a[1] + b[1] - 2*a[0] - b[0]
            tmp = max(tmp, c)
        ans_r_l.append( tmp)

    
    # print(ans_l)
    # print(ans_r)
    l = max([x[1]-x[0] for x in ans_l])
    r = max([x[1]-x[0] for x in ans_r])
    lr = max(ans_l_r)
    rl = max(ans_r_l)


    return max(l, r, lr, rl)



def main():
    N, C = list(map(int, input().split()))
    X = []
    V = []
    for _ in range(N):
        x, v = list(map(int, input().split()))
        X.append(x)
        V.append(v)
    print(slv(N, C, X, V))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import random


def slv(N, C, X, V):
    ans_l = [(0, 0)]
    ans_l_ = [0]
    for x, v in zip(X, V):
        ans_l_.append(max(ans_l_[-1], ans_l[-1][1] + v - x))
        ans_l.append((x, ans_l[-1][1] + v))
    ans_l_.pop(0)
    ans_l.pop(0)

    ans_r = [(0, 0)]
    ans_r_ = [0]
    for x, v in list(zip(X, V))[::-1]:
        ans_r_.append(max(ans_r_[-1], ans_r[-1][1] + v - (C-x)))
        ans_r.append((C-x, ans_r[-1][1] + v))
    ans_r_.pop(0)
    ans_r.pop(0)
        

    # print('p1')

    ans_l_r = []
    for i, a in enumerate(ans_l[:-1], 1):
        # print(ans_r_[N-i-1],  a[1]-2*a[0])
        ans_l_r.append(ans_r_[N-i-1] + a[1]-2*a[0])

    # print('p2')
    ans_r_l = []
    for i, a in enumerate(ans_r[:-1], 1):
        # print(ans_l_[N-i-1],  a[1]-2*a[0])
        ans_r_l.append(ans_l_[N-i-1] + a[1]-2*a[0])

    l = max([x[1]-x[0] for x in ans_l])
    r = max([x[1]-x[0] for x in ans_r])
    lr = 0 if not ans_l_r else max(ans_l_r)
    rl = 0 if not ans_r_l else max(ans_r_l)

    # print(ans_l)
    # print(ans_l_)
    # print(ans_r)
    # print(ans_r_)

    # print(l, r, lr, rl)
    return max(l, r, lr, rl)



def main():
    N, C = list(map(int, input().split()))
    X = []
    V = []
    for _ in range(N):
        x, v = list(map(int, input().split()))
        X.append(x)
        V.append(v)

    # N = 100000
    # C = 1000000000000
    # X = [1]
    # V = [100]
    # for _ in range(N):
    #     X.append(X[-1]+random.randint(1, 10000))
    #     V.append(random.randint(1, 10000))

    print(slv(N, C, X, V))


if __name__ == '__main__':
    main()