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

def solve(n, g):
    mod = 10 ** 9 + 7

    dp = tuple([1] * 2 for _ in range(n))

    # dp[j][0/1] := 頂点jを0/1とする場合のjを親とする部分木の塗り方の状態数
    # dp[j][0] = reduce(mul, (dp[k][0] + dp[k][1] for k in g[j]))
    # dp[j][1] = reduce(mul, (dp[k][0] for k in g[j]))

    def dfs(v):
        checked[v] = True
        for u in g[v]:
            if checked[u]:
                continue
            dfs(u)
            dp[v][0] = dp[v][0] * (dp[u][0] + dp[u][1]) % mod
            dp[v][1] = dp[v][1] * dp[u][0] % mod

    checked = [False] * n
    checked[0] = True
    dfs(0)

    return sum(dp[0]) % mod


if __name__ == '__main__':
    import sys

    sys.setrecursionlimit(10 ** 7)

    input = sys.stdin.readline

    n = int(input())
    g = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        x, y = (int(j) - 1 for j in input().rstrip().split())
        g[x].add(y)
        g[y].add(x)
    print(solve(n, g))

# 適当な頂点を根とする


### FIXED CODE ###

def solve(n, g):
    mod = 10 ** 9 + 7

    def dfs(v):
        checked[v] = True

        w = 1
        b = 1
        for u in g[v]:
            if checked[u]:
                continue
            uw, ub = dfs(u)
            w = w * (uw + ub) % mod
            b = b * uw % mod
        return w, b

    stack = [0]
    order = []
    parent = [-1] * n
    checked = [False] * n
    checked[0] = True

    while stack:
        v = stack.pop()
        order.append(v)
        for u in g[v]:
            if checked[u]:
                continue
            checked[u] = True
            parent[u] = v
            stack.append(u)

    order.reverse()

    checked = [False] * n

    dp_w = [1] * n
    dp_b = [1] * n

    for v in order:
        checked[v] = True
        par = parent[v]
        if par == -1:
            continue
        dp_w[par] = (dp_w[par] * (dp_w[v] + dp_b[v])) % mod
        dp_b[par] = (dp_b[par] * dp_w[v]) % mod

    v = order[-1]
    return (dp_w[v] + dp_b[v]) % mod


if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

    n = int(input())
    g = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        x, y = (int(j) - 1 for j in input().rstrip().split())
        g[x].add(y)
        g[y].add(x)
    print(solve(n, g))

# 適当な頂点を根とする
# 2次元配列でdpするより、1次元*2本の方が若干速い
### BUGGY CODE ###

import fractions
from functools import reduce

def lcm_base(x, y):
  return (x * y) // fractions.gcd(x, y)

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

mod = 10 ** 9 + 7
n = int(input())
numList = list(map(int, input().split()))

# lcmTotal = 1
# for i in numList:
#   lcmTotal = lcm_base(lcmTotal, i)

lcmTotal = lcm_list(numList)

result = 0
for targetNum in numList:
  result += lcmTotal // targetNum % mod

print(result % mod)


### FIXED CODE ###

import fractions
from functools import reduce

def lcm_base(x, y):
  return (x * y) // fractions.gcd(x, y)

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

mod = 10 ** 9 + 7
n = int(input())
numList = list(map(int, input().split()))

# lcmTotal = 1
# for i in numList:
#   lcmTotal = lcm_base(lcmTotal, i)

lcmTotal = lcm_list(numList)

result = 0
for targetNum in numList:
  result += lcmTotal // targetNum

print(result % mod)
### BUGGY CODE ###

import numpy as np

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

L = np.array(sorted(L, reverse=True))

ans = 0

for n in range(0,N-2):
    for o in range(n+1,N-1):
        ans += np.sum(L[o+1:]>L[n]+-L[o])
                
print(int(ans))

### FIXED CODE ###

import bisect

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

count = 0
for n in range(N-2):
    for m in range(n+1,N-1):
        count += bisect.bisect_left(L,L[m]+L[n]) -m-1

print(count)
### BUGGY CODE ###

from collections import namedtuple

Ratio = namedtuple('Ratio', 'gold, silver copper')


def convert(n, Rfrm, Rto):
    Df = Ratio(*(t - f for f, t in zip(Rfrm, Rto)))

    ret = n

    g_max = n // Rfrm.gold if Df.gold > 0 else 0
    for g in range(g_max + 1):
        dg = Df.gold * g
        s_max = (n - Rfrm.gold * g) // Rfrm.silver if Df.silver > 0 else 0
        for s in range(s_max + 1):
            ds = Df.silver * s
            b = (n - Rfrm.gold * g - Rfrm.silver * s) // Rfrm.copper if Df.copper > 0 else 0

            db = Df.copper * b
            ret = max(ret, n + dg + ds + db)

    return ret


n = int(input())
Ra = Ratio(*map(int, input().split()))
Rb = Ratio(*map(int, input().split()))

ret = convert(n=n, Rfrm=Ra, Rto=Rb)
ret = convert(n=ret, Rfrm=Rb, Rto=Ra)
print(ret)


### FIXED CODE ###

N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())

# A : ドングリと金属に変える
# B : 全部ドングリに変える
# B : ドングリと金属に変える（無駄な操作でロスがないので、いったんドングリ化してよい）
# A : ドングリに変える

dp1 = list(range(N + 1))  # dp1[巣から持ってきたドングリ数] = 取引所 B で持てる最大ドングリ数
dp1[0] = 0
for i in range(N + 1):
    if i >= ga:
        dp1[i] = max(dp1[i], dp1[i - ga] + gb)
    if i >= sa:
        dp1[i] = max(dp1[i], dp1[i - sa] + sb)
    if i >= ba:
        dp1[i] = max(dp1[i], dp1[i - ba] + bb)

N = dp1[N]
dp2 = list(range(N + 1))  # dp2[取引所 B から持ってきたドングリ数] = 巣に持ち帰れる最大ドングリ数
for i in range(N + 1):
    if i >= gb:
        dp2[i] = max(dp2[i], dp2[i - gb] + ga)
    if i >= sb:
        dp2[i] = max(dp2[i], dp2[i - sb] + sa)
    if i >= bb:
        dp2[i] = max(dp2[i], dp2[i - bb] + ba)
print(dp2[N])
### BUGGY CODE ###

nkc=list(map(int, input().split()))
s=input()
n=nkc[0]
k=nkc[1]
c=nkc[2]
l=[]
r=[]
onum=sum(1 for i in range(len(s)) if s[i]=='o')
num=0
counter=0
while counter<k and num<n:
    #print(num)
    if s[num]=='o':
        l.append(num)
        counter+=1
        num+=c+1
    else:
        num+=1
num=n-1
counter=0
while counter<k and num>=0:
    #print(num)
    if s[num]=='o':
        r.insert(0,num)
        counter+=1
        num-=c+1
    else:
        num-=1
#print(l)
#print(r)
for i in range(min(len(r), len(l))):
    if r[i]==l[i]:
        print(r[i]+1)

### FIXED CODE ###

nkc=list(map(int, input().split()))
s=input()
n=nkc[0]
k=nkc[1]
c=nkc[2]
l=[]
r=[]
onum=sum(1 for i in range(len(s)) if s[i]=='o')
num=0
counter=0
while counter<k and num<n:
    #print(num)
    if s[num]=='o':
        l.append(num)
        counter+=1
        num+=c+1
    else:
        num+=1
num=n-1
counter=0
while counter<k and num>=0:
    #print(num)
    if s[num]=='o':
        r.append(num)
        counter+=1
        num-=c+1
    else:
        num-=1
#print(l)
#print(r)
lenr=len(r)
for i in range(min(lenr, len(l))):
    if r[lenr-i-1]==l[i]:
        print(l[i]+1)
### BUGGY CODE ###

k=int(input())
if k%2==0 or k%5==0:
  print(-1)
else:
  if k%7==0:
    k=k//7
  t=1
  tm=0
  for i in range(1,100000):
    tm=tm+t%k
    if tm==0:
      print(i)
      break
    else:
      t=t*10
  else:
    print(k-1)


### FIXED CODE ###

k=int(input())
if k%2==0 or k%5==0:
  print(-1)
else:
  t=7
  ans=1
  while True:
    if t%k==0:
      print(ans)
      break
    t=(t*10+7)%k
    ans=ans+1
### BUGGY CODE ###

n, k = map(int,input().split())
a_list = list(map(int,input().split()))
a_list.sort()

import math

def cmb(n,r):
    o = math.factorial(n)
    u = math.factorial(r)*math.factorial(n-r)
    return o//u

max_val = 0
min_val = 0
val = cmb(n-1, k-1)
for i in range(n-k+1):
    if i != 0:
        val = val*(n-i-k+1)//(n-i)
    max_val = int(max_val + (((a_list[-(i+1)])*val)))%(10**9+7)
    min_val = int(min_val + ((a_list[i])*val))%(10**9+7)


print(int((max_val-min_val)%(10**9+7)))

### FIXED CODE ###

n, k = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort()


mod = 10 ** 9 + 7
f_list = [1]
for i in range(1,n+1):
    f_list.append((f_list[-1] * i) % mod)
def comb(n,r):
    return f_list[n] * (pow(f_list[r], mod-2, mod) * pow(f_list[n-r], mod-2, mod) % mod) % mod


max_val = 0
min_val = 0
for i in range(n - k + 1):
    val = comb(n - i - 1, k - 1)
    max_val = (max_val + (((a_list[-(i + 1)]) * val))) % (10 ** 9 + 7)
    min_val = (min_val + ((a_list[i]) * val)) % (10 ** 9 + 7)

print(int((max_val - min_val) % (10 ** 9 + 7)))
### BUGGY CODE ###

N,T = map(int,input().split())
import copy
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
C = zip(A,B)
C = sorted(C)
A,B = zip(*C)
A = list(A)
B = list(B)
dp = [[0 for i in range(T)]for j in range(N+1)]
for i in range(1,N+1):
    a,b = A[i-1],B[i-1]
    for t in range(1,T):
        p = dp[i-1][t]
        if t >= a:
            q = dp[i-1][t-a] + b
            dp[i][t] = max(p,q)
        else:
            dp[i][t] = p
M = 0
for i in range(1,N+1):
    M = max(M,B[i-1]+dp[i-1][T-1])
print(M)

### FIXED CODE ###

N,T = map(int,input().split())
C = []
for i in range(N):
    a,b = map(int,input().split())
    C.append([a,b])
C.sort()
dp = [[0 for i in range(T)]for j in range(N+1)]
for i in range(1,N+1):
    a,b = C[i-1][0],C[i-1][1]
    for t in range(1,T):
        p = dp[i-1][t]
        if t >= a:
            q = dp[i-1][t-a] + b
            dp[i][t] = max(p,q)
        else:
            dp[i][t] = p
M = 0
for i in range(1,N+1):
    M = max(M,C[i-1][1]+dp[i-1][T-1])
print(M)
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
for _ in range(M):
    B, C = map(int, input().split())
    for _ in range(B):
        A_min = A[0]
        if A_min < C:
            heapq.heappop(A)
            heapq.heappush(A, C)
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B_C = []
for _ in range(M):
    B, C = map(int, input().split())
    B_C.append((C, B))
B_C = sorted(B_C, reverse=True)
Cs = []
rem = N
for c, b in B_C:
    if rem >= b:
        Cs += [c]*b
        rem -= b
    else:
        Cs += [c]*rem
        break
ans = sum(sorted(A+Cs, reverse=True)[:N])
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
N, W=map(int, input().split())
WV=[list(map(int, input().split())) for i in range(N)]
dp = [-1] * (W+1)
dp[0] = 0
for w, v in WV:
    for i in range(W, w-1, -1):
        if dp[i-w] == -1:
            continue
        dp[i] = max(dp[i], dp[i-w] + v)
print(max(dp))


### FIXED CODE ###

N, W=map(int, input().split())
WV=[list(map(int, input().split())) for i in range(N)]
dp = [-1] * (W+1)
dp[0] = 0
for w, v in WV:
    for i in range(W, w-1, -1):
        if dp[i-w] == -1:
            continue
        dp[i] = max(dp[i], dp[i-w] + v)
print(max(dp))
### BUGGY CODE ###

K, S = map(int, input().split())

success = 0

for x in range (K + 1):
    for y in range (K + 1):
        for z in range (K + 1):
            if x + y + z == S:
                success = success + 1

print(success)


### FIXED CODE ###

K, S = map(int, input().split())

success = 0

for x in range (K + 1):
    for y in range (K + 1):
        if S - x - y >= 0 and S - x - y <= K:
            success = success + 1

print(success)
### BUGGY CODE ###

s = input()
a = "*"
n = int(input())
kaitenn = 1

for i in range(n):
    q = input()
    if q[0] == "1":
        kaitenn *= -1
        a = a[::-1]
    else:
        if q[2] == "1":
            a = q[4] + a
        else:
            a = a + q[4]
            
print(a[:a.index("*")]+s[::kaitenn]+a[a.index("*")+1:])

### FIXED CODE ###

s = input()
n = int(input())
a = "*"
spin = 1

for i in range(n):
    q = input()
    if q[0] == "1":
        spin *= -1
        a = a[::-1]
    else:
        if q[2] == "1":
            a = q[4] + a
        else:
            a = a + q[4]
            
    if len(a) == 100:
        s = a[:a.index("*")] + s[::spin] + a[a.index("*")+1:]
        a = "*"
        spin = 1
            
print(a[:a.index("*")] + s[::spin] + a[a.index("*")+1:])
### BUGGY CODE ###

s = input()
q = int(input())
r = False#ひっくり返されたか
for i in range(q):
  t=list(input().split())
  if len(t) == 1:#一つしか入力されていない
    r = not(r)
  else:
    if (t[1] == '1' and r == False):
      s = t[2] + s
    elif (t[1] == '2' and r == True):
      s = t[2] + s
    else:
      s = s + t[2]
if r:
  print(s[::-1])
else:
  print(s)

### FIXED CODE ###

s = input()
q = int(input())
r = False#ひっくり返されたか
f = ''#in front of#逆転しているので最後に戻しましょう
b = '' #behind
for i in range(q):
  t=list(input().split())
  if len(t) == 1:#一つしか入力されていない
    r = not(r)
  else:
    if (t[1] == '1' and r == False):
      f += t[2]
    elif (t[1] == '2' and r == True):
      f += t[2]
    else:
      b += t[2]
s = f[::-1] + s + b
if r:
  print(s[::-1])
else:
  print(s)
### BUGGY CODE ###

from itertools import product

n, k = map(int, input().split())
p = [list(map(int, input().split())) for i in range(n)]
ans = float("inf")

for i, j, l, m in product(range(n), repeat=4):
    cnt = 0
    for g in range(n):
        if p[i][0] <= p[g][0] <= p[j][0] and p[l][1] <= p[g][1] <= p[m][1]:
            cnt += 1
    if cnt >= k:
        ans = min(ans, (p[j][0] - p[i][0]) * (p[m][1] - p[l][1]))
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
p = [list(map(int, input().split())) for i in range(n)]
ans = float("inf")

p.sort()
for i in range(n-k+1):
    for j in range(i+k-1, n):
        x = p[j][0] - p[i][0]
        yl = sorted(p[i:j+1],key=lambda x:x[1])
        for l in range(len(yl)-k+1):
            y = yl[l+k-1][1] - yl[l][1]
            ans = min(ans, y*x)
print(ans)
### BUGGY CODE ###

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

mod = 1000000007

f = [] # 素因数分解(指数部のみ)

for p in range(2, M): # 素因数分解
    e = 0
    while M%p == 0:
        e += 1
        M /= p
    
    if e>0:
        f.append(e)
    
    if M == 1:
        break

def pw(a, e):
    if e == 1:
        return a
    p = pw(a, e // 2)
    if e%2 == 1:
        return p * p % mod * a % mod
    else:
        return p * p % mod

# fact, inv の計算
fact = [1]
inv = [1]
for k in range(1, 100033):
    fact.append(fact[k-1] * k % mod)
    inv.append(pw(fact[k], mod-2))

def combine(n, k):
    return fact[n] * inv[k] % mod * inv[n-k] % mod

ans = 1
for e in f:
    ans *= combine(e+N-1, e) # N_H_e (重複組合せ)
    ans %= mod

print(ans)


### FIXED CODE ###

from collections import Counter

mod = 1000000007

# nの素因数分解

def prime(n):
    d = Counter()
    i = 2
    while i*i <= n:
        while n%i == 0:
            n //= i
            d[i] += 1
        i += 1
    if n > 1:
        d[n] += 1
    return d

# xのn乗を計算する
def mod_pow(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        half_x = mod_pow(x, n // 2)
        return half_x * half_x % mod
    else:
        return x * mod_pow(x, n-1) % mod

fact = [1] * 100100
inv = [1] * 100100
for k in range(1, 100100):
    fact[k] = fact[k-1] * k % mod
    inv[k] = mod_pow(fact[k], mod-2)

def nCr(n, r):
    return fact[n] * inv[r] % mod * inv[n-r] % mod

def solve():
    N, M = map(int, input().split())
    p = prime(M)
    s = 1
    for i in p.values():
        s *= nCr(i + N - 1, N - 1)
        s %= mod
    print(s)

solve()
### BUGGY CODE ###

n = int(input())
k = [int(a) for a in input().split()]
k_set = set(k)
all = 0

for b in k_set:
    tmp = k.count(b)
    all += tmp * (tmp - 1) // 2

for c in k:
    tmp = k.count(c)
    print(all - (tmp - 1))

### FIXED CODE ###

import collections

n = int(input())
k = [int(a) for a in input().split()]
k_set = set(k)
all = 0
count_dic = collections.Counter(k)

for b in k_set:
    tmp = count_dic[b]
    all += tmp * (tmp - 1) // 2

for c in k:
    tmp = count_dic[c]
    print(all - (tmp - 1))
### BUGGY CODE ###

N = int(input())
participants = sorted([ int(v) for v in input().split(" ") ], reverse=True)

# 1 2 4 5 5 5 7 8 9 
# 1 2 5 5 5 8

sum = 0
for i in range(N):
  #print(participants)
  c_max = participants.pop(0)
  n_max = participants.pop(0)
  c_min = participants.pop(-1)
  sum += n_max

print(sum)

### FIXED CODE ###

N = int(input())
participants = sorted([ int(v) for v in input().split(" ") ], reverse=True)

# 1 2 4 5 5 5 7 8 9 
# 1 2 5 5 5 8

sum = 0
for i in range(0, N):
  #print(participants)
  #c_max = participants.pop(0)
  #n_max = participants.pop(0)
  #c_min = participants.pop(-1)
  sum += participants[2*i+1]

print(sum)
### BUGGY CODE ###

import sys
from operator import itemgetter

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    n = int(input())
    l = [list(map(int, input().split())) for i in range(n)]
    limits = set([e[1] for e in l])

    is_possible = True
    for e in l:
        if sum([i[0] for i in l if i[1] <= e[1]]) > e[1]:
            is_possible = False
            break

    print("Yes" if is_possible else "No")


### FIXED CODE ###

import sys
from operator import itemgetter

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    n = int(input())
    l = [list(map(int, input().split())) for i in range(n)]
    l.sort(key=itemgetter(1))

    is_possible = True
    sum = 0
    for e in l:
        sum += e[0]
        if sum > e[1]:
            is_possible = False
            break

    print("Yes" if is_possible else "No")
### BUGGY CODE ###

import sys
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    H, W = read_values()
    F = [input().strip() for _ in range(H)]
    A = [False] * (H * W)
    Q = queue.Queue()

    for h in range(H):
        for w in range(W):
            if F[h][w] == "#":
                Q.put((h, w, 0))
                A[h * W + w] = True

    res = V(max)
    while not Q.empty():
        h, w, d = Q.get()
        res.ud(d)

        for hh, ww in ((h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)):
            if 0 <= hh < H and 0 <= ww < W:
                if A[hh * W + ww]:
                    continue
                Q.put((hh, ww, d + 1))
                A[hh * W + ww] = True
    
    print(res)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    H, W = read_values()
    F = [input().strip() for _ in range(H)]
    A = [False] * (H * W)
    Q = deque() 

    for h in range(H):
        for w in range(W):
            if F[h][w] == "#":
                Q.append((h, w, 0))
                A[h * W + w] = True

    res = V(max)
    while Q:
        h, w, d = Q.popleft()
        res.ud(d)

        for hh, ww in ((h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)):
            if 0 <= hh < H and 0 <= ww < W:
                if A[hh * W + ww]:
                    continue
                Q.append((hh, ww, d + 1))
                A[hh * W + ww] = True
    
    print(res)


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

def resolve():
    '''
    code here
    '''

    N, M, K = [int(item) for item in input().split()]
    As = [int(item) for item in input().split()]
    Bs = [int(item) for item in input().split()]

    res = 0
    time = 0

    memo_A = [0]
    for i in range(N):
        memo_A.append(As[i]+memo_A[-1])

    memo_B = [0]
    for i in range(M):
        memo_B.append(Bs[i]+memo_B[-1])

    res = 0
    for i, av in enumerate(memo_A):
        if av > K:
            break
        else:
            for j , bv in enumerate(memo_B):
                if bv + av  <= K:
                    res = max(res, i+j)
            
    print(res)

if __name__ == "__main__":
    resolve()
            


### FIXED CODE ###

def resolve():
    '''
    code here
    '''

    N, M, K = [int(item) for item in input().split()]
    As = [int(item) for item in input().split()]
    Bs = [int(item) for item in input().split()]

    res = 0
    time = 0

    memo_A = [0]
    for i in range(N):
        memo_A.append(As[i]+memo_A[-1])

    memo_B = [0]
    for i in range(M):
        memo_B.append(Bs[i]+memo_B[-1])

    res = 0
    j = M
    for i, av in enumerate(memo_A):
        if av > K:
            break
        else:
            
            while av + memo_B[j] > K:
                j -= 1
            res = max(res,j+i)

    print(res)

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

import sys
input = sys.stdin.readline

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

end=[[] for i in range(N+2)]

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

seg_el_list=[]
i=seg_el-1
while i>=0:
    seg_el_list.append(i)
    i=(i-1)//2

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        ADD[k]+=x#そのノードのADD値を更新
        return
    
    updates(a,b,x,k*2+1,l,(l+r)>>1)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    updates(a,b,x,k*2+2,(l+r)>>1,r)

    SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def update_solo(n,x):#A[n]=xに更新（反映）
    i=n+seg_el-1
    SEG[i]=x
    i=(i-1)//2
    
    while i>=min_seg_el:
        SEG[i]=max(SEG[i*2+1]+ADD[i*2+1],SEG[i*2+2]+ADD[i*2+2])
        i=(i-1)//2

for i in range(1,N+2):
    i_bit=i.bit_length()
    min_seg_el=seg_el_list[i_bit]

    for b,x in end[i]:
        updates(b,i,x,min_seg_el,0,1<<i_bit)#点数がもらえる区間から出たときにその分を加算

    update_solo(i,SEG[min_seg_el]+ADD[min_seg_el])#[0,i)の最大値はSEG[0]+ADD[0]と一致するはず

print(SEG[min_seg_el]+ADD[min_seg_el])


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

end=[[] for i in range(N+2)]

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値
seg_el_list=[524286, 262142, 131070, 65534, 32766, 16382, 8190, 4094, 2046, 1022, 510, 254, 126, 62, 30, 14, 6, 2, 0]

def update(k):#SEGのkより上のノードを更新（反映）
    while k>=0:
        k=(k-1)//2
        if SEG[k]==max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2]):
            break
        SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def to_seg(a):#aが終点となる区間をSegment treeの座標へ変換  
    b=(a&(-a)).bit_length()
    return seg_el_list[b]+a//(1<<(b-1))

def add(a,b,x):#区間(a,b]にxを加算
    #print(a,b,x)
    while b!=0:
        ADD[to_seg(b)]+=x
        update(to_seg(b))
        b-=(b&(-b))

    while a!=0:
        ADD[to_seg(a)]+=-x
        update(to_seg(a))
        a-=(a&(-a))
    
for i in range(N+2):
    for b,k in end[i]:
        add(b,i,k)#点数がもらえる区間から出たときにその分を加算

    SEG[i+seg_el-1]=SEG[0]
    update(i+seg_el-1)

print(SEG[0])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)

def f(i):
    if memo[i] != float("Inf"):return memo[i]

    for j in range(1,k+1):
        if i - j >= 0:
            memo[i] = min(memo[i],f(i-j)+abs(ary[i-j]-ary[i]))
    return memo[i]
n,k = map(int,input().split())
ary = list(map(int,input().split()))
memo = [float("Inf") for _ in range(n)]
memo[0] = 0
print(f(n-1))

### FIXED CODE ###

import numpy as np

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

h = np.array(h)
dp = np.zeros(n, dtype=int)

for i in range(1,n):
    m = max(0,i-k)
    dp[i] = min(dp[m:i] + np.abs(h[i] - h[m:i]))
print(dp[n-1])