Harryxun/stf_run huggingface dataset:
import numpy as np
import copy
from collections import defaultdict
from heapq import heappush, heappop


def djkstra(adj_mat, src):
    dist = defaultdict(lambda: np.inf)
    dist[src] = 0

    prev = defaultdict(lambda: None)

    queue = []
    heappush(queue, (dist[src], src))

    while len(queue) > 0:
        dist_u, u = heappop(queue)
        vs = np.argwhere(adj_mat[u] > 0).flatten()
        for v in vs:
            weight = adj_mat[u, v]
            alt = dist_u + weight
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heappush(queue, (alt, v))
    visited_edges = np.zeros_like(adj_mat, dtype=np.int32)

    for v in range(adj_mat.shape[0]):
        u = prev[v]
        if u is not None:
            visited_edges[u, v] = 1
            visited_edges[v, u] = 1

    return visited_edges


def main():
    N, M = map(int, input().split())
    adj_mat = np.zeros((N, N), dtype=np.int32)
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        adj_mat[a, b] = c
        adj_mat[b, a] = c

    visited_edge_count = np.sum(
        np.stack([djkstra(adj_mat, src)[np.newaxis, :, :] for src in range(N)], axis=0), axis=0)
    out = np.sum(np.logical_and(adj_mat > 0, visited_edge_count == 0)) // 2
    print(out)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
import copy
from collections import defaultdict
from heapq import heappush, heappop


def djkstra(adj_mat, src):
    dist = defaultdict(lambda: np.inf)
    dist[src] = 0

    prev = defaultdict(lambda: None)

    queue = []
    heappush(queue, (dist[src], src))

    while len(queue) > 0:
        dist_u, u = heappop(queue)
        vs = np.argwhere(adj_mat[u] > 0).flatten()
        for v in vs:
            weight = adj_mat[u, v]
            alt = dist_u + weight
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heappush(queue, (alt, v))
    visited_edges = np.zeros_like(adj_mat, dtype=np.int32)

    for v in range(adj_mat.shape[0]):
        u = prev[v]
        if u is not None:
            visited_edges[u, v] = 1
            visited_edges[v, u] = 1

    return visited_edges


def main():
    N, M = map(int, input().split())
    adj_mat = np.zeros((N, N), dtype=np.int32)
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        adj_mat[a, b] = c
        adj_mat[b, a] = c

    visited_edge_count = np.sum(
        np.concatenate([djkstra(adj_mat, src)[np.newaxis, :, :] for src in range(N)], axis=0), axis=0)
    out = np.sum(np.logical_and(adj_mat > 0, visited_edge_count == 0)) // 2
    print(out)


if __name__ == '__main__':
    main()
def resolve():
    N = int(input()) // 2 * 2 
    A = list(map(int,input().split()))
    ans = 0

    for i in range(0,N+2,2):
        if A[i] % 2 == 1:
            ans += 1
    print(ans)
resolve()

### FIXED CODE ###

def resolve():
    N = (int(input()) + 1) // 2 * 2 
    A = list(map(int,input().split()))
    ans = 0

    for i in range(0,N,2):
        if A[i] % 2 == 1:
            ans += 1
    print(ans)
resolve()
n = int(input())
a = n//2
ans = 0
for j in range(1,n+1):
  	count = 1
	for i in range(a):
    	if n % i == 0:
      		count += 1
        if count >= 8:
          ans +=1
print(ans)

            


### FIXED CODE ###

n = int(input())
a = n//2
ans = 0
for j in range(1,n+1):
    count = 0
    for i in range(1,j+1):
        if j % i == 0:
            count += 1
        if count >= 8 and j % 2 == 1:
            ans +=1
print(ans)
n,k=map(int,input().split())
count=0
while n>0:
    count+=1
    n//=k
print(count)

### FIXED CODE ###

n,r=map(int,input().split())
if n<10:
    r+=100*(10-n)
print(r)
import math
N = int(input())
ps = []
minx = float('inf')
miny = float('inf')
mini = None
for i in range(N):
  x, y = map(int, input().split())
  if x <= minx and y < miny:
    minx = x
    miny = y
    mini = i
  ps.append((x, y))

if len(ps) == 2:
  print(0.5)
  print(0.5)
  exit()

# 2点の2等分線の単位ベクトルを返す
# i -> j に対して右方向
def divvector(xi, yi, xj, yj):
  if xi == xj:
    if yj > yi: return (1, 0)
    else: return (-1, 0)
  elif yi == yj:
    if xj > xi: return (0, -1)
    else: return (0, 1)

  a = (yi - yj) / (xi - xj) # 傾き
  b = (1/a**2)
  x = math.sqrt(1/(1+b))
  y = math.sqrt(b/(1+b))
  if xj > xi:
    if yj > yi: return (x, -y)
    else: return (-x, -y)
  else:
    if yj > yi: return (x, y)
    else: return (-x, y)

# p1 -> p0 -> p2 が時計回りかどうか
def clockwise(x0, y0, x1, y1, x2, y2):
  return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0) <= 0

# 反時計回りに、凸包を求める
first = now = mini
convexs = [now]
divvecs = { now: [] }
end = False
while not end:
  for j in range(N):
    if j != first and j in divvecs: continue
    for k in range(N):
      if k == now or k == j: continue
      if not clockwise(ps[j][0], ps[j][1], ps[now][0], ps[now][1], ps[k][0], ps[k][1]):
        break
    else:
      convexs.append(j)
      divv = divvector(ps[now][0], ps[now][1], ps[j][0], ps[j][1])
      divvecs[now].append(divv)
      if j not in divvecs:
        divvecs[j] = []
      divvecs[j].append(divv)
      now = j
      if now == first:
        end = True
      break

# 凸包を構成する各頂点について、
# 隣の頂点との二等分線のなす角を360度で割ったものが確率
# 凸包を構成しない点については、確率はほぼ0
for i in range(N):
  if i not in convexs:
    print(0)
    continue
  v1, v2 = divvecs[i]
  # すでに単位ベクトルになっているので、cos = 内積
  cos = v1[0]*v2[0] + v1[1]*v2[1]
  print(math.acos(cos) / (2*math.pi))

### FIXED CODE ###

import math
N = int(input())
ps = []
for i in range(N):
  x, y = map(int, input().split())
  ps.append((x, y, i))
ps.sort()

# i -> j のベクトル
def vec(pi, pj):
  return (pj[0] - pi[0], pj[1] - pi[1])
# i -> j 向きの外積
def det(vi, vj):
  return vi[0] * vj[1] - vi[1] * vj[0]

# 凸包を求める
cvx = []
for i in list(range(N)) + list(range(N-1))[::-1]:
  while len(cvx) >= 2 and det(vec(ps[cvx[-2]], ps[cvx[-1]]), vec(ps[cvx[-1]], ps
[i])) < 0:
    cvx.pop()
  cvx.append(i)

# 凸包の各頂点について、頂点から出る2辺のなす角を計算
ans = {}
pi = None
for i in cvx:
  x, y, j = ps[i]
  if pi is not None:
    px, py, pj = ps[pi]
    slope = math.atan2(y-py, x-px)
    if j not in ans: ans[j] = [0, 0]
    if pj not in ans: ans[pj] = [0, 0]
    ans[j][0] = slope
    ans[pj][1] = slope
  pi = i

for i in range(N):
  if i not in ans:
    print(0)
    continue
  v1, v2 = ans[i]
  if v2 < v1:
    v2 += 2*math.pi
  print(round((v2-v1) / (2*math.pi), 8))
def solve():
    N = int(input())
    ABCDE = []
    for _ in range(5):
        ABCDE.append(int(input()))
        
    min_ = min(ABCDE)
    
    print(math.floor(N/min_)+4)
    
solve()

### FIXED CODE ###

import math

def solve():
    N = int(input())
    ABCDE = []
    for _ in range(5):
        ABCDE.append(int(input()))
        
    min_ = min(ABCDE)
    
    print(math.ceil(N/min_)+4)
    
solve()
N = input()

N = str(N)

sum = 0
for i in range(0, len(N)):
  sum += N[i]

if sum % 9 ==0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

N = int(input())

if N % 9 ==0:
  print('Yes')
else:
  print('No')
import math
N=int(input())
print(math.factrial(N)%(10**9+7))

### FIXED CODE ###

import math
N=int(input())
print(math.factorial(N) % (10**9+7))
s1 = input()
s2 = input()
s3 = input()

print(s1.upper()[0] + s2.upper()[0] + s3.upper()[0])

### FIXED CODE ###

s1, s2, s3 = input().split()
print((s1[0]+s2[0]+s3[0]).upper())
S = int(input())
h = S//3600
m = (S//60)-(S//3600)
s = S//60
print(h':'m':'s)





### FIXED CODE ###

S = int(input())
h = S//3600
m = (S//60)-60*(S//3600)
s = S%60
print('{}:{}:{}'.format(h,m,s))
n = int(input())

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

s=0
for x in a:
    s+=1/x
ans=1/s

print(ans)

### FIXED CODE ###

a = int(input())
s = input()

if a >= 3200:
    print(s)
else:
    print("red")
n=int(input())
a=list(map(int,input().split()))

l=[]
l.append(0)
l.append(0)
r=[]
r.append(0)
r.append(a[n-1])
g=[]

def gcd(x,y):
  if x%y==0:
    return y
  else:
    return gcd(y,x%y)


for i in range(1,n):
  l.append(gcd(l[i],a[i-1]))
  r.append(gcd(r[i],a[n-1-i]))
  
  
for j in range(0,n):
  g.append(gcd(l[j+1],r[n-j-1]))

print(max(g))    
  
  


### FIXED CODE ###

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

l=[]
l.append(0)
l.append(0)
r=[]
r.append(a[n-1])
r.append(a[n-1])
g=[]

def gcd(x,y):
  if x%y==0:
    return y
  else:
    return gcd(y,x%y)


for i in range(1,n):
  l.append(gcd(l[i],a[i-1]))
  r.append(gcd(r[i],a[n-1-i]))
  
r[0]=l[n]

for j in range(0,n):
  g.append(gcd(l[j+1],r[n-j-1]))

print(max(g))
def main():
    import sys
    input = sys.stdin.readline

    s = input()
    if int(s.strip("'")) < 20190430:
        print('Heisei')
    else:
        print('TBD')
    
if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    #import sys
    #input = sys.stdin.readline

    s = input()
    if int(''.join(s.split('/'))) <= 20190430:
        print('Heisei')
    else:
        print('TBD')
    
if __name__ == '__main__':
    main()
def memoize(f):
    cache={}
    def helper(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return helper

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

def f(n):
    if n<=1:
        return 0
    elif n==2:
        return abs(h[1]-h[0])
    elif n==3:
        return abs(h[2]-h[0])
    else:
        return min(f(n-1)+abs(h[n-1]-h[n-2]),f(n-2)+abs(h[n-1]-h[n-3]))

print(f(N))


### FIXED CODE ###

def memoize(f):
    cache={}
    def helper(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return helper

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

import sys
sys.setrecursionlimit(1000000)

@memoize
def f(n):
    if n==1:
        return 0
    elif n==2:
        return abs(h[1]-h[0])
    elif n==3:
        return abs(h[2]-h[0])
    else:
        return min(f(n-1)+abs(h[n-1]-h[n-2]),f(n-2)+abs(h[n-1]-h[n-3]))

print(f(N))
n = int(input())
s = list(input())
t = "abcdefghijklmnopqrstuvwxyz"
ans = 1

for i in range(n):
    ans *= (s.count(t[i]) + 1)
    if ans > 10**9 + 7:
        ans %= 10**9+7

print(ans-1)

### FIXED CODE ###

n = int(input())
s = list(input())
t = "abcdefghijklmnopqrstuvwxyz"
ans = 1

for i in range(26):
    ans *= (s.count(t[i]) + 1)

print((ans-1)%(10**9+7))
N,X,M=map(int, input().split())

from math import log, ceil

ans=0

ini=[0]*M
mod=[0]*M
ini[0]=sum(list(range(1,M)))
Counter=[0]*M
Counter[0]=M-1

for i in range(1,M):
    now=i+1
    temp=now
    count=1
    while now**2<M:
        now=now**2
        temp+=now
        count+=1
    m=now**2%M
    ini[i]=temp
    mod[i]=m
    Counter[i]=count
#print(ini[:5])
#print("ok")
#print(Counter[:100])
ans=0
count=0
now=X
done=[-1]*M
ok=False
while True:
    if count+Counter[now-1]>N:
        break
    if done[now-1]==-1 or ok==True:
        done[now-1]=(ans, count)
        ans+=ini[now-1]
        #print(ini[now-1])
        count+=Counter[now-1]
        now=mod[now-1]
    else:
        pans, pcount=done[now-1]
        #print(count, pcount)
        #print("break")
        ans+=(ans-pans)*((N-count)//(count-pcount))
        count+=(count-pcount)*((N-count)//(count-pcount))
        #print(count)
        ok=True





    


while True:
    if count==N:
        break
    ans+=now
    now=now**2
    count+=1

    

print(ans)






#print(ini)
#print(mod)
#print(Counter)

### FIXED CODE ###

N,X,M=map(int, input().split())

ans=0
count=0
now=X
done=[-1]*(M-1)
L=[]
if now==0:
    print(ans)
    exit()
j=False
while True:
    if count==N:
        break

    if now==0:
        print(ans)
        exit()
    else:
        if done[now-1]==-1:
            done[now-1]=1
            L.append(now)
        else:
            for i in range(len(L)):
                if L[i]==now:
                    j=i
            break
    ans+=now
    count+=1
    now=(now**2)%M

if j:
    L=L[j:]

total=sum(L)
length=len(L)

ans+=((N-count)//length)*total
ans+=sum(L[:(N-count)%length])
print(ans)
A,B,K = map(int,input().split())

i=0
j=1
while i<K:
  if A%j=0 and B%j=0:
     i +=1
  else:
     i =i
  j+=1

print(j)
  


### FIXED CODE ###

A,B,K = map(int,input().split())

i=0
j=100
while i<K:
    if A%j==0 and B%j==0:
        i +=1
    else:
        i =i
    j-=1

print(j+1)
N = int(input())
lst=[]
for i in range(1,int(N**0.5)+1):
    if n%i==0:
        lst.append(i+n//i-2)
print(min(lst))

### FIXED CODE ###

N = int(input())
lst=[]
for i in range(1,int(N**0.5)+1):
    if N%i==0:
        lst.append(i+N//i-2)
print(min(lst))
D, N = map(int, input().split())
if N = 100:
    N = 101
if D == 0:
    print(N)
elif D == 1:
    print(N * 100)
else:
    print(N * (100 ** 2))

### FIXED CODE ###

D, N = map(int, input().split())
if N == 100:
    N = 101
if D == 0:
    print(N)
elif D == 1:
    print(N * 100)
else:
    print(N * (100 ** 2))
import itertools,math,bisect,pprint,sys
n, a, b = map(int, raw_input().split())
v = sorted(map(int, raw_input().split()))[::-1]
res1 = sum(v[:a])*1.0/a
print res1
res2 = 0
def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)
if a==v[:a].count(v[a-1]):
    res2 = 0
    for i in range(a,b+1):
        res2 += nCr(v.count(v[a]),i)
    print res2
else:
    print nCr(v.count(v[a-1]),v[:a].count(v[a-1]))

### FIXED CODE ###

import itertools,math,bisect,pprint,sys
n, a, b = map(int, raw_input().split())
v = sorted(map(int, raw_input().split()))[::-1]
res1 = sum(v[:a])*1.0/a
print '{0:.6f}'.format(res1)
res2 = 0
def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)
if a==v[:a].count(v[a-1]):
    res2 = 0
    for i in range(a,b+1):
        if i <= v.count(v[a-1]):
            res2 += nCr(v.count(v[a-1]),i)
    print res2
else:
    print nCr(v.count(v[a-1]),v[:a].count(v[a-1]))
n = int(input())
A = list(map(int,input().split()))

def zenbu(m, B):
    if m == 1:
        return B[0]
    elif m == 2:
        return max(B[0],B[1])
    elif m == 3:
        return max(B[0],B[1],B[2])
    elif m%2 == 0: #偶数の場合
        temp = 0
        for i in range(m//2-1):
            temp += B[i*2]
        return max(temp+ max(B[m-2],B[m-1]), zenbu(m-2, B[:-2])+ B[m-1])
    else:#奇数の場合
        temp = 0
        for i in range((m-1)//2):
            temp += B[i*2]
        return max(temp, zenbu(m-2,B[:-2])+ B[m-1], zenbu(m-3,B[:-3])+ max(B[m-2],B[m-1]))

ans = zenbu(n,A)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
if N%2 == 0:
  dp = [[0]*2 for _ in range(N)] #0index
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  for i in range(2,N):
    dp[i][0] = dp[i-2][0]+A[i]
    if i-3>=0:
      dp[i][1] = max(dp[i-2][1],dp[i-3][0])+A[i]
    else:
      dp[i][1] = max(dp[i-2][1],0)+A[i]
  ans = max(dp[-2][0],dp[-1][1])
  print(ans)
#i個目を使ってj(0-2)回多く飛んでいる。
else: #N%2 == 1:
  dp = [[0]*3 for _ in range(N)] #0index
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  dp[2][2] = A[2]
  dp[2][0] = A[0]+A[2]
  #print(dp)
  for i in range(3,N):
    dp[i][0] = dp[i-2][0]+A[i]
    if i-3 >= 0:
      dp[i][1] = max(dp[i-2][1],dp[i-3][0])+A[i]
    else:
      dp[i][1] = max(dp[i-2][1],0)+A[i]
    if i-4 >= 0:
      dp[i][2] = max(dp[i-2][2],dp[i-3][1],dp[i-4][0])+A[i]
    elif i-3 >= 0:
      dp[i][2] = max(dp[i-2][2],dp[i-3][1],0)+A[i]
  #else:
  #  dp[i][2] = max(dp[i-2][2],0,0)+A[i]
  #print(dp[-1],dp[-2],dp[-3])

  ans = max(dp[-3][0],dp[-2][1],dp[-1][2])
  print(ans)
  exit()
a,b = inpur().split()
if a == b:
    print("H")
else:
    print("D")

### FIXED CODE ###

a,b = input().split()
if a == b:
    print("H")
else:
    print("D")
import sys


N,P = map(int,input().split())
S = list(sys.stdin.readline().rstrip())

A = [0]*(N)
A[-1] = int(S[-1])
A[-1] %= P
base = 10
for i in reversed(range(N-1)):
    A[i] = A[i+1] + base*int(S[i])
    A[i] %= P
    base *= 10


ans = 0
if P==2 or P==5:
    for i in reversed(range(N)):
        if int(S[i])%P==0:
            ans += i+1
else:
    a = A[10**9]
    nums = {}
    for a in A:
        nums[a] = 0
    for a in A:
        nums[a] += 1
    
    for n in nums.keys():
        k = nums[n]
        if n==0:
            ans += k*(k+1)//2
        else:
            ans += k*(k-1)//2
    
print(ans)    



### FIXED CODE ###

import sys


N,P = map(int,input().split())
S = list(input())

A = [0]*(N)
A[-1] = int(S[-1])
A[-1] %= P
base = 10 % P
for i in reversed(range(N-1)):
    A[i] = A[i+1] + base*int(S[i])
    A[i] %= P
    base *= 10
    base %= P


ans = 0
if P==2 or P==5:
    for i in reversed(range(N)):
        if int(S[i])%P==0:
            ans += i+1
else:
    nums = {}
    for a in A:
        if not (a in nums):
            nums[a] = 1
        else:
            nums[a] += 1
    
    for n in nums.keys():
        k = nums[n]
        if n==0:
            ans += k*(k+1)//2
        else:
            ans += k*(k-1)//2
    
print(ans)
class dset:
    def __init__(self,n):
        self.par = [-1]*n

    def size(self,n):
        return -self.par[self.root(n)]

    def root(self,n):
        return self.par[n] = root(par[n]) if self.par[n]>=0 else n

    def same(self, a, b):
        return self.root(a) == self.root(b)

    def __link__(self,a,b):
        if a == b:
            return 
        
        if self.size(a) < self.size(b):
            a,b = b,a
        
        self.par[a] += self.par[b]
        self.par[b] = a

    def unite(self,a,b):
        self.__link__(
            self.root(a)
            ,self.root(b)
            )


def main():
    n, m = map(int, input().split() ) 


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

    ds = dset(n)

    ans = [0]*m
    ans[-1] = n*(n-1)//2
    for i in range(m-1,0,-1):
        ans[i-1] = ans[i]

        a,b = ins[i]
        a-=1
        b-=1

#        print(ins[i])
       # print( (ds.root(a),ds.root(b)) ) 
        if not ds.same(a,b):
            x = ds.size(a)
            y = ds.size(b)
            #print((x,y))
            ans[i-1] -= x*y
            ds.unite(a,b)

    for e in ans:
        print(e)

if __name__ == '__main__':
    main()

### FIXED CODE ###




class dset:
    def __init__(self,n):
        self.par = [-1]*n

    def size(self,n):
        return -self.par[self.root(n)]

    def root(self,n):
        if self.par[n]<0:
            return n
        else:
            self.par[n] = self.root(self.par[n])
            return self.par[n]

    def same(self, a, b):
        return self.root(a) == self.root(b)

    def __link__(self,a,b):
        if a == b:
            return 
        
        if self.size(a) < self.size(b):
            a,b = b,a
        
        self.par[a] += self.par[b]
        self.par[b] = a

    def unite(self,a,b):
        self.__link__(
            self.root(a)
            ,self.root(b)
            )


def main():
    n, m = map(int, input().split() ) 


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

    ds = dset(n)

    ans = [0]*m
    ans[-1] = n*(n-1)//2
    for i in range(m-1,0,-1):
        ans[i-1] = ans[i]

        a,b = ins[i]
        a-=1
        b-=1

#        print(ins[i])
       # print( (ds.root(a),ds.root(b)) ) 
        if not ds.same(a,b):
            x = ds.size(a)
            y = ds.size(b)
            #print((x,y))
            ans[i-1] -= x*y
            ds.unite(a,b)

    for e in ans:
        print(e)

if __name__ == '__main__':
    main()
import math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
A = list(map(int, input().split()))
answer = 0
mod = 10**9 + 7
# print(*A)
# print(lcm(*A))
LCM = lcm(*A)

for i in range(N):
    answer += LCM // A[i]

print(answer % mod)

### FIXED CODE ###

from fractions import gcd
from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
A = list(map(int, input().split()))
answer = 0
mod = 10**9 + 7
LCM = lcm(*A)

for i in range(N):
    answer += LCM // A[i]

print(answer % mod)
n, c = list(map(int, input().split()))
sushi1 = []
sushi2 = []
c1 = []
c2 = []
c3 = []
c4 = []
k1 = 0
k2 = 0
for i in range(n):
    x, v = list(map(int, input().split()))
    sushi1.append((x, v))
    sushi2.append((c-x, v))
sushi1.sort()
sushi2.sort()
for j in range(n):
    k1 += sushi1[j][1]
    k2 += sushi2[j][1]
    c1.append(k1-sushi1[j][0])
    c2.append(k2-sushi2[j][0])
for k in range(n):
    c3.append(c1[k]+max(c2[:n-k])-sushi1[k][0])
    c4.append(c2[k]+max(c1[:n-k])-sushi2[k][0])
print(max(c1+c2+c3+c4, 0)

### FIXED CODE ###

import numpy as np
n, c = list(map(int, input().split()))
xv = list(list(map(int, input().split())) for i in range(n))
sushi1, max1, sushi2, max2 = [0], [0], [0], [0]
sum1, sum2 = 0, 0
for x, v in xv:
    sum1 += v
    sushi1.append(max(sum1 - x, sushi1[-1]))
    max1.append(max(sum1 - 2*x, max1[-1]))
for x, v in xv[::-1]:
    sum2 += v
    sushi2.append(max(sum2 - (c-x), sushi2[-1]))
    max2.append(max(sum2 - 2*(c-x), max2[-1]))
ans1 = max(np.array(sushi1) + np.array(max2[::-1]))
ans2 = max(np.array(sushi2) + np.array(max1[::-1]))
print(max(0, ans1, ans2))
# Fast IO (only use in integer input)

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

# Fenwick Tree to Calculate Sum

MaxLength = 500001
FenwickTree = []

CurLen = MaxLength
while CurLen != 0:
    FenwickTree.append([0] * CurLen)
    CurLen //= 2

Depth = len(FenwickTree)

def addElem(n,index): # add n to an element in index
    for j in range(Depth):
        FenwickTree[j][index] += n
        index //= 2

def firstNSum(n): # Return the sum of the first n elements (0 to n-1)
    nCpy = n
    summ = 0
    depthCur = 0
    while nCpy != 0:
        if nCpy % 2 != 0:
            summ += FenwickTree[depthCur][nCpy - 1]
        nCpy //= 2
        depthCur += 1
    return summ

N,Q = map(int,input().split())
c = list(map(int,input().split()))
firstLocColor = [-1] * N
ans = [-1] * Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,i))
queries.sort(key = lambda x: x[1])
queryIndex = 0
for i in range(N):
    # Update the Fenwick tree to count ith element
    if firstLocColor[c[i] - 1] == -1:
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    else:
        addElem(-1,firstLocColor[c[i] - 1])
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    
    # get query
    while queryIndex < Q and queries[queryIndex][1] - 1 <= i:
        if queries[queryIndex][1] - 1 == i:
            ans[queries[queryIndex][2]] = firstNSum(queries[queryIndex][1]) - firstNSum(queries[queryIndex][0] - 1)
        queryIndex += 1

for elem in ans:
    print(elem)

### FIXED CODE ###

# Fast IO (only use in integer input)

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

# Fenwick Tree to Calculate Sum

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

MaxLength = 2 * N
FenwickTree = []

CurLen = MaxLength
while CurLen != 0:
    FenwickTree.append([0] * CurLen)
    CurLen //= 2

Depth = len(FenwickTree)

def addElem(n,index): # add n to an element in index
    for j in range(Depth):
        FenwickTree[j][index] += n
        index //= 2

def firstNSum(n): # Return the sum of the first n elements (0 to n-1)
    nCpy = n
    summ = 0
    depthCur = 0
    while nCpy != 0:
        if nCpy % 2 != 0:
            summ += FenwickTree[depthCur][nCpy - 1]
        nCpy //= 2
        depthCur += 1
    return summ

c = list(map(int,input().split()))
firstLocColor = [-1] * N
ans = [-1] * Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,i))
queries.sort(key = lambda x: x[1])
queryIndex = 0
for i in range(N):
    # Update the Fenwick tree to count ith element
    if firstLocColor[c[i] - 1] == -1:
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    else:
        addElem(-1,firstLocColor[c[i] - 1])
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    
    # get query
    while queryIndex < Q and queries[queryIndex][1] - 1 <= i:
        if queries[queryIndex][1] - 1 == i:
            ans[queries[queryIndex][2]] = firstNSum(queries[queryIndex][1]) - firstNSum(queries[queryIndex][0] - 1)
        queryIndex += 1

for elem in ans:
    print(elem)