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

import bisect
import math
N = int(input())
A = list(map(int, input().split()))
T = [2 ** i for i in range(int(math.log2(max(A))) + 1, -1, -1)]

A.sort()
already = set()

def is_in(t, n):
    i = bisect.bisect_left(A, t)
    while i < n and t == A[i]:
        if i not in already:
            already.add(i)
            return i
        i += 1

    return -1

res = 0
for n in range(len(A) - 1, -1, -1):
    if n in already:
        continue

    already.add(n)
    a = A[n]
    for t in [t - a for t in T if a < t <= 2 * a]:
        i = is_in(t, n)
        if i != -1:
            res += 1
            break

print(res)



### FIXED CODE ###

import bisect
import math
N = int(input())
A = list(map(int, input().split()))
T = [2 ** i for i in range(31)]
A.sort()
already = set()


def to_dic(A):
    d = {}
    for a in A:
        d[a] = d.setdefault(a, 0) + 1

    return d

def is_in(t, num):
    i = D.setdefault(t, 0)
    if i == 0:
        return 0
    s = min(i, num)
    D[t] -= s
    return s


res = 0
D = to_dic(A)
A2 = list(D.keys())
A2.sort()

for n in range(len(A2) - 1, -1, -1):
    a = A2[n]

    if a in T:
        res += D[a] // 2
        D[a] = 0

        if D[a] % 2 == 0:
            continue

    num = D[a]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        s = is_in(t - a, num)
        res += s
        num -= s
        if num == 0:
            break

        t >>= 1

print(res)
### BUGGY CODE ###

from operator import itemgetter

N, Q = map(int, input().split())

events = []

for _ in range(N):
    s, t, x = map(int, input().split())
    add_event = (s - x, 1, x)
    remove_event = (t - x, -1, x)
    events.append(add_event)
    events.append(remove_event)

events.sort(key=itemgetter(0))  # イベント処理時刻昇順ソート

under_construction = set()

cur = 0
for _ in range(Q):
    d = int(input())
    # print('d', d)
    while cur < N * 2 and events[cur][0] <= d:
        exec_time, event_type, under_construction_x = events[cur]
        # print(cur, exec_time, event_type, under_construction_x)
        if event_type == 1:
            # add_event
            under_construction.add(under_construction_x)
        else:
            # remove_event
            under_construction.discard(under_construction_x)
        cur += 1
    # print('cur', cur, 'events', events)
    # print('uc', under_construction)
    print(min(under_construction) if under_construction else -1)

    # print()


### FIXED CODE ###

# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')
### BUGGY CODE ###

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

Lists=[]
for i in range(n):
    Lists.append(a.count(i+1))
#print(a)
#print(Lists)
moto=0
for j in range(n):
    if ((Lists[j]>1)):
        moto+=Lists[j]*(Lists[j]-1)//2

#print(moto)
#print(Lists)
for i in range(n):
    if (Lists[a[i]-1]>1):
        ans=moto+1-Lists[a[i]-1]
    else:
        ans=moto
    print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
List={}
x=0
for i in range(n):
    if not a[i] in List:
        List[a[i]] = 1
    else:
        List[a[i]]+=1
    
sigma=0

for key,item in List.items():
    sigma += item*(item-1)//2
for i in range(n):
    print(sigma-List[a[i]]+1)
### BUGGY CODE ###

n,m = map(int,input().split())
lis = [[] for i in range(n)]

query = []

for _ in range(m):
  tp = tuple(map(int,input().split()))
  query.append(tp)
  lis[tp[0]-1].append(tp[1])
  
for i in range(n):
  lis[i].sort()

for item in query:
  print("{:06}{:06}".format(item[0],lis[item[0]-1].index(item[1])+1))

### FIXED CODE ###

n,m = map(int,input().split())
lis = [[] for i in range(n)]
query = []

for num in range(m):
  tp = tuple(map(int,input().split()))
  query.append(tp)
  lis[tp[0]-1].append((tp[1],num))  

ans = [[0,0] for i in range(m)]

for num_p , pref in enumerate(lis):
  pref.sort(key = lambda tp:tp[0])
  for i,tp_city in enumerate(pref):
    ans[tp_city[1]][0] = num_p
    ans[tp_city[1]][1] = i+1

for item in ans:
  print("{:06}{:06}".format(item[0]+1,item[1]))
### BUGGY CODE ###

from numpy import cumsum
N,K=map(int,input().split())
A=list(map(int,input().split()))
imos=[0 for i in range(N+1)]
ANS=[str(N)]*N
if K>=40:
  ans=" ".join(ANS)
  print(ans)
else:
  for t in range(K):
    for i in range(N):
      l=max(0,i-A[i])
      r=min(N,i+A[i]+1)
      imos[l]+=1
      imos[r]-=1
    imos=cumsum(imos)
    for i in range(0,N):
      A[i]=imos[i]
    imos=[0 for i in range(N+1)]
  for i in range(N):
    A[i]=str(A[i])
  ans=" ".join(A)
  print(ans)  

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
imos=[0 for i in range(N+1)]
ANS=[str(N)]*N
if K>=50:
  ans=" ".join(ANS)
  print(ans)
else:
  for t in range(K):
    for i in range(N):
      l=max(0,i-A[i])
      r=min(N,i+A[i]+1)
      imos[l]+=1
      imos[r]-=1
    for i in range(0,N):
      imos[i+1]+=imos[i]
      A[i]=imos[i]
    imos=[0 for i in range(N+1)]
  for i in range(N):
    A[i]=str(A[i])
  ans=" ".join(A)
  print(ans)
### BUGGY CODE ###

def resolve():
    X = int(input())
    ans = X
    while True:
        count = 0
        if X != 2 and X != 3 and X != 4 and X != 5 and X != 6:
            for i in range(7, X):
                if X%i == 0:
                    count += 1
            if count == 0:
                print(ans)
                exit()
            else:
                ans += 1
        elif X != 2:
            print("2")
        elif X != 3:
            print("3")
        elif X != 4 and X != 5:
            print("5")
        else:
            print("7")
resolve()

### FIXED CODE ###

def resolve():
    import math
    X = int(input())
    while True:
        count = 0
        for i in range(2, int(math.sqrt(X))):
            if X%i == 0:
                count += 1
                break
        if count == 0:
            print(X)
            exit()
        else:
            X += 1
resolve()
### BUGGY CODE ###

n = int(input())
attends = [int(x) for x in input().split()]
arr = []
for x in range(1, n + 1):
    arr.append(attends.index(x) + 1)
print(*arr)


### FIXED CODE ###

n = int(input())
attends = dict(enumerate(list(map(int, input().split())), start=1))
attends_sorted = sorted(attends.items(), key=lambda x: x[1])
arr = [x[0] for x in attends_sorted]
print(*arr)
### BUGGY CODE ###

r,g,b,n= map(int, input().split())
ans=0
for i in range(n//r+1):
    for j in range(n//g+1):
        if (n-i*r-j*g)%b==0 and n-i*r-j*g>=0:
            ans+=1
print(ans)

### FIXED CODE ###

r,g,b,n= map(int, input().split())
ans=0
for i in range(n//r+1):
    for j in range(n//g+1):
        if (n-i*r-j*g)%b==0 and n-i*r-j*g>=0:
            ans+=1
print(ans)
### BUGGY CODE ###

import numpy as np
INF=10**20
N,M,S,T=[int(a) for a in input().split(" ")]
UVAB=[[int(a) for a in input().split(" ")] for i in range(M)]

def dijkstra(S, N, paths):
    from heapq import heappush,heappop
    q=[(0,S)]
    check=[False]*N
    shortest=[INF]*N
    shortest[S]=0
    while len(q)>0:
        d0, src=heappop(q)
        if d0>shortest[src]:
            continue
        check[src]=True
        for dst, d1 in paths[src]:
            if check[dst] is False and d0+d1<shortest[dst]:
                shortest[dst]=d0+d1
                heappush(q, (d0+d1, dst))
        if all(check):
            break
    return np.array(shortest)

paths_yn=[[] for _ in range(N)]
paths_sn=[[] for _ in range(N)]
for u,v,a,b in UVAB:
    paths_yn[u-1].append((v-1,a))
    paths_yn[v-1].append((u-1,a))
    paths_sn[u-1].append((v-1,b))
    paths_sn[v-1].append((u-1,b))
shortest_yn = dijkstra(S-1, N, paths_yn)
shortest_sn = dijkstra(T-1, N, paths_sn)

totals = 10**15-(shortest_yn+shortest_sn)
for a in np.maximum.accumulate(totals[::-1])[::-1]:
    print(int(a))

### FIXED CODE ###

import numpy as np
INF=10**20
N,M,S,T=[int(a) for a in input().split(" ")]
UVAB=[[int(a) for a in input().split(" ")] for i in range(M)]

def dijkstra(S, N, paths):
    from heapq import heappush,heappop
    q=[(0,S)]
    shortest=[INF]*N
    shortest[S]=0
    while len(q)>0:
        d0, src=heappop(q)
        if d0>shortest[src]:
            continue
        for dst, d1 in paths[src]:
            if d0+d1<shortest[dst]:
                shortest[dst]=d0+d1
                heappush(q, (d0+d1, dst))
    return np.array(shortest)

paths_yn=[[] for _ in range(N)]
paths_sn=[[] for _ in range(N)]
for u,v,a,b in UVAB:
    paths_yn[u-1].append((v-1,a))
    paths_yn[v-1].append((u-1,a))
    paths_sn[u-1].append((v-1,b))
    paths_sn[v-1].append((u-1,b))
shortest_yn = dijkstra(S-1, N, paths_yn)
shortest_sn = dijkstra(T-1, N, paths_sn)

totals = 10**15-(shortest_yn+shortest_sn)
for a in np.maximum.accumulate(totals[::-1])[::-1]:
    print(int(a))
### BUGGY CODE ###

def main():
    from itertools import accumulate

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

    R, G, B = [0], [0], [0]
    for s in S:
        if s == 'R':
            R.append(1)
            G.append(0)
            B.append(0)

        elif s == 'G':
            R.append(0)
            G.append(1)
            B.append(0)

        elif s == 'B':
            R.append(0)
            G.append(0)
            B.append(1)

    R = list(accumulate(R))
    G = list(accumulate(G))
    B = list(accumulate(B))

    # print(R)
    # print(G)
    # print(B)
    ans = 0
    for j in range(1, N - 1):
        sj = S[j]
        for i in range(j):
            si = S[i]
            if si == sj:
                continue
            # print(sj, j, i)
            if set(['R', 'G', 'B']) - {sj} - {si} == {'R'}:
                ans += R[-1] - R[j + 1]
                if (j + j - i < N) and si != S[j + j - i] and sj != S[j + j - i]:
                    ans -= 1
                # print('Rx', ans)

            if set(['R', 'G', 'B']) - {sj} - {si} == {'G'}:
                ans += G[-1] - G[j + 1]

                if (j + j - i < N) and si != S[j + j - i] and sj != S[j + j - i]:
                    ans -= 1
                # print('Gx', ans)

            if set(['R', 'G', 'B']) - {sj} - {si} == {'B'}:
                ans += B[-1] - B[j + 1]
                if (j + j - i < N) and si != S[j + j - i] and sj != S[j + j - i]:
                    ans -= 1
                # print('Bx', ans)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from itertools import accumulate

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

    R, G, B = [0], [0], [0]
    for s in S:
        if s == 'R':
            R.append(1)
            G.append(0)
            B.append(0)

        elif s == 'G':
            R.append(0)
            G.append(1)
            B.append(0)

        elif s == 'B':
            R.append(0)
            G.append(0)
            B.append(1)

    R = list(accumulate(R))
    G = list(accumulate(G))
    B = list(accumulate(B))

    # print(R)
    # print(G)
    # print(B)
    ans = 0
    for j in range(1, N - 1):
        sj = S[j]
        for i in range(j):
            si = S[i]
            sk = ''
            if j + j - i < N:
                sk = S[j + j - i]

            if si == sj:
                continue

            # if sj == sk:
            #     continue

            # print(sj, j, i)
            if (si == 'G' and sj == 'B') or (si == 'B' and sj == 'G'):
                ans += R[-1] - R[j + 1]
                if sk and si != sk and sj != sk:
                    ans -= 1
                # print('Rx', ans)

            if (si == 'R' and sj == 'B') or (si == 'B' and sj == 'R'):
                ans += G[-1] - G[j + 1]

                if sk and si != sk and sj != sk:
                    ans -= 1
                # print('Gx', ans)

            if (si == 'R' and sj == 'G') or (si == 'G' and sj == 'R'):
                ans += B[-1] - B[j + 1]
                if sk and si != sk and sj != sk:
                    ans -= 1
                # print('Bx', ans)

    print(ans)


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

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

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

### FIXED CODE ###

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

b = [0]*n

for i in a:
    b[i-1] += 1

for i in b:
    print(i)
### BUGGY CODE ###

n = int(input())
ans = 0

for i in range(1,n+1):
    if set(str(i)) == {'3','5','7'}:
        ans += 1
print(ans)

### FIXED CODE ###

n = input()
m = len(n)
ans = 0

for k in range(m+1):
    for i in range(3 ** k):
        li = [] 
        for j in range(k):
            li.insert(0,int((i%(3**(j+1)))/(3**j)))                
        for j in range(k):
            if li[j] == 0:
                li[j] = '3'
            if li[j] == 1:
                li[j] = '5'
            if li[j] == 2:
                li[j] = '7'
        if li != []:
            if int(''.join(li)) <= int(n) and len(set(li)) == 3:
                ans += 1
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())

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

ans = []

for i in range(m):
    a, b = map(int, input().split())
    if h[a-1] < h[b-1]:
        if a not in ans:
            ans.append(a)
    elif h[a-1] > h[b-1]:
        if b not in ans:
            ans.append(b)
    elif h[a-1] == h[b-1]:
        if a not in ans:
            ans.append(a)
            if b not in ans:
                ans.append(b)
        elif b not in ans:
            ans.append(b)

print(n-len(ans))


### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
LIST = [ 1 for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    if H[A-1] >= H[B-1]: LIST[B-1] = 0
    if H[A-1] <= H[B-1]: LIST[A-1] = 0
print(sum(LIST))
### BUGGY CODE ###

S = input()
INF = 10 ** 9 + 7
mod = [1,10,9,12,3,4]
dp = [[0 for _ in range(13)] for l in range(len(S))]
S_li = [_ for _ in S]
S_li = S_li[::-1]
if S_li[0] == '?':
    dp[0][0:10] = [1,1,1,1,1,1,1,1,1,1]
else:
    dp[0][int(S_li[0])] = 1
for _ in range(1,len(S)):
    if S_li[_] == '?':
        for x in range(10):
            for y in range(13):
                dp[_][(x * mod[_ % 6] + y) % 13] += dp[_ - 1][y] % INF
    else:
        for y in range(13):
            dp[_][(int(S_li[_]) * mod[_ % 6] + y) % 13] += dp[_ - 1][y] % INF
print(dp[-1][5] % INF)

### FIXED CODE ###

MOD = 1000000007;
 
s = [int(x) if x!="?" else -1 for x in input()]
#print(s)
n=len(s)
 
r=[0]*13
 
c=s[0]
if (c!=-1):
    r[c]=1
else:
    for i in range(10):r[i]=1
for i in range(1,n):
    dp=[0]*26
    for j in range(13):dp[j*10%13]+=(r[j]%MOD)
    dp[13:26]=dp[0:13]
    c=s[i]
    r=[0]*13
    if (c==-1):
        w=sum(dp[4:14])
        for j in range(13):
            r[j]+=w
            w=w+dp[j+1]-dp[4+j]
    else:
        for j in range(13):
            r[j]+=dp[13-c+j]
print (r[5]%MOD)
### BUGGY CODE ###

s = input()
q = int(input())
ans = 0

for i in range(q):
    c = list(map(str, input().split()))
    if c[0] == '1':
        ans +=1
    if c[0] == '2':
        if (int(c[1])+ans%2)%2== 1 :
          s = c[2] + s
        if (int(c[1])+ans%2)%2== 0 :
          s = s + c[2]

if ans%2 == 1:
  s = s[::-1]

print(s)

### FIXED CODE ###

s=input()
q=int(input())
f=""
b=""
r=0
for i in range(q):
  query=input().split()
  if int(query[0])==1:
    r=1-r
  else:
    if (r^(int(query[1])-1))==0:
      f+=query[2]
    else:
      b+=query[2]
ret=f[::-1]+s+b
if r:
  ret=ret[::-1]
print(ret)
### BUGGY CODE ###

n = int(input())
a = [0] + [int(input()) for i in range(n)]
c = a[1]
p = 1
while c > 2:
    c = a[c]
    p += 1

if c == 2:
    print(p)
else:
    print(-1)


### FIXED CODE ###

n = int(input())
a = [0] + [int(input()) for i in range(n)]
c = a[1]
p = 1
while c > 2:
    d = a[c]
    a[c] = 0
    c = d
    p += 1

if c == 2:
    print(p)
else:
    print(-1)
### BUGGY CODE ###

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data
 
p_list = get_sieve_of_eratosthenes(10**3)
 
# def factorization_counta(n):
#     arr = []
#     temp = n
#     for i in p_list:
#         if i * i > n:
#             break
#         elif temp % i == 0:
#             cnt = 0
#             while temp % i == 0:
#                 cnt += 1
#                 temp //= i
#             arr.append(cnt)
            
#     if temp != 1:
#         arr.append(1)
#     if arr == []:
#         arr.append(1)
#     return arr

def prime(m):
    pf = {}
    for i in p_list:
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1
    return pf
 
def main():
    N = int(input())
    ans = 0
    for c in range(1, N):
        p = prime(N - c)
        tmp = 1
        for v in p.values():
            tmp *= (v + 1)
        ans += tmp
    return ans
 
if __name__ == '__main__':
    print(main())

### FIXED CODE ###

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data
 
p_list = get_sieve_of_eratosthenes(10**3)
 
def factorization_counta(n):
    arr = []
    temp = n
    for i in p_list:
        if i * i > n:
            break
        elif temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append(cnt)
            
    if temp != 1:
        arr.append(1)
    if arr == []:
        arr.append(1)
    return arr

def main():
    N = int(input())
    ans = 1
    for c in range(2, N):
        p = factorization_counta(c)
        tmp = 1
        for v in p:
            tmp *= (v + 1)
        ans += tmp
    return ans
 
if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#
from copy import deepcopy
from collections import deque

d = deque()
h, w = map(int, input().split())
s = [list(map(str, list(input()))) for i in range(h)]
used = [[True for j in range(w)] for i in range(h)]
# used = [[True]*w]*h
for i in range(h):
    for j in range(w):
        if (s[i][j] == "#"):
            d.append([i, j])
            used[i][j] = False


ans = -1
while (d):

    tmp = deque()
    while(d):
        i, j = d.popleft()

        if i+1 < h and used[i+1][j]:
            s[i+1][j] = "#"
            tmp.append([i+1, j])
            used[i+1][j] = False

        if i-1 >= 0 and used[i-1][j]:
            s[i-1][j] = "#"
            tmp.append([i-1, j])
            used[i-1][j] = False

        if j+1 < w and used[i][j+1]:
            s[i][j+1] = "#"
            tmp.append([i, j+1])
            used[i][j+1] = False

        if j-1 >= 0 and used[i][j-1]:
            s[i][j-1] = "#"
            tmp.append([i, j-1])
            used[i][j-1] = False

    d = tmp
    ans += 1

print(ans)


### FIXED CODE ###

# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#
from copy import deepcopy
from collections import deque

d = deque()
h, w = map(int, input().split())
s = [list(map(str, list(input()))) for i in range(h)]
used = [[True for j in range(w)] for i in range(h)]
# used = [[True]*w]*h
for i in range(h):
    for j in range(w):
        if (s[i][j] == "#"):
            d.append([i, j])
            used[i][j] = False


ans = -1
while (d):

    tmp = deque()
    while(d):
        i, j = d.popleft()

        if i+1 < h and used[i+1][j]:
            s[i+1][j] = "#"
            tmp.append([i+1, j])
            used[i+1][j] = False

        if i-1 >= 0 and used[i-1][j]:
            s[i-1][j] = "#"
            tmp.append([i-1, j])
            used[i-1][j] = False

        if j+1 < w and used[i][j+1]:
            s[i][j+1] = "#"
            tmp.append([i, j+1])
            used[i][j+1] = False

        if j-1 >= 0 and used[i][j-1]:
            s[i][j-1] = "#"
            tmp.append([i, j-1])
            used[i][j-1] = False

    d = tmp
    ans += 1

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

N, W = map(int, input().split())

dp = [0 for j in range(W + 1)]
items = []
for i in range(N):
  w, v = map(int, input().split())
  items.append((w, v))
  
for w, v in items:
  for wk in range(W, w - 1, -1):
      tv = dp[wk - w] + v
      if tv > dp[wk]:
        dp[wk] = tv
print(max(dp))

### FIXED CODE ###

def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)


n, cap = map(int, input().split())
print(nap(n, cap))
### BUGGY CODE ###

# coding:utf-8

import sys
import heapq
import itertools
from collections import deque

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, c = LI()
sushi = [LI() for _ in range(n)]

clockwise = [0]
for x, v in sushi[::-1]:
    clockwise.append(clockwise[-1] + v)
counterclockwise = [0]
for x, v in sushi:
    counterclockwise.append(counterclockwise[-1] + v)

sushi = deque(sushi)
sushi.append([c, 0])
sushi.appendleft([0, 0])

ans = 0
for i in range(n + 1):
    for j in range(n + 1 - i):
        # cal1: 反時計回り->時計回り
        cal1 = counterclockwise[i] + clockwise[j]
        cal1 -= sushi[i][0] * 2 + (c - sushi[-1 - j][0])
        # cal2: 時計回り->反時計回り
        cal2 = counterclockwise[i] + clockwise[j]
        cal2 -= sushi[i][0] + (c - sushi[-1 - j][0]) * 2
        ans = max(ans, cal1, cal2)

print(ans)


### FIXED CODE ###

n,c = map(int, input().split())
x = []
x_r = []
v = []
for i in range(n):
    xi,vi = map(int, input().split())
    x.append(xi)
    x_r.append(c - xi)
    v.append(vi)
x_r.reverse()
x.insert(0, 0)
x_r.insert(0, 0)

score = [0]
score_r = [0]
tmp = 0
for i, vi in enumerate(v):
    tmp += vi
    score.append(tmp - x[i+1])
tmp = 0
for i, vi in enumerate(v[::-1]):
    tmp += vi
    score_r.append(tmp - x_r[i+1])

maxscore = []
maxscore_r = []
tmp = 0
for i, si in enumerate(score):
    tmp = max(tmp, si)
    maxscore.append(tmp)
tmp = 0
for i, si in enumerate(score_r):
    tmp = max(tmp, si)
    maxscore_r.append(tmp)

ans = 0
for i, si in enumerate(score):
    ans = max(si + maxscore_r[n-i] - x[i], ans)
for i, si in enumerate(score_r):
    ans = max(si + maxscore[n-i] - x_r[i], ans)

print(ans)