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

def resolve():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    cost = [float("inf")]*n
    cost[0] = 0
    for i in range(n):
        for j in range(1, min(k+1, n-i)):
            cost[i+j] = min(cost[i+j], cost[i] + abs(h[i+j]-h[i]))
    print(cost[n-1])
resolve()

### FIXED CODE ###

def resolve():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    cost = [float("inf")]*n
    cost[0] = 0
    for i in range(n):
        for j in range(1, min(k+1, n-i)):
            cost[i+j] = min(cost[i+j], cost[i] + abs(h[i+j]-h[i]))
    print(cost[n-1])
resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

class RangeUpdateQuery:
    def __init__(self, n):
        self.n0 = 2**(n-1).bit_length()
        self.INF = (-1, -1)
        self.data = [self.INF]*(2*self.n0-1)

    def update(self, l,r,v):
        l += self.n0
        r += self.n0
        while l < r:
            if r&1:
                r -= 1
                self.data[r-1] = v
            if l&1:
                self.data[l-1] = v
                l += 1
            l >>=1
            r >>=1

    def query(self, i):
        i += self.n0-1
        res = self.INF
        while i+1:
            if self.data[i] > res:
                res = self.data[i]
            i = ~-i//2
        return res

n,q = map(int, input().split())
start = [None]*q
se = set()
road = []
for i in range(n):
    s,t,x = map(int, input().split())
    se.add(x-s)
    se.add(x-(t-1))
    road.append([x, x-(t-1), x-s])
for i in range(q):
    d = int(input())
    start[i] = -d
    se.add(-d)

dd = sorted(se)
d = {j:i for i, j in enumerate(dd)}
k = len(d)

RUQ = RangeUpdateQuery(k)
road.sort(reverse=True)
for i, (x, s, t) in enumerate(road):
    l = d[s]
    r = d[t]
    RUQ.update(l, r+1, (i, x))

ans = []
for i in range(q):
    _, x = RUQ.query(d[start[i]])
    ans.append(x)

print(*ans, sep="\n")

### FIXED CODE ###

import sys
input = sys.stdin.readline

class RangeUpdateQuery:
    def __init__(self, n):
        self.n0 = 2**(n-1).bit_length()
        self.INF = float("inf")
        self.data = [self.INF]*(2*self.n0-1)

    def update(self, l,r,v):
        l += self.n0
        r += self.n0
        while l < r:
            if r&1:
                r -= 1
                self.data[r-1] = v
            if l&1:
                self.data[l-1] = v
                l += 1
            l >>=1
            r >>=1

    def query(self, i):
        i += self.n0-1
        res = self.INF
        while i+1:
            if self.data[i] < res:
                res = self.data[i]
            i = ~-i//2
        return res

n,q = map(int, input().split())
start = [None]*q
se = set()

road = []
for i in range(n):
    s,t,x = map(int, input().split())
    road.append([x, x-t, x-s])
for i in range(q):
    d = int(input())
    start[i] = -d

start = start[::-1]

RUQ = RangeUpdateQuery(q)
road.sort(reverse=True)
from bisect import bisect_left,bisect_right
for i, (x, s, t) in enumerate(road):
    l = bisect_right(start, s)
    r = bisect_right(start, t)
    #print(x, (s,t), l, r)
    RUQ.update(l, r, x)

ans = []
for i in range(q):
    x = RUQ.query(i)
    if x == float("inf"):
        x = -1
    ans.append(x)
ans = ans[::-1]
print(*ans, sep="\n")
### BUGGY CODE ###

def solve():
    a = input()
    a = list(a)
    q = int(input())
    
    for _ in range(q):
        _q = [i for i in input().split()]
        t, f, c =0, 0, 0
        t = int(_q[0])
        if t == 2:
            f, c = int(_q[1]), _q[2]
        
        if t == 1:
            a = list(reversed(a))
        elif t == 2:
            if f == 1:
                a = list(reversed(a))
                a.append(c)
                a = list(reversed(a))
            elif f == 2:
                a.append(c)
    
    print("".join(a))


if __name__ == "__main__":
    solve()

### FIXED CODE ###

def solve():
    a = input()
    q = int(input())
    
    top = []
    tail = []
    rev = 0
    for _ in range(q):
        _q = [i for i in input().split()]
        t, f, c =0, 0, 0
        t = int(_q[0])
        if t == 2:
            f, c = int(_q[1]), _q[2]
        
        if t == 1:
            rev = 1 - rev
        elif t == 2:
            if (f + rev) % 2 == 1:
                top.append(c)
            else:
                tail.append(c)
                
    if rev == 1:
        a = a[::-1]
        _top = tail
        tail = top
        top = _top
    
    print("".join(list(reversed(top))), end="")
    print(a, end="")
    print("".join(tail))


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

# https://atcoder.jp/contests/abc102/tasks/arc100_a
# C - Linear Approximation

N = int(input().split()[0])
a_list = list(map(int, input().split()))
min_b = float('inf')
max_a = max(a_list)

work_list = [a - i - 1 for i, a in enumerate(a_list)]
work_list = list(set(work_list))

for b in work_list:  # 10 ** 5
    total_b = 0
    for i, a in enumerate(a_list):  # 10 ** 5
        total_b += abs(a - (b + i + 1))
    min_b = min(min_b, total_b)

print(min_b)


### FIXED CODE ###

# https://atcoder.jp/contests/abc102/tasks/arc100_a
# C - Linear Approximation

N = int(input().split()[0])
a_list = list(map(int, input().split()))
min_b = float('inf')
max_a = max(a_list)

work_list = [a - (i + 1) for i, a in enumerate(a_list)]
w = sorted(work_list)[int(N / 2)]
ans = sum([abs(x - w) for x in work_list])
print(ans)
### BUGGY CODE ###

N = int(input())

A = []
for i in range(N):
    A.append(int(input()))

B = []
for i in range(N):
    B = A[:i] + A[i+1:]
    #print(B)
    print(max(B))

### FIXED CODE ###

N = int(input())

A = []
for i in range(N):
    A.append(int(input()))
    
B = sorted(A,reverse = True)

for i in A:
    if i == B[0]:
        print(B[1])
    else:
        print(B[0])
### BUGGY CODE ###

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

dp = [[-1]*n for i in range(n)]
for i in range(n):
    dp[i][i] = 0
cumsum = [0]
for i in range(n):
    cumsum.append(cumsum[-1] + a[i])

def calc_cost(left, right):
    if dp[left][right] >= 0:
        return dp[left][right]
    min_ = min(calc_cost(left, i) + calc_cost(i+1, right) for i in range(left, right))
    dp[left][right] = cumsum[right+1]-cumsum[left] + min_
    return dp[left][right]

print(calc_cost(0,n-1))

### FIXED CODE ###

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

dp = [[-1]*n for i in range(n)]
for i in range(n):
    dp[i][i] = 0
cumsum = [0]
for i in range(n):
    cumsum.append(cumsum[-1] + a[i])

def calc_cost(left, right):
    if dp[left][right] >= 0:
        return dp[left][right]
    min_ = min(calc_cost(left, i) + calc_cost(i+1, right) for i in range(left, right))
    dp[left][right] = cumsum[right+1]-cumsum[left] + min_
    return dp[left][right]

print(calc_cost(0,n-1))
### BUGGY CODE ###

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

#累積和
ans=0
acum=[]
acumi=0
for i in range(n):
    acumi+=a[i]
    acum.append(acumi)
ans+=acum.count(0)
#print(a)
#print(acum)
i_ans=0
for i in range(n):
    i_ans+=a[i]
    ans+=acum[i+1:].count(i_ans)
#    print(ans,i_ans,acum[i+1:])
print(ans)


### FIXED CODE ###

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

#累積和
ans=0
acum={}
acumi=0
for i in range(n):
    acumi+=a[i]
    acum[acumi]=acum.get(acumi, 0)+1

for k,v in acum.items():
    if(k==0):
        ans+=v*(1+v)//2
    else:
        ans+=(v-1)*v//2
print(ans)
### BUGGY CODE ###

h,w = map(int,input().split())
raw = []
for _ in range(h):
  tmp = input()
  add = []
  for j in range(w):
    if tmp[j] == '.':
      add.append(0)
    else:
      add.append(2)
  raw.append(add)
nex = [[0,1],[0,-1],[1,0],[-1,0]]
can = []
from copy import deepcopy as dc
for a in range(h):
  for b in range(w):
    if raw[a][b] == 2:
      continue
    last = dc(raw)
    last[a][b] = 1
    ans = 0
    while True:
      now = dc(last)
      ans += 1
      for i in range(h):
        for j in range(w):
          if last[i][j] == 1:
            for x in nex:
              if 0 <= i+x[0] < h and 0 <= j+x[1] < w:
                if now[i+x[0]][j+x[1]] == 0:
                  now[i+x[0]][j+x[1]] = 1
      check = 1
      for i in range(h):
        for j in range(w):
          check *= now[i][j]
      if check > 0:
        can.append(ans)
        #print(a,b)
        #for y in now:
          #print(y)
        break
      #if (a,b) == (0,4):
        #print(ans)
        #for y in now:
          #print(y)
      last = dc(now)
print(max(can))
#print(can)
#print(raw)

### FIXED CODE ###

h,w = map(int,input().split())
n = h * w
raw = []
for i in range(h):
  tmp = input()
  add = []
  for j in range(w):
    if tmp[j] == '.':
      add.append(0)
    else:
      add.append(1)
  raw += add
wf = [[1000 for _ in range(n)] for _ in range(n)]
for i in range(n):
  if raw[i] == 0:
    wf[i][i] = 0
    d = []
    if i-w >= 0:
      d.append(i-w)
    if i+w < n:
      d.append(i+w)
    if i%w != 0:
      d.append(i-1)
    if (i+1)%w != 0:
      d.append(i+1)
    for e in d:
      if raw[e] == 0:
        wf[i][e] = 1
#for x in wf:
  #print(x)
for k in range(n):
  for i in range(n):
    for j in range(n):
      if wf[i][k] + wf[k][j] < wf[i][j]:
        wf[i][j] = wf[i][k] + wf[k][j]
ans = 0
for i in range(n):
  for j in range(n):
    if ans < wf[i][j] % 1000:
      ans = wf[i][j]
print(ans)
#for x in wf:
  #print(x)
### BUGGY CODE ###

N= int(input())
S=input()
r=[]
g=[]
b=[]
for i in range(N):
    if S[i]=="R":
        r.append(i)
    elif S[i]=="G":
        g.append(i)
    else:
        b.append(i)

t=0
for i in range(len(r)):
    for j in range(len(g)):
        k=0
        if 2*r[i]-g[j] in b:
            k+=1
        if 2*g[j]-r[i] in b:
            k+=1
        if (r[i]+g[j])/2 in b:
            k+=1
        t+=(len(b)-k)
print(t)

### FIXED CODE ###

N= int(input())
S=input()
r=[]
g=[]
b=[]
A=0
B=0
C=0
for i in range(N):
    if S[i]=="R":
        r.append(i)
        A+=1
    elif S[i]=="G":
        g.append(i)
        B+=1
    else:
        b.append(i)
        C+=1
k=0
for i in range(N-2):
    for j in range(i+1,N-1):
        t=2*j-i
        if t<N:
            if S[i]!=S[j] and S[i]!=S[t] and S[t]!=S[j] :
                k+=1

print(A*B*C-k)
### BUGGY CODE ###

H, N = map(int, input().split())
A,B = [],[]
for _ in range(N):
	ta,tb = map(int, input().split())
	A.append(ta)
	B.append(tb)

ini_A,ini_B = A[0], B[0]
dp = [-(-j//ini_A)*ini_B for j in range(H+1)]

for i in range(1,N):
	obj_A,obj_B = A[i], B[i]
	for j in range(H+1):
		if j < A[i]:
			dp[j] = min(dp[j], -(-j//obj_A)*obj_B)
		else:
			dp[j] = min(dp[j], -(-j//obj_A)*obj_B, dp[j-obj_A]+obj_B)

print(dp[-1])


### FIXED CODE ###

H, N = map(int, input().split())
A,B = [],[]
for _ in range(N):
	ta,tb = map(int, input().split())
	A.append(ta)
	B.append(tb)

ini_A,ini_B = A[0], B[0]
dp = [-(-j//ini_A)*ini_B for j in range(H+1)]

for i in range(1,N):
	obj_A,obj_B = A[i], B[i]
	for j in range(H+1):
		if j < A[i]:
			dp[j] = min(dp[j], -(-j//obj_A)*obj_B)
		else:
			dp[j] = min(dp[j], -(-j//obj_A)*obj_B, dp[j-obj_A]+obj_B)

print(dp[-1])
### BUGGY CODE ###

a,b = map(int,input().split())
xor = 0

for i in range(a,b+1):
    xor ^= i
else:
    ans = xor
    print(ans)

### FIXED CODE ###

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

if a%2 == 0 and b%2 == 0:
    ans = b^((b-a)//2)%2
elif a%2 == 0 and b%2 != 0:
    ans = ((b-a+1)//2)%2
elif a%2 != 0 and b%2 == 0:
    ans = a^b^((b-1-a)//2)%2
else:
    ans = a^((b-a)//2)%2

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

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

As = []
a_ = -1
for i in range(m):
  a = int(input())
  if a == a_ + 1:
    print(0)
    sys.exit()
  As.append(a)
  a_ = a

nums = [1] + [0] * n
if 1 in As:
  pass
else:
  nums[1] = 1
  
for i in range(2, n + 1):
  if i in As:
    continue
  else:
    nums[i] = (nums[i-1] + nums[i-2]) % 1000000007
    
print(nums[-1])

### FIXED CODE ###

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

if m > 0:
  As = set(map(int, sys.stdin))
else:
  As = set()

nums = [0] * (n + 1)
nums[0] = 1
if 1 in As:
  pass
else:
  nums[1] = 1
  
for i in range(2, n + 1):
  if i in As:
    continue
  else:
    nums[i] = (nums[i-1] + nums[i-2]) % 1000000007
    
print(nums[-1])
### BUGGY CODE ###

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

num = K
memo = []
town = 1
for _ in range(K):
    memo.append(town)
    if not A[town-1] in memo:
        town = A[town-1]
        num -= 1
    else:
        index = memo.index(A[town-1])
        l = len(memo) - index
        if num % l == 0:
            town = memo[-1]
        else:
            town = memo[index + (num % l) - 1]
        break
print(town)

### FIXED CODE ###

from collections import deque
n, k = map(int, input().split())
a = [-1] + list(map(int, input().split()))
town = [-1] * (n + 1)
town[1] = 0
now_town = 1
second_first = 0
while True:
    if town[a[now_town]] != -1:
        second_first = a[now_town]
        break
    town[a[now_town]] = town[now_town] + 1
    if town[a[now_town]] == k:
        print(a[now_town])
        exit()
    now_town = a[now_town]
    # print(town)
start_index = town[second_first]
end_index = max(town)
rest = k - end_index
div = (rest-1) % (end_index - start_index + 1)
# print(rest, div)
ans = town.index((start_index) + div)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,list(input().split())))
Q = int(input())
s = []
for i in range(Q):
    B,C = map(int,(input().split()))
    for j in range(N):
        if A[j] == B:
            A[j] = C
    s.append(sum(A))
for i in range(Q):
    print(s[i])

### FIXED CODE ###

import sys,collections
input = sys.stdin.readline

N=input().rstrip()
A=list(map(int,input().split()))
Ac = collections.Counter(A)
Q = int(input())
for i in range(Q):
    B,C = list(map(int,input().split()))
    nb = Ac[B]
    Ac[C] += Ac[B]
    Ac[B] = 0

    if i==0:
        ans = 0
        for key,val in Ac.items():
            ans += key*val
    else:
        ans +=nb*C - nb*B
    
    print(ans)
### BUGGY CODE ###

import itertools
import operator

dataset = []
while True:
    try:
        dataset.append(input())
    except EOFError:
        break

for item in dataset:
    a, b, c, d, e, f = [int(i) for i in item.split()]
    for i in range(-1000, 1001):
        for j in range(-1000, 1001):
            if a * i + b * j == c and d * i + e * j == f:
                print("{:.3f} {:.3f}".format(i, j))

### FIXED CODE ###

import sys
dataset = sys.stdin.readlines()

for item in dataset:
    a, b, c, d, e, f = list(map(int, item.split()))

    y = (c * d - f * a)/(b * d - e * a)
    x = (c * e - b * f) / (a * e - b * d)
    if x == 0:
        x = 0
    print("{:.3f} {:.3f}".format(x, y))
### BUGGY CODE ###

import numpy as np

n, x, y = map(int,input().split())
ans = np.zeros(n-1)

for i in range(1,n):
    for j in range(i+1,n+1):
        if j <= x or y <= i:
            dist = j - i
        else:
            dist = j - i
            short = abs(x - i) + 1 + abs(y - j)
            if short < dist:
                dist = short
        ans[dist-1] = ans[dist-1] + 1

for k in ans:
    print(int(k))

### FIXED CODE ###

n, x, y = map(int,input().split())
ans = [0]*(n-1)

for i in range(1,n):
    for j in range(i+1,n+1):
        if j <= x or y <= i:
            dist = j - i
        else:
            dist = j - i
            short = abs(x - i) + 1 + abs(y - j)
            dist = min(dist, short)
        ans[dist-1] += 1

for k in ans:
    print(k)
### BUGGY CODE ###

n=int(input())
li=list(map(int,input().split()))
if 0 in li:
    print(0)
    exit()
ans=1

for i in li:
    ans=ans*i

if ans>10**18:
    print(-1)

else:
    print(ans)

### FIXED CODE ###

n=int(input())
li=list(map(int,input().split()))
if 0 in li:
    print(0)
    exit()
ans=1

for i in li:
    ans=ans*i
    if ans>10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

from sys import stdin
import math
import fractions
from collections import deque
import sys

# 再起の上限を変更
sys.setrecursionlimit(100000)

INF = 10 ** 10

# 深さ優先探索
def dfs(i):
    global is_visited
    global tsort_res

    if is_visited[i]:
        return 

    is_visited[i] = True
    for j in nextl[i]:
        dfs(j)
    
    # 帰りがけ順で追加
    # 追加は先頭に行う
    tsort_res.insert(0, i)


# トポロジカルソート
def tsort():
    for i in range(1, N+1):
        dfs(i)

if __name__ == "__main__":

    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    xv = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]

    # トポロジカルソートで頂点iより後ろのパスの最大長
    dp = [0] * (N+1)

    # 頂点xから頂点vへの有向辺
    nextl = [[] for _ in range(N+1)]
    for x, v in xv:
        nextl[x].append(v)
    
    # トポロジカルソートされた結果の入るリスト
    tsort_res = []

    is_visited = [False] * (N+1)

    tsort()

    # 今回は逆順に使うのでリバースする
    # 汎用性のため、dfsでは先頭に追加するようにしている
    tsort_res = tsort_res[::-1]

    for x in tsort_res:
        for v in nextl[x]:
            dp[x] = max(dp[x], dp[v] + 1)


    # for DEBUG
    #print(dp)
    print(max(dp))

### FIXED CODE ###

from sys import stdin
import math
import fractions
from collections import deque
import sys

# 再起の上限を変更
sys.setrecursionlimit(100000)

INF = 10 ** 10

# 深さ優先探索
def dfs(i):
    global is_visited
    global tsort_res

    if is_visited[i]:
        return 

    is_visited[i] = True
    for j in nextl[i]:
        dfs(j)
    
    # 帰りがけ順で追加
    # 追加は先頭に行う
    tsort_res.appendleft(i)


# トポロジカルソート
def tsort():
    for i in range(1, N+1):
        dfs(i)

if __name__ == "__main__":

    N, M = [int(x) for x in stdin.readline().rstrip().split()]

    # トポロジカルソートで頂点iより後ろのパスの最大長
    dp = [0] * (N+1)

    # 頂点xから頂点vへの有向辺
    nextl = [[] for _ in range(N+1)]
    for _ in range(M):
        x, v = list(map(int, stdin.readline().rstrip().split()))
        nextl[x].append(v)
    
    # トポロジカルソートされた結果の入るリスト
    tsort_res = deque([])

    is_visited = [False] * (N+1)

    tsort()

    # 今回は逆順に使うのでリバースする
    # 汎用性のため、dfsでは先頭に追加するようにしている
    tsort_res = list(tsort_res)[::-1]

    for x in tsort_res:
        for v in nextl[x]:
            dp[x] = max(dp[x], dp[v] + 1)


    # for DEBUG
    #print(dp)
    print(max(dp))
### BUGGY CODE ###

K, S = map(int, input().split())
c = 0
for x in range(K + 1):
    for y in range(x + 1):
        if x + y > S:
            break
        for z in range(y + 1):
            if x + y + z > S:
                break
            if x + y + z == S:
                if x != y and x!= z and y!= z:
                    c += 6
                elif x == y and x == z and y == z:
                    c += 1
                else:
                    c += 3
print(c)

### FIXED CODE ###

K, S = map(int, input().split())
c = 0
for x in range(K + 1):
    for y in range(x + 1):
        if x + y > S:
            break
        z = S - x - y
        if z >= 0 and z < y + 1:
            if x != y and x!= z and y!= z:
                c += 6
            elif x == y and x == z and y == z:
                c += 1
            else:
                c += 3
print(c)
### BUGGY CODE ###

n,m,q=map(int,input().split())
line=sorted([list(map(int,input().split())) for i in range(m)])
question=[tuple(map(int,input().split())) for j in range(q)]
dis={}
for i in range(1,n+1):
    for j in range(1,n+1):
        dis[(i,j)]=0
        for x,y in line[i-1:]:
            if i<=x and y<=j:
                dis[(i,j)] +=1

for i in question:
    print(dis[i])

### FIXED CODE ###

import numpy as np
N, M, Q = map(int, input().split())

#input
lst = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    L, R = map(int, input().split())
    lst[R][L] += 1

lst = np.array(lst)
# print (lst)

#2次元累積和
for i in range(1, N + 1):
    lst[:,i] += lst[:, i - 1]
for j in range(1, N + 1):
    lst[j,:] += lst[j - 1, :]


#output
for _ in range(Q):
    p, q = map(int, input().split())
    print (lst[q, q] - lst[p-1, q] - lst[q, p-1] + lst[p-1, p-1])

# print (lst)
### BUGGY CODE ###

N, Q = map(int, input().split())
AB = [None] * (N-1)
for i in range(N-1):
    a, b = map(int, input().split())
    AB[i] = (a, b)
PX = [None] * (Q)
for i in range(Q):
    p, x = map(int, input().split())
    PX[i] = (p, x)
    
edges = AB[:]
vals = PX[:]

from collections import defaultdict
graph = defaultdict(lambda: {})
for a, b in edges:
    graph[a][b] = 0
    graph[b][a] = 0
#print(graph)
    
vals_dict = defaultdict(lambda: 0)
for v, n in vals:
    vals_dict[v] += n
#print(vals_dict)

from collections import deque
q = deque([1])
visited = [None] * (N+1)
while q:
    v = q.popleft()
    visited[v] = True
    for t in graph[v]:
        if visited[t] == None:
            graph[v][t] = vals_dict[t]
            q.append(t)
#print(graph)
from heapq import heappush, heappop
def dijkstra(graph, start, N):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shortest = dijkstra(graph, 1, N)
shortest = [s+vals_dict[1] for s in shortest]
#print(shortest)
ans = ' '.join(map(str, shortest[1:]))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
AB = [None] * (N-1)
for i in range(N-1):
    a, b = map(int, input().split())
    AB[i] = (a, b)
PX = [None] * (Q)
for i in range(Q):
    p, x = map(int, input().split())
    PX[i] = (p, x)
    
edges = AB[:]
vals = PX[:]

from collections import defaultdict
vals_dict = defaultdict(lambda: 0)
for v, n in vals:
    vals_dict[v] += n
#print(vals_dict)

graph = defaultdict(lambda: {})
for a, b in edges:
    graph[a][b] = vals_dict[b]
    graph[b][a] = vals_dict[a]
#print(graph)
    

from heapq import heappush, heappop
def dijkstra(graph, start, N):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shortest = dijkstra(graph, 1, N)
shortest = [s+vals_dict[1] for s in shortest]
#print(shortest)
ans = ' '.join(map(str, shortest[1:]))
print(ans)
### BUGGY CODE ###

N,C=map(int, raw_input().split())
X=[ tuple( map(int, raw_input().split()) ) for i in range(N)]
T=[]
R=[]

a=[]

v_sum=0
for x,v in X:
	v_sum+=v
	T.append(v_sum-x)

a+=T

v_sum=0
for x,v in X[::-1]:
	v_sum+=v
	R.append(v_sum-(C-x))

a+=R

for i in range(N):
	extra_x=X[i][0]
	if len(R[:N-i-1])>0: val=T[i]+max(R[:N-i-1])-extra_x
	else: val=T[i]
	a.append(val)


for i in range(N):
	extra_x=C-X[N-i-1][0]
	if len(T[:N-i-1])>0: val=R[i]+max(T[:N-i-1])-extra_x
	else: val=R[i]
	a.append(val)


print max(0,max(a))

### FIXED CODE ###

N,C=map(int, raw_input().split())
X=[ tuple( map(int, raw_input().split()) ) for i in range(N)]
T=[]
R=[]

a=[]

v_sum=0
for x,v in X:
	v_sum+=v
	T.append(v_sum-x)

a+=T

v_sum=0
for x,v in X[::-1]:
	v_sum+=v
	R.append(v_sum-(C-x))

a+=R



T_MAX=[]
val=float("-inf")
for i in T:
	val=max(val,i)
	T_MAX.append(val)


R_MAX=[]
val=float("-inf")
for i in R:
	val=max(val,i)
	R_MAX.append(val)


for i in range(N):
	extra_x=X[i][0]
	if N-i-2>=0:
		val=T[i]+R_MAX[N-i-2]-extra_x
		a.append(val)


for i in range(N):
	extra_x=C-X[N-i-1][0]
	if N-i-2>=0:
		val=R[i]+T_MAX[N-i-2]-extra_x
		a.append(val)


print max(0,max(a))