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

import sys
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
cost = []
res = []
tree = []
level = []
childs = []
parent = []
cache = []
for i in range(210000):
    res.append(0)
    tree.append([])
    level.append(-1)
    childs.append([])
    parent.append(-1)
    cost.append(0)
    cache.append(-1)

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

for loop in range(q):
    p, x = map(int, input().split())
    cost[p] += x

def make_level(index, lev, pp):
    l = 0
    level[index] = lev
    parent[index] = pp
    for next in tree[index]:
        #print("index {0} search {1}".format(index, next))
        # 逆走はしない
        if level[next] != -1:
            #print("CANNOT MOVE to {0}".format(next))
            continue
        # 子供に親を設定
        parent[next] = index
        cost[next] += cost[index]
        curparent = index
        make_level(next, lev + 1, index)

make_level(1, 0, -1)

res = list(map(str, cost))
print(" ".join(res[1:n+1]))

### FIXED CODE ###

edge = []
n, q = map(int, input().split())
for _ in range(n+100):
    edge.append([])
for _ in range(n-1):
    a,b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)
res = [0] * (n+1)
cost = [0] * (n+1)
for _ in range(q):
    a,b = map(int, input().split())
    res[a] += b

import collections
q = collections.deque([[1, 0]])
used = [False] * (n+1)
while len(q) > 0:
    #print(q)
    curnode, cost = q.popleft()
    res[curnode] += cost
    used[curnode] = True
    for i in range(len(edge[curnode])):
        nnext = edge[curnode][i]
        if used[nnext] is True:
            continue
        else:
            q.append([nnext, res[curnode]])
res=res[1:]
print(" ".join(list(map(str, res))))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
S = raw_input()
T = ""
t = ['dream','dreamer','erase','eraser']
def rec(T,S):
    if len(S) < len(T):
        return False
    if S==T:
        return True
    elif S[len(T)] == "e":
        return rec(T+t[2],S) or rec(T+t[3],S)
    elif S[len(T)] == "d":
        return rec(T+t[0],S) or rec(T+t[1],S)
    else:
        return False
if rec(T,S):
    print "YES"
else:
    print "NO"


### FIXED CODE ###

S = raw_input().split()[0]
t = ['dreameraser','dreamerase','dreamer','dream','eraser','erase']
while len(S) > 0:
    for i in t:
        if S[-len(i):]==i:
            S = S[:-len(i)]
            break
        elif i == t[-1]:
            print "NO"
            exit()
print "YES"
### BUGGY CODE ###

def main():
    s = list(str(input()))
    s.reverse()
    s = [int(c) for c in s]
    s += [0]
    m = len(s)
 
    dp = [[10**7, 10**7] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり
 
    dp[0][0] = 0
 
    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            if dp[i+1][0] >= dp[i][j]+nd:
                dp[i+1][0] = dp[i][j]+nd
            if dp[i+1][1] >= dp[i][j]+10-nd:
                dp[i+1][1] = dp[i][j]+10-nd
    #print(dp)
    print(dp[m][0])
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    s = list(str(input()))
    s.reverse()
    for i in range(len(s)):
        s[i] = int(s[i])
    s += [0]
    m = len(s)

    dp = [[10**7, 10**7] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり

    dp[0][0] = 0

    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            if dp[i+1][0] >= dp[i][j]+nd:
                dp[i+1][0] = dp[i][j]+nd
            if dp[i+1][1] >= dp[i][j]+10-nd:
                dp[i+1][1] = dp[i][j]+10-nd
    #print(dp)
    print(dp[m][0])

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

import sys
input = sys.stdin.readline
import bisect

n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
for i in range(n):
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d,i,n)
        for j in range(q-i):
            if x[i+j][1]<=0:
                continue
            else:
                x[i+j][1]-=w
    else:
        continue

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
import collections
from collections import deque
n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
# 累積ダメージを管理
qq=deque([])
ans=0
atk=0
for i in range(n):
    w=x[i][1]
    # iがダメージの有効期限を超過している場合
    while len(qq)>0 and i > qq[0][0]:
        atk-=qq[0][1]
        qq.popleft()

    if w-atk>0:
        ans+=w-atk
        q=bisect.bisect_right(y,x[i][0]+2*d)-1
        # 有効期限　ダメージ
        qq.append([q,w-atk])
        atk += w - atk
print(ans)
### BUGGY CODE ###

def main():
    n = 13
    mod = 1000000007
    r = 5

    s_list = list(reversed(input()))

    amari_list = amari(n)
    amari_len = len(amari_list)

    ans_list = initial(s_list[0], n)

    for i, s in enumerate(s_list):
        if i == 0:
            continue
        if s == "?":
            tmp_list, ans_list = ans_list, [0]*n
            for j in range(10):
                t = j * amari_list[i % amari_len] % n
                ans_list = add(ans_list, shift(t, tmp_list))
                ans_list = list(map(lambda x: x % mod, ans_list))
        else:
            t = int(s) * amari_list[i % amari_len] % n
            ans_list = shift(t, ans_list)

    print(ans_list[r] % mod)


def shift(r, ans_list):
    l = len(ans_list)
    return [ans_list[(i + l - r) % l] for i in range(l)]


def add(list1, list2):
    return list(map(sum, zip(list1, list2)))


def initial(s, n):
    if s == "?":
        return [1 if i < 10 else 0 for i in range(n)]
    else:
        return [1 if i == int(s) else 0 for i in range(n)]


def amari(n):
    ret = []
    for i in range(n+1):
        r = (10**i) % n
        if r in ret:
            return ret
        else:
            ret.append(r)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np


def main():
    n = 13
    mod = 1000000007
    r = 5
    in_str = input()

    amari_l = amari_list(n)
    amari_m = amari_matrix(n, amari_l)

    ans_list = initial(in_str[-1:], n)

    for i, s in enumerate(reversed(in_str)):
        if i == 0:
            continue
        if s == "?":
            ans_list = np.dot(ans_list, amari_m[i % len(amari_m)]) % mod
        else:
            t = int(s) * amari_l[i % len(amari_l)] % n
            ans_list = np.roll(ans_list, t)

    print(int(ans_list[r] % mod))


def initial(s, n):
    if s == "?":
        return np.array([1 if i < 10 else 0 for i in range(n)], dtype='int64')
    else:
        return np.array([1 if i == int(s) else 0 for i in range(n)], dtype='int64')


def shift(n, r):
    return np.array([[1 if (i - j + r) % n == 0 else 0 for j in range(n)] for i in range(n)])


def amari_list(n):
    ret = []
    for i in range(n + 1):
        r = 10**i % n
        if r in ret:
            return ret
        else:
            ret.append(r)


def amari_matrix(n, amari_list):
    ret = np.zeros((len(amari_list), n, n))
    for i, j in enumerate(amari_list):
        tmp = np.zeros((n, n))
        for k in range(10):
            tmp += shift(n, j * k % n)
        ret[i] = tmp
    return ret


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

n =int(input())
l = list(map(int,input().split()))
a = 1
for i in l:
    a *= i
if a > 10 **18:
    a = -1

print(a)
    

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    
    if 0 in a:
        print(0)
        return
    
    prod = 1
    for i in a:
        prod *= i
        if prod > 10 ** 18:
            print(-1)
            return
    
    print(prod)
    
    return

main()
### BUGGY CODE ###

import itertools

n, k = map(int, input().split())
*l, = map(int, input().split())

ans = 0
for c in itertools.combinations(l, k):
    ans = max(ans, sum(c))

print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
l = sorted(map(int, input().split()), reverse=True)

print(sum(l[:k]))
### BUGGY CODE ###

N = int(input())
tot = 1
for i in range(1, N+1):
    tot *= i
print(tot % (10 ** 9 + 7))

### FIXED CODE ###

N = int(input())
ans = 1
for i in range(1, N+1):
    ans = i * ans % (10 ** 9 + 7)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
sum = 0
for i in range(1,N+1):
    for j in range(1,N+1):
        if i < j:
            sum += A[i-1]*A[j-1]
print(sum%(10**9+7))

### FIXED CODE ###

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

mod= 10**9+7

A = sum(a)

ans=0

for i in a:
  A -= i
  A%=mod
  ans += A*i
  ans%=mod
print(ans)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np
 
K = INT()
sum = 0
 
for n in range(K):
  for m in range(K):
    for l in range(K):
      sum += gcd(n+1, gcd(m+1, l+1))
 
print(sum)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
K = INT()
sum = 0
 
for n in range(K):
  for m in range(K):
    for l in range(K):
      sum += gcd(n+1, gcd(m+1, l+1))
 
print(sum)
### BUGGY CODE ###

N,C = map(int,input().split())
D = [list(map(int,input().split())) for i in range(C)]
c = [list(map(int,input().split())) for i in range(N)]
color = [[] for i in range(3)]
for h in range(N):
    for w in range(N):
        color[(h+w+2)%3].append(c[h][w])

ans = float('inf')
for c1 in range(1,C+1):
    for c2 in range(1,C+1):
        if c1 != c2:
            for c3 in range(1,C+1):
                if c1 != c3 and c2 != c3:
                    cand = 0
                    for i in color[0]:
                        cand += D[i-1][c1-1]
                    for i in color[1]:
                        cand += D[i-1][c2-1]
                    for i in color[2]:
                        cand += D[i-1][c3-1]
                    ans = min(ans,cand)
print(ans)

### FIXED CODE ###

N,C = map(int,input().split())
D = [list(map(int,input().split())) for i in range(C)]
c = [list(map(int,input().split())) for i in range(N)]
color = [{} for i in range(3)]
for h in range(N):
    for w in range(N):
        if c[h][w] not in color[(h+w+2)%3]:
            color[(h+w+2)%3][c[h][w]] = 1
        else:
            color[(h+w+2)%3][c[h][w]] += 1

ans = float('inf')
for c1 in range(1,C+1):
    for c2 in range(1,C+1):
        if c1 != c2:
            for c3 in range(1,C+1):
                if c1 != c3 and c2 != c3:
                    cand = 0
                    for k,v in color[0].items():
                        cand += D[k-1][c1-1]*v
                    for k,v in color[1].items():
                        cand += D[k-1][c2-1]*v
                    for k,v in color[2].items():
                        cand += D[k-1][c3-1]*v
                    ans = min(ans,cand)
print(ans)
### BUGGY CODE ###

# 毎回ソートする？そんで一つもマイナスがないように選ぶ まにあうかは知らん
n, m = map(int, input().split())
arr = list(sorted(list(map(int, input().split()))))
for _ in range(m):
    b, c = map(int, input().split())
    for bi in range(b):
        if arr[bi] >= c:
            break
        arr[bi] = c
    arr = list(sorted(arr))
print(sum(arr))


### FIXED CODE ###

# 書き換える枚数は確定できる
# cの大きい順にしたものでaの小さい順にしたものを置き換えるイメージ
# なんか尺取っぽくなった

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))

bcs = []
for _ in range(m):
    bc = list(map(int, input().split()))
    bcs.append(bc)

bcs = sorted(bcs, key=lambda x: x[1], reverse=True)
ans = 0

i = 0
for b in bcs:
    while i < n and arr[i] < b[1] and b[0] > 0:
        ans += b[1]
        b[0] -= 1
        i += 1
print(ans + sum(arr[i:]))
### BUGGY CODE ###

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

MOD = 998244353

fact = [1]*200001
t = 1
for i in range(1,200001):
    t = (t*i)%MOD
    fact[i] = t

def ncr(n,r):
    return (fact[n] * pow(fact[r],MOD-2,MOD) % MOD) * pow(fact[n-r],MOD-2,MOD) % MOD

for i in range(2,2*K+1):
    t1,t2 = 0,0
    Ans = 0
    # p : 足して i になる整数の組の数
    np = i//2 - max(i-1-K,0)
    # p組からq組, 片方を使用する場合の数を足し合わせる
    # 偶奇で場合分け
    if i%2==0:
        # 偶数の場合 : 1組だけ同じ数の組があるため特別扱いする
        np -= 1
        for nq in range(np+1):
            # 同じ数の組の数字を全く含まない場合
            t1 = ncr(np,nq)*(2**nq)
            nr = K - np*2 - 1
            t2 = ncr(N+nr-1,N-nq) if N+nr-1>=N-nq else 0
            Ans += t1*t2
            # 同じ数の組の数字を1つ含む場合
            t2 = ncr(N-1+nr-1,N-1-nq) if N-1+nr-1>=N-1-nq else 0
            Ans += t1*t2
    else:
        # 奇数の場合 : p組全て互いに異なる数
        for nq in range(np+1):
            t1 = ncr(np,nq)*(2**nq)
            nr = K - np*2
            t2 = ncr(N+nr-1,N-nq) if N-1+nr-1>=N-1-nq else 0
            Ans += t1*t2
    print(Ans%MOD)


### FIXED CODE ###

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

MOD = 998244353

fact = [1]*4000
t = 1
for i in range(1,4000):
    t = (t*i)%MOD
    fact[i] = t

factinv = [1]*4000
for i in range(1,4000):
    factinv[i] = pow(fact[i], MOD-2, MOD)

def ncr(n,r):
    if n < 0 or r < 0 or n-r < 0:
        return 0
    return (fact[n] * factinv[r] * factinv[n-r]) % MOD

def nhr(n,r):
    if n == 0 and r == 0:
        return 1
    return ncr(n+r-1, r)

for i in range(2,2*K+1):
    t1,t2 = 0,0
    Ans = 0
    # p : 足して i になる整数の組の数
    np = i//2 - max(i-1-K,0)
    # p組からq組, 片方を使用する場合の数を足し合わせる
    # 偶奇で場合分け
    if i%2==0:
        # 偶数の場合 : 1組だけ同じ数の組があるため特別扱いする
        np -= 1
        for nq in range(np+1):
            # 同じ数の組の数字を全く含まない場合
            t1 = ncr(np,nq)*pow(2, nq, MOD)
            t1 %= MOD
            t2 = nhr(K-np*2+nq-1,N-nq)
            t2 %= MOD
            Ans = (Ans + t1*t2) % MOD
            # 同じ数の組の数字を1つ含む場合
            t2 = nhr(K-np*2+nq-1,N-nq-1)
            t2 %= MOD
            Ans = (Ans + t1*t2) % MOD
    else:
        # 奇数の場合 : p組全て互いに異なる数
        for nq in range(np+1):
            t1 = ncr(np,nq)*pow(2, nq, MOD)
            t1 %= MOD
            t2 = nhr(K-np*2+nq,N-nq)
            t2 %= MOD
            Ans = (Ans + t1*t2) % MOD
    print(Ans%MOD)
### BUGGY CODE ###

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

all = S.count("R") * S.count("G") * S.count("B")
count = 0
for i in range(N):
    for j in range(1,N):
        k = 2*j - i
        if k < N and i < j:
            if (S[i] != S[j]) and (S[j] != S[k]) and (S[k] != S[i]):
                count += 1
print(all-count)    

### FIXED CODE ###

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

all = S.count("R") * S.count("G") * S.count("B")
count = 0
for i in range(N):
    for j in range(1,N):
        k = 2*j - i
        if k < N and i < j:
            if (S[i] != S[j]) and (S[j] != S[k]) and (S[k] != S[i]):
                count += 1
print(all-count)
### BUGGY CODE ###

from itertools import accumulate


def solve(n, rev):
    def existence_right(rev_c):
        acc = [[0] * (n * 2)]
        row = [0] * (n * 2)
        for x in rev_c:
            row[n * 2 - x - 1] += 1
            acc.append(list(reversed(list(accumulate(row)))))
        return acc

    # How many white/black ball lower than 'k' righter than index x? (0<=x<=2N-1)
    # cost[color][k][x]
    cost = list(map(existence_right, rev))

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for w, x in enumerate(rev[0]):
        dp[w + 1][0] = dp[w][0] + cost[0][w][x]
    for b, y in enumerate(rev[1]):
        dp[0][b + 1] = dp[0][b] + cost[1][b][y]
    for w, x in enumerate(rev[0]):
        for b, y in enumerate(rev[1]):
            dp[w + 1][b + 1] = min(dp[w][b + 1] + cost[0][w][x] + cost[1][b + 1][x],
                                   dp[w + 1][b] + cost[0][w + 1][y] + cost[1][b][y])
    return dp[n][n]


n = int(input())
# White/Black 'k' ball is what-th in whole row?
rev = [[0] * n, [0] * n]
for i in range(n * 2):
    c, a = input().split()
    a = int(a) - 1
    rev[int(c == 'B')][a] = i
print(solve(n, rev))


### FIXED CODE ###

from itertools import accumulate


def solve(n, rev):
    def existence_right(rev_c):
        n2 = n * 2
        acc = [[0] * n2]
        row = [0] * n2
        for x in rev_c:
            row[n2 - x - 1] += 1
            acc.append(list(reversed(list(accumulate(row)))))
        return acc

    # How many white/black ball lower than 'k' righter than index x? (0<=x<=2N-1)
    # cost[color][k][x]
    cost = list(map(existence_right, rev))

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for w, x in enumerate(rev[0]):
        dp[w + 1][0] = dp[w][0] + cost[0][w][x]
    for b, y in enumerate(rev[1]):
        dp[0][b + 1] = dp[0][b] + cost[1][b][y]
    for w, x in enumerate(rev[0]):
        dpw0, dpw1 = dp[w], dp[w + 1]
        cost_wx, cost_w1 = cost[0][w][x], cost[0][w + 1]
        for b, y in enumerate(rev[1]):
            dpw1[b + 1] = min(dpw0[b + 1] + cost_wx + cost[1][b + 1][x],
                              dpw1[b] + cost_w1[y] + cost[1][b][y])
    return dp[n][n]


n = int(input())
# White/Black 'k' ball is what-th in whole row?
rev = [[0] * n, [0] * n]
for i in range(n * 2):
    c, a = input().split()
    a = int(a) - 1
    rev[int(c == 'B')][a] = i
print(solve(n, rev))
### BUGGY CODE ###

import math
honsu,hp=map(int , input().split())
huru=[]
nageru=[]
for i in range(honsu):
  a,b=input().split()
  huru+=[int(a)]
  nageru+=[int(b)]
cc=list(filter(lambda v:v>=max(huru) , nageru))
cou=0
for i in cc:
  hp-=i
  cou+=1
  if hp<=0:
    break
if hp>0:
  cou+=math.ceil(hp/max(huru))
print(cou)

### FIXED CODE ###

from math import ceil
 
N, H = map(int, input().split())
a, b = [], []
 
for _ in range(N):
    a_i, b_i = map(int, input().split())
    a.append(a_i)
    b.append(b_i)
 
max_a = max(a)
b = sorted(b, reverse=True)
ans = float('inf')
th_po = 0
 
for i in range(N):
    th_po += b[i]
    
    if H >= th_po:
        ans_cand = i + 1 + ceil((H - th_po) / max_a)
    else:
        ans_cand = i + 1
    
    ans = min([ans, ans_cand])
 
print(ans)
### BUGGY CODE ###

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

p = 1
conta = int(k)

for i in range(k):
  p = p * a[i]

while conta <= n-1:
  next_p = p * a[conta] // a[conta-k]
  if next_p > p:
    print('Yes')
  else:
    print('No')
  conta += 1

### FIXED CODE ###

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

for i in range(k,n):
  if a[i-k] < a[i]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

from itertools import accumulate

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0

a_accum = [0] + list(accumulate(a))
b_accum = [0] + list(accumulate(b))

for j in range(len(a_accum)):
  for i in range(len(b_accum)):
    t = a_accum[-(j+1)] + b_accum[-(i+1)]
    candi = (n-j) + (m-i)
    if ans >= candi:
      break
    if t <= k:
      ans = candi
      break

print(ans)

### FIXED CODE ###

from itertools import accumulate

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0

a_accum = [0] + list(accumulate(a))
b_accum = [0] + list(accumulate(b))

j = m
for i in range(n+1):
  while k < a_accum[i] + b_accum[j] and j >= 1:
    j -= 1
  if k >= a_accum[i] + b_accum[j] and ans < i + j:
    ans = i + j

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

n, m = map(int, input().split())
ab = sorted(set([tuple(map(int, input().split())) for _ in range(m)]))

c = []
flag = False
for i in ab:
    a, b = i[0], i[1]
    for i in c:
        if a in i or b in i:
            i.add(a)
            i.add(b)
            if len(i) == n:
                flag = True
    else:
        c.append(set())
        c[-1].add(a)
        c[-1].add(b)
    if flag:
        break
if m == 0:
    print(1)
else:
    print(max(map(len, c)))

### FIXED CODE ###

class Union:
    def __init__(self, n):
        self.parents = [-1] * n
    
    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            return self.root(self.parents[x])
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

uni = Union(n)
for a, b in ab:
    a -= 1
    b -= 1
    uni.unite(a, b)
print(-min(uni.parents))
### BUGGY CODE ###

import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, T = map(int, input().split())
I = np.array(read().split(), dtype = np.int64)
A = I[::2]
B = I[1::2]

sort_ind = np.argsort(A)
A = A[sort_ind]
B = B[sort_ind]

DP = [[0] * (T) for _ in range(N-1)]
for i in range(N-1):
	for j in range(T):
		if i == 0:
			if j >= A[0]:
				DP[i][j] = B[0]
		else:
			if j >= A[i]:
				DP[i][j] = max(DP[i-1][j], DP[i-1][j-A[i]] + B[i])
			else:
				DP[i][j] = DP[i-1][j]




# DP = np.zeros([N-1, T], dtype = np.int64)
# DP[0,A[0]:] = B[0]

# for i in range(1, N-1):
# 	for j in range(T):
# 		if j - A[i] >= 0:
# 			DP[i,j] = max(DP[i-1, j], DP[i-1,j-A[i]] + B[i])
# 		else:
# 			DP[i,j] = DP[i-1,j]

tmp = 0
for i in reversed(range(N)):
	tmp = max(B[i], tmp)
	B[i] = tmp
ans = 0
for i in range(N-1):
	ans = max(ans, DP[i][T-1] + B[i+1])

print(ans)

# C = DP[:,T-1] + B[1:]
# print(np.max(C))

### FIXED CODE ###

N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key = lambda x: x[0])

DP = [[0] * T for _ in range(N-1)]

for i in range(N-1):
	for j in range(T):
		if i == 0:
			if j >= AB[0][0]:
				DP[i][j] = AB[0][1]
		else:
			if j >= AB[i][0]:
				DP[i][j] = max(DP[i-1][j], DP[i-1][j-AB[i][0]] + AB[i][1])
			else:
				DP[i][j] = DP[i-1][j]

ans = 0
tmp = 0

for i in reversed(range(N-1)):
	tmp = max(tmp, AB[i+1][1])
	ans = max(ans, DP[i][T-1] + tmp)

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

n,k = map(int,input().split())
P = list(map(int,input().split()))
sum_a = 0
index = 0
for i in range(n):
    num = 0
    
    if (int(i)+k<=n):
        for j in range(int(i),int(i)+k):
            num += P[j]
        if(sum_a<num):
            index = i
            sum_a = num
            #print(sum_a,index)
total = 0.0
for m in range(index,index+k):
    total += sum(list(range(P[m]+1)))/P[m]
print(total)

### FIXED CODE ###

n,k = map(int,input().split())
P = list(map(int,input().split()))
sum_a = 0
index = 0

for i in range(k):
    sum_a += P[i]
num = sum_a
for j in range(1,n-k+1):
    num += P[j+k-1]
    #print(num)
    num -= P[j-1]
    #print(num)
    if(sum_a<num):
        index = j
        sum_a = num

total = 0.0
for m in range(index,index+k):
    total += sum(list(range(P[m]+1)))/P[m]
print(total)