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

# グラフわからんのでグラフアルゴリズム忘れた
# dfsでやる 限度2回

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)


def dfs(t, c, used):
    if c != 0 and t == n - 1:
        return True
    if c == 0:
        return False
    flag = False
    for g in graph[t]:
        if g in used:
            continue
        next_used = used[:]
        next_used.append(g)
        flag = dfs(g, c - 1, next_used)
        if flag:
            break
    return flag


for x in graph[0]:
    if dfs(x, 2, [x]):
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")


### FIXED CODE ###

# グラフわからんのでグラフアルゴリズム忘れた
# dfsでやる 限度2回c
# なんかしらんけどdfsが2TLEになるので諦めた それぞれの島について1とNがあれば良い

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

for g in graph[1 : n - 1]:
    c = 0
    for v in g:
        if c >= 2:
            break
        if v == 0 or v == n - 1:
            c += 1
    if c == 2:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

import fractions
total = 0
K = int(input())
for i in range(1, K+1):
    for j in range(1, K+1):
        ans2 = fractions.gcd(i, j)
        for k in range(1, K+1):
            ans3 = fractions.gcd(ans2, k)
            #print(i, j, k, ans3)
            total += ans3
print(total)

### FIXED CODE ###

import math
total = 0
K = int(input())
for i in range(1, K+1):
    for j in range(1, K+1):
        ans2 = math.gcd(i, j)
        for k in range(1, K+1):
            ans3 = math.gcd(ans2, k)
            #print(i, j, k, ans3)
            total += ans3
print(total)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

cnt = 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) // b >= 0:
            cnt += 1

print(cnt)

### FIXED CODE ###

r, g, b, n = map(int, input().split())

cnt = 0
for i in range(3001):
    for j in range(3001):
        if (n-i*r-j*g) % b == 0 and (n-i*r-j*g) // b >= 0:
            cnt += 1

print(cnt)
### BUGGY CODE ###

h, w = map(int, input().split())
ls = [input().strip() for _ in range(h)]
xs = [[-1] * w for _ in range(h)]
ys = [[-1] * w for _ in range(h)]
for y in range(h):
    for x in range(w):
        if xs[y][x] >= 0 and ys[y][x] >= 0:
            continue
        if ls[y][x] == '#':
            xs[y][x] = 0
            ys[y][x] = 0
        if xs[y][x] == -1:
            count = 0
            while x + count < w:
                c2 = ls[y][x + count]
                if c2 == '.':
                    count += 1
                else:
                    break
            for i in range(count):
                xs[y][x + i] = count
        if ys[y][x] == -1:
            count = 0
            while y + count < h:
                c2 = ls[y + count][x]
                if c2 == '.':
                    count += 1
                else:
                    break
            for i in range(count):
                ys[y + i][x] = count
res = 0
for y in range(h):
    for x in range(w):
        res = max(res, xs[y][x] + ys[y][x] - 1)
print(res)

### FIXED CODE ###

h, w = map(int, input().split())
ls = [input().strip() for _ in range(h)]
counts = [[[-1] * w for _ in range(h)] for _ in range(4)]

for y in range(h):
    for x in range(w):
        if ls[y][x] == '#':
            counts[0][y][x] = 0
        else:
            if x == 0:
                counts[0][y][x] = 1
            else:
                counts[0][y][x] = counts[0][y][x - 1] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[1][yy][xx] = 0
        else:
            if x == 0:
                counts[1][yy][xx] = 1
            else:
                counts[1][yy][xx] = counts[1][yy][xx + 1] + 1

        if ls[y][x] == '#':
            counts[2][y][x] = 0
        else:
            if y == 0:
                counts[2][y][x] = 1
            else:
                counts[2][y][x] = counts[2][y - 1][x] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[3][yy][xx] = 0
        else:
            if y == 0:
                counts[3][yy][xx] = 1
            else:
                counts[3][yy][xx] = counts[3][yy + 1][xx] + 1

res = 0
for y in range(h):
    for x in range(w):
        val = -3
        for i in range(4):
            val += counts[i][y][x]
        res = max(res, val)

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

N = int(input())
l = [-1] * N

def get(v1, v2):
    print(v1)
    s = input()
    if s=="Male":
        l[v1] = 0
    elif s=="Female":
        l[v1] = 1
    else:
        print(v1)
        return -1

    print(v2)
    s = input()
    if s=="Male":
        l[v2] = 0
    elif s=="Female":
        l[v2] = 1
    else:
        print(v2)
        return -1
    
    return l[v2]==l[v1]


left, right = 0, N-1
while 1:
    mid = (left+right)//2
    v = get(left, mid)
    if v==-1:
        exit()
    elif v==True and (mid-left)%2:
        right = m
    else:
        left = m

### FIXED CODE ###

N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    exit(0)

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    exit(0)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        exit(0)

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        left, right = left, mid
    else:
        left, right = mid, right
### BUGGY CODE ###

import sys

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

def main():
    K = int(input())
    S = input()

    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0

    fact =[1]*(K+n)
    factinv = [1]*(K+n)
    inv = [0,1]


    for i in range(2,K+n):
        fact[i] = (fact[i-1] * i) % mod
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv[i] = (factinv[i-1] * inv[i]) % mod

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

    for i in range(K+1):
        ans += ((25 ** i * nCr(i+n-1,n-1)) * (26 ** (K - i))) % mod
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

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

def main():
    K = int(input())
    S = input()

    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0

    fact =[1]*(K+n)
    factinv = [1]*(K+n)
    inv = [0,1]


    for i in range(2,K+n):
        fact[i] = (fact[i-1] * i) % mod
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv[i] = (factinv[i-1] * inv[i]) % mod

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

    for i in range(K+1):
        tmp = pow(25,i,mod)
        tmp *= nCr(i+n-1,n-1)
        tmp *= pow(26,K-i,mod)
        ans += tmp
        ans %= mod
    print(ans)

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

n=int(input())
l=[]
for _ in range(n):
    a = int(input())
    if a in l:
        l.remove(a)
    else:
        l.append(a)
print(len(l))

### FIXED CODE ###

import collections
n=int(input())
a=[int(input()) for _ in range(n)]
ca = collections.Counter(a)
cak = list(ca.values())
res = [i for i in cak if i % 2 ==1]
print(len(res))
### BUGGY CODE ###

from collections import deque
H, W = [int(i) for i in input().split()]
A = [list(input()) for _ in range(H)]

Q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            Q.append((i, j, 0))

ans = 0
while Q:
    i, j, dist = Q.popleft()
    ans = max(ans, dist)
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "#"
            Q.append((ni, nj, dist + 1))

print(ans)


### FIXED CODE ###

from collections import deque
H, W = [int(i) for i in input().split()]
A = [list(input()) for _ in range(H)]

Q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            Q.append((i, j, 0))

ans = 0
while Q:
    i, j, dist = Q.popleft()
    ans = max(ans, dist)
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "#"
            Q.append((ni, nj, dist + 1))

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

import heapq
import sys
input = sys.stdin.readline

def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    重み付きグラフgraphは隣接リストで与えられる
    計算量: O(|E|log|V|)
    """
    INF = float("inf")
    n = len(graph)
    distance = [INF] * n
    distance[start] = 0
    q = [(start, 0)]  #q = [(現在地, startからの距離)]
    while q:
        pos, dist = heapq.heappop(q)
        if distance[pos] < dist:
            continue
        for next_pos, cost in graph[pos]:
            if distance[pos] + cost < distance[next_pos]:
                distance[next_pos] = distance[pos] + cost
                heapq.heappush(q, (next_pos, distance[next_pos]))
    return distance


n, m, s, t = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

y_graph = [[] for i in range(n)]
s_graph = [[] for i in range(n)]
for u, v, a, b in info:
    u -= 1
    v -= 1
    y_graph[u].append((v, a))
    y_graph[v].append((u, a))
    s_graph[u].append((v, b))
    s_graph[v].append((u, b))

s -= 1
t -= 1
y_cost = dijkstra(s, y_graph)
s_cost = dijkstra(t, s_graph)

ans = [0]*n
for i in range(n):
    ans[i] = y_cost[i] + s_cost[i]

for i in range(n-1)[::-1]:
    ans[i] = min(ans[i], ans[i+1])

for num in ans:
    print(10**15 - num)

### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    重み付きグラフgraphは隣接リストで与えられる
    計算量: O(|E|log|V|)
    """
    INF = float("inf")
    n = len(graph)
    distance = [INF] * n
    distance[start] = 0
    q = [(0, start)]  #q = [(startからの距離, 現在地)]
    while q:
        dist, pos = heapq.heappop(q)
        if distance[pos] < dist:
            continue
        for next_pos, cost in graph[pos]:
            if distance[pos] + cost < distance[next_pos]:
                distance[next_pos] = distance[pos] + cost
                heapq.heappush(q, (distance[next_pos], next_pos))
    return distance


n, m, s, t = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

y_graph = [[] for i in range(n)]
s_graph = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = info[i]
    u -= 1
    v -= 1
    y_graph[u].append((v, a))
    y_graph[v].append((u, a))
    s_graph[u].append((v, b))
    s_graph[v].append((u, b))

s -= 1
t -= 1
y_cost = dijkstra(s, y_graph)
s_cost = dijkstra(t, s_graph)

ans = [0]*n
for i in range(n):
    ans[i] = y_cost[i] + s_cost[i]

for i in range(n-1)[::-1]:
    ans[i] = min(ans[i], ans[i+1])

for num in ans:
    print(10**15 - num)
### BUGGY CODE ###

def main():
    N = int(input())
    A = []
    for n in range(N):
        A.append(int(input()))

    max1_A = max(A)
    A_cp = sorted(A)
    A_cp.pop(-1)
    max2_A = max(A_cp)
    argmax_A = [i for i, x in enumerate(A) if x == max(A)]

    for a in A:
        if a == max1_A:
            print(max2_A)
        else:
            print(max1_A)
            
        
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    A = []
    for n in range(N):
        A.append(int(input()))

    A_cp = sorted(A)
    max1_A = A_cp.pop(-1)
    max2_A = max(A_cp)
    for a in A:
        if a == max1_A:
            print(max2_A)
        else:
            print(max1_A)
            
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
k = [int(i) for i in input().split()]
pair = {}

for i in range(n):
    pair.setdefault(k[i], []).append(i)

for i in range(n):
    ans = 0
    for value in pair.values():
        l = len(value)-1 if i in value else len(value)
        ans += l*(l-1)//2
    print(ans)

### FIXED CODE ###

n = int(input())
k = [int(i) for i in input().split()]
pair = {}

for i in range(n):
    pair.setdefault(k[i], []).append(i)

sum = 0
for value in pair.values():
    l = len(value)
    sum += l*(l-1)//2

for i in range(n):
    len_pair = len(pair[k[i]])
    if len_pair != 1:
        ans = sum - ((len_pair*(len_pair-1)//2)-((len_pair-1)*(len_pair-2)//2))
        print(ans)
    else:
        print(sum)
### BUGGY CODE ###

import math
import bisect
import copy

n = int(input())

list1 = list(map(int,input().split()))
list1.sort()
cout = 0
m,k = 0,0
for i in range(n-2):
	o = list1.pop(0)
	list1_c = copy.deepcopy(list1) #ここでjのためのdeepcopyを更新
	for j in range(len(list1)):
		p = list1_c.pop(0)

		a = abs(o-p) +1
		b = o+p -1 #<= ではなく<条件に揃える

		c = bisect.bisect_left(list1_c,a)
		d = bisect.bisect_right(list1_c,b)

		if c < d:
			cout += d-c

print(cout)

### FIXED CODE ###

import bisect
import copy

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

cout = 0
m,k = 0,0

for i in range(n-2):
	o = list1.pop(0)
	for j in range(n-i-1):
		p = list1[j]

		a = abs(o-p) +1
		b = o+p -1 #<= ではなく<条件に揃える

		d = bisect.bisect_right(list1[j+1:],b)
		
		cout += d

print(cout)
### BUGGY CODE ###

N = int(input())
S = []
ans = 0
for i in range(N):
    tmp = input()
    if not tmp in S:
        S.append(tmp)
        ans += 1
print(ans)


### FIXED CODE ###

import numpy as np
N = int(input())
S = [0] * N
ans = 0
for i in range(N):
    S[i] = input()
print(len(np.unique(S)))
### BUGGY CODE ###


n=int(input())

arr=[0]*(n+1)

for i in range(1,n+1):
	for j in range(i,n+1,i):
		arr[j]+=1
	
ans=0
for i in range(1,n+1):
	ans+=(i)*arr[i]


print(ans)


### FIXED CODE ###


n= int(input())
 
ans = 0
for i in range(1, n + 1):
    x = n // i
    ans += x * (x + 1) * i // 2
 
print(ans)
### BUGGY CODE ###

import itertools


flatten_iter = itertools.chain.from_iterable
def factors(n):
    return set(flatten_iter((i, n//i) 
                for i in range(1, int(n**0.5)+1) if n % i == 0))

line = int(input())


line = input()
numbers = [int(n) for n in line.split()]

num_factors = [factors(num) for num in numbers]
factors_pairs = []
for i in range(len(numbers)):
    common_factors = None
    for dividends in num_factors[:i] + num_factors[i+1:]:
        if not common_factors:
            common_factors = dividends
        else:
            common_factors = common_factors.intersection(dividends)
    factors_pairs.append(max(common_factors))
predicted_value = max(factors_pairs)

print(predicted_value)

### FIXED CODE ###

from fractions import gcd

X = int(input())

line = input()
numbers = [int(n) for n in line.split()]

left_list = [0]*(X+1)
right_list = [0]*(X+1)
for i in range(X):
    left_list[i+1] = gcd(left_list[i], numbers[i])
    right_list[X-1-i] = gcd(right_list[X-i], numbers[X-1-i])
predicted_value = max([gcd(left_list[i], right_list[i+1]) for i in range(X)])

print(predicted_value)
### BUGGY CODE ###

def f(num):
    ans=0
    for x in range(1,100):
        for y in range(1,100):
            for z in range(1,100):
                if x==y==z and x**2+y**2+z**2+x*y+y*z+z*x==num:
                    ans+=1
                    return ans
                elif x**2+y**2+z**2+x*y+y*z+z*x==num:
                    ans+=3
                    return ans
    return ans

N=int(input())
for i in range(N):
    print(f(i+1))

### FIXED CODE ###

N=int(input())
ans=[0 for _ in range(10050)]
for x in range(1,105):
    for y in range(1,105):
        for z in range(1,105):
            v=x**2+y**2+z**2+x*y+y*z+z*x
            if v<10050:
                ans[v]+=1

for i in range(N):
    print(ans[i+1])
### BUGGY CODE ###

import bisect
N = int(input())
A = []
for n in range(N):
    A.append(int(input()))
A = A[::-1]
INF = int(1e+9 + 10)
lis = [INF]* (N+1)
lis[-1] = -1
for n in range(N):
    i = bisect.bisect(lis[::-1], A[n])    
    lis[N-i] = A[n]
print (bisect.bisect_left(lis[::-1], INF) - 1)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
N = int(input())
A = []
for n in range(N):
    A.append(int(input()))
A = A[::-1]
INF = int(1e+9 + 10)
lis = [INF]* (N+1)
lis[0] = -1
for n in range(N):
    i = bisect.bisect(lis, A[n])    
    lis[i] = A[n]
print (bisect.bisect_left(lis, INF) - 1)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,q = inpl()
g = [[0]*n for _ in range(n)]
for _ in range(m):
    l,r = inpl()
    l,r = l-1, r-1
    g[l][r] += 1
for _ in range(q):
    a,b = inpl()
    a,b = a-1,b-1
    cnt = 0
    for i in range(a,b+1):
        for j in range(i,b+1):
            cnt += g[i][j] 
    print(cnt)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m,q = inpl()
lr = [inpl() for i in range(m)]
st = [inpl() for i in range(q)]
cnt = [[0 for j in range(n)] for i in range(n)]

for i in lr:
    a,b = i
    cnt[a-1][b-1] += 1
for i in range(n):
    for j in range(i,n-1):
        cnt[i][j+1] += cnt[i][j]
# pprint.pprint(cnt)
for i in st:
    cc = 0
    a,b = i
    for _ in range(a-1,b):
        cc += cnt[_][b-1]
    print(cc)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())

A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = map(int, input().split())

C = deque()

while len(C) < M:
    for j in range(B[A.index(min(A))]):
        C.append(min(A))
    B.pop(A.index(min(A)))
    A.remove(min(A))

C = sorted(C)
print(sum(C[:M]))

### FIXED CODE ###

import sys
from collections import deque
from operator import itemgetter
input = sys.stdin.readline
N, M = map(int, input().split())

A = deque()
for i in range(N):
    A.append(list(map(int, input().split())))

A = sorted(A, key=itemgetter(0))

m=0
cost=0

for i in range(N):
    if m >= M:
        break
    buy = min(M - m, A[i][1])
    cost += A[i][0] * buy
    m += buy

print(cost)
### BUGGY CODE ###

MOD = 10**9+7
N, M = map(int, input().split())
broken = [int(input())for _ in range(M)]

dp = [0 for _ in range(N+2)]
dp[N+1] = 0
dp[N] = 1

for i in reversed(range(N)):
    if i not in broken:
        dp[i] = dp[i+1] + dp[i+2]
        dp[i] %= MOD
        
print(dp[0])


### FIXED CODE ###

N, B = map(int, input().split())
ana = []
dp = [0] * (N+2)

for i in range(B):
    ana.append(int(input()))

mod = 1000000007

dp[N] = 1
for i in reversed(range(N)):
    if len(ana) >= 1 and i == ana[-1]:
        dp[i] = 0
        if len(ana) != 0:
            ana.pop(-1)
        continue
    dp[i] = dp[i + 1] + dp[i + 2]
print(dp[0] % mod)
### BUGGY CODE ###

lines =  input().split()
n = int(lines[0])
m = int(lines[1])

py = []
od = [[]*1 for i in range(n)]

for i in range(0,m):

    lines =  input().split()
    p = int(lines[0])
    y = int(lines[1])
    py.append([p,y])     
    od[p-1].append(y)

for o in od :
    o.sort()

for i in range(0,m):
    py0 = py[i][0] 
    r = od[py0-1].index(py[i][1])

    tmp = py0
    digit = 0
    while tmp > 0 :        
        digit += 1
        tmp = tmp // 10
    
    l = 6-digit
    for j in range(l):
        print('0',end="")
    print(py0,end="")

    tmp = r + 1
    digit = 0
    while tmp > 0 :        
        digit += 1
        tmp = r // 10

    l = 6-digit
    for j in range(l):
        print('0',end="")
    print(r+1)

### FIXED CODE ###

import sys as sys

lines =  input().split()
n = int(lines[0])
m = int(lines[1])

py = []
od = {}

#lines = sys.stdin.readlines()

for i in range(0,m):


    #l =  lines[i].split()
    l = input().split()
    p = int(l[0])
    y = int(l[1])
    
    if p in od :
        od[p].append([i,y])
    else:
        od[p] = [[i,y]]

a = []
for p in od.keys():
    od[p].sort(key=lambda x:x[1])
    r = 1

    for o in od[p]:
        cs = ""

        tmp = p
        digit = 0
        while tmp > 0 :        
            digit += 1
            tmp = tmp // 10
        
        l = 6-digit
        for j in range(l):
            cs += '0'
        cs += str(p)

        tmp = r 
        digit = 0
        while tmp > 0 :        
            digit += 1
            tmp = tmp // 10

        l = 6-digit
        for j in range(l):
            cs += '0'
        cs += str(r)        

        a.append([o[0],cs])
        r += 1

a.sort(key=lambda x:x[0])
for aa in a:
    print(aa[1])
### BUGGY CODE ###

N,K = map(int,input().split())
H = [0] + list(map(int,input().split()))

INF = float('inf')
dp = [[INF]*(N-K+1) for _ in range(N+1)]
dp[0][0] = 0

for i,h in enumerate(H):
    if i==0: continue
    for j in range(N-K,0,-1):
        for k in range(i):
            c = max(0, h - H[k])
            dp[i][j] = min(dp[i][j], dp[k][j-1] + c)
print(min(row[-1] for row in dp))

### FIXED CODE ###

N,K = map(int,input().split())
H = [0] + list(map(int,input().split()))

INF = float('inf')
dp = [[INF]*(N-K+1) for _ in range(N+1)]
dp[0][0] = 0

for i,h in enumerate(H):
    if i==0: continue
    for j in range(N-K,0,-1):
        for k in range(i):
            c = max(0, h - H[k])
            dp[i][j] = min(dp[i][j], dp[k][j-1] + c)
print(min(row[-1] for row in dp))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**5 + 1)

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

for _ in range(n-1):
    x,y,z = map(int, input().split())
    if z % 2 == 0:
        ge[x-1].append(y-1)
        ge[y-1].append(x-1)
    else:
        go[x-1].append(y-1)
        go[y-1].append(x-1)

color = [0] * n

def dfs(v, c):
    color[v] = c
    for i in range(len(go[v])):
        if color[go[v][i]] == 0:
            dfs(go[v][i], -c)
    for i in range(len(ge[v])):
        if color[ge[v][i]] == 0:
            dfs(ge[v][i], c)

dfs(0, 1)

for i in range(n):
    if color[i] == -1:
        print(0)
    else:
        print(1)

### FIXED CODE ###

import queue

n = int(input())
go = [[]for _ in range(n)]
ge = [[]for _ in range(n)]
 
for _ in range(n-1):
    x,y,z = map(int, input().split())
    if z % 2 == 0:
        ge[x-1].append(y-1)
        ge[y-1].append(x-1)
    else:
        go[x-1].append(y-1)
        go[y-1].append(x-1)

color = [0] * n
color[0] = 1

q = queue.Queue()

q.put(0)

while not q.empty():
    v = q.get()
    for i in range(len(go[v])):
        if color[go[v][i]] == 0:
            color[go[v][i]] = - color[v]
            q.put(go[v][i])
    for i in range(len(ge[v])):
        if color[ge[v][i]] == 0:
            color[ge[v][i]] = color[v]
            q.put(ge[v][i])

for i in range(n):
    if color[i] == -1:
        print(0)
    else:
        print(1)