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

from collections import deque

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


t = dict()

for i in range(1, n + 1):
    t[i] = set()


for a, b in ab:
    t[a].add(b)
    t[b].add(a)


def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)

            stack.extend(graph[vertex] - visited)
    return visited

length = 0

for i in range(1, n+1):
    ans = dfs(t, i)
    if len(ans) > length:
        length = len(ans)

print(length)


### FIXED CODE ###

from collections import deque

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


t = dict()

for i in range(1, n + 1):
    t[i] = set()


for a, b in ab:
    t[a].add(b)
    t[b].add(a)


def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)

            stack.extend(graph[vertex] - visited)
    return visited

seen = set()
length = 0
for i in range(1, n+1):
    if i not in seen:
        ans = dfs(t, i)
        for num in ans:
            seen.add(num)

        if len(ans) > length:
            length = len(ans)

print(length)
### BUGGY CODE ###

n = int(input())
count = 0
b = 0
a =  list(map(int, input().split()))
while len(a) != 0:
    b = a.count(a[0])
    if a[0] > b:
        count += b
    if a[0] < b:
        count += b - a[0]
    a = [item for item in a if item is not a[0]]
print (count)


### FIXED CODE ###

n = int(input())
a = []
a =  list(map(int, input().split()))
d = {}
c = 0
for x in a:
    d[x] = d.get(x, 0) + 1
for y,z in d.items():
    if y < z:
        c += z-y
    if y > z:
        c += z
print(c)
### BUGGY CODE ###

def dot(a, b):
    an = len(a)
    bn = len(b[0])
    c = [[0] * bn for _ in range(an)]
    for i in range(an):
        ai = a[i]
        for j in range(bn):
            ck = 0
            for ak, bk in zip(ai, [bi[j] for bi in b]):
                ck += ak * bk
                c[i][j] = ck % md
    return c


def pwr(a, k):
    c = None
    while k > 0:
        if k & 1:
            if c:
                c = dot(a, c)
            else:
                c = a
        a = dot(a, a)
        k >>= 1
    return c


md = 10 ** 9 + 7
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
print(sum([sum(pk) % md for pk in pwr(a, k)]) % md)


### FIXED CODE ###

import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


md = 10 ** 9 + 7
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
print(sum([sum(pk) % md for pk in pwr(a, k)]) % md)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
data=[0]*n
for i in range(n):
  data[i]=(p[i]/2)+float(0.5)
ans=0
for i in range(n-k+1):
  ans=max(ans,sum(data[i:i+k]))
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
data=[0]*n
for i in range(n):
  data[i]=p[i]/2+float(0.5)
res=sum(data[0:k])
ans=sum(data[0:k])
for i in range(n-k):
  res-=data[i]-data[i+k]
  ans=max(ans,res)
print(ans)
### BUGGY CODE ###

n = int(input())
lis = list(map(int, input().split()))
cnt = 0

for a,b in enumerate(lis):
    for i in range(a+1):
        if b > lis[i]:
            cnt += 1
            break
print(n-cnt)

### FIXED CODE ###

n = int(input())
lis = list(map(int, input().split()))
inf = 10 ** 15
ans = 0
for i in lis:
    if i < inf:
        ans += 1
        inf = i
print(ans)
### BUGGY CODE ###

import math
N, M = map(int, input().split())
prices = list(map(int, input().split(' ')))
total = 0
for i in range(M):
    prices.sort(reverse=True)
    prices[0] /= 2

for price in prices:
    total += math.floor(price)
print(total)

### FIXED CODE ###

import heapq
N, M = map(int, input().split(' '))
prices = list(map(lambda x: x * (-1), map(int, input().split(' '))))

# 優先度付きキューに変換
heapq.heapify(prices)

for i in range(M):
    # 最大のものを半額にしてまたキューに突っ込む
    heapq.heappush(prices, ((heapq.heappop(prices) * (-1)) // 2) * -1)

print(sum(prices) * -1)
### BUGGY CODE ###

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

matchNum = {
    1 : 2,
    2 : 5,
    3 : 5,
    4 : 4,
    5 : 5,
    6 : 6,
    7 : 3,
    8 : 7,
    9 : 6,
}

dp = [''] * (N + 1)
for n in range(1, N + 1):
    for k in nums:
        d = 0
        cnt = n - matchNum[k]
        if cnt >= 0 and (dp[cnt] != '' or cnt == 0):
            newVal = int(''.join(sorted(list(str(dp[cnt])) + [str(k)], reverse=True)))
            d = max(d, newVal)
        if d == 0:
            continue
        elif dp[n] == '':
            dp[n] = d
        else:
            dp[n] = max(dp[n], d)

print(dp[N])

### FIXED CODE ###

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

A.sort(reverse=True)

match = [2,5,5,4,5,6,3,7,6]

dp = [-float('inf')] * (N + 1)

dp[0] = 0
for i in range(1, N+1) :
    maxDigit = -float('inf')
    for a in A :
        if i - match[a - 1] >= 0 :
            maxDigit = max(maxDigit, dp[i - match[a - 1]] + 1)
    dp[i] = maxDigit

maxDigit = dp[-1]

r = N

for _ in range(maxDigit) :
    for a in A :
        if r - match[a - 1] < 0 or r < 0 :
            continue
        if dp[r - match[a - 1]] == dp[r] - 1 :
            print(a, end='')
            r -= match[a - 1]
            break

print('')
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
l = -1
r = 10**13

a.sort(reverse=True)
f.sort()

while l+1<r:
    #print()
    now = (l+r)//2
    s=0
    for i in range(n):
        s += max(0,a[i]-now//f[i])
    if s<=k:
        r=now
    else:
        l=now

print(r)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
l = -1
r = 10**12

a.sort(reverse=True)
f.sort()

while l+1<r:
    #print()
    now = (l+r)//2
    s=0
    for i in range(n):
        s += max(0,a[i]-now//f[i])
    if s<=k:
        r=now
    else:
        l=now

print(r)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=1
for i in range(n):
  ans=ans*l[i]
if ans>10**18:
  print(-1)
else:
  print(ans)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=1
f=1
i=0
for i in range(n):
  if ans<=10**18:
    ans=ans*l[i]
  else:
  	f=0
if f==1 and ans<=10**18:
  print(ans)
else:
  print(-1)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

L = []

for i in range(len(A)):
    for j in range(len(B)):
        tmp = A[i] + B[j] 
        L.append(tmp)

L.sort(reverse=True)

ans_list =[]
for i in range(min(K,len(L))):
    for j in range(len(C)):
        tmp = L[i] + C[j]
        ans_list.append(tmp)

ans_list.sort(reverse=True)


for i in range(K):
    print(ans_list[i])

### FIXED CODE ###

#%%
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()

bc = [0] * (y * z)
q = 0
for i in range(y):
    for j in range(z):
        bc[q] = b[i] + c[j]
        q += 1

bc.sort(reverse=True)
r = len(bc)
bc = bc[:min(k, r)]

abc = [0] * (x * min(k, r))
q = 0
for i in range(min(k, r)):
    for j in range(x):
        abc[q] = bc[i] + a[j]
        q += 1

abc.sort(reverse=True)
for i in range(min(k, x*y*z)):
    print(abc[i])
### BUGGY CODE ###

def deep_search(L,i,f):
    Q=L[i]
    if f[i]==0:
        f[i]=i
        for j in L[i]:
            f[j]=i
        while Q!=[]:
            p=Q.pop()
            Q=Q+L[p]
            for j in L[p]:
                f[j]=i
    return f

N,K,L=input().split(" ")
N=int(N)
K=int(K)
L=int(L)
a=[0 for i in range(N+1)]
b=[0 for i in range(N+1)]
road=[[] for i in range(N+1)]
train=[[] for i in range(N+1)]
for i in range(K+L):
    p,q=input().split(" ")
    p=int(p)
    q=int(q)
    if i<K:
        road[p].append(q)
    else:
        train[p].append(q)
for i in range(1,N+1):
    a=deep_search(road,i,a)
    b=deep_search(train,i,b)
ans=[[a[i],b[i]] for i in range(1,N+1)]
for i in range(N):
    print(ans.count(ans[i]),end=" ")

### FIXED CODE ###

from collections import defaultdict
class Unionfind:
    def __init__(self,n):
        self.n=n
        self.roots=[i for i in range(self.n)]


    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.root(x)>self.root(y):
                self.roots[self.root(x)]=self.root(y)
            else:
                self.roots[self.root(y)]=self.root(x)
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train.unite(r-1,s-1)



count=defaultdict(lambda:0)
point=[]
for i in range(N):
    a=road.root(i)
    b=train.root(i)
    l=[a,b]
    point.append(l)
    count[str(l)]+=1
for i in point:
    print(count[str(i)],end=" ")
### BUGGY CODE ###

from sys import stdin
from collections import defaultdict as dd
from collections import deque as dq
import itertools as it
from math import sqrt, log, log2
from fractions import Fraction

n, k = map(int, input().split())
intensity = list(map(int, stdin.readline().split()))

count = 0
while count < k:
    totsum = 0
    prefs = [0]*n
    zeros = []
    for i in range(n):
        if intensity[i]!=0:
            l = i - intensity[i]
            r = i + intensity[i] + 1

            prefs[max(l, 0)] += 1
            if r <= n-1: 
                prefs[r] += -1
        else:
            zeros.append(i)
            
    for i in range(1, n):
        prefs[i] += prefs[i-1]
        totsum += prefs[i]
    
    for i in zeros:
        if intensity[i] == 0:
            prefs[i] += 1
            totsum += 1
    
    if sum(prefs) == n*k:
        print(*prefs)
        exit()
    
    intensity = prefs
    count += 1

print(*prefs)

### FIXED CODE ###

from sys import stdin
# from collections import defaultdict as dd
# from collections import deque as dq
# import itertools as it
# from math import sqrt, log, log2
# from fractions import Fraction

n, k = map(int, input().split())
intensity = list(map(int, stdin.readline().split()))

count = 0
while count < k:
    totsum = 0
    prefs = [0]*n
    zeros = []
    for i in range(n):
        l = i - intensity[i]
        r = i + intensity[i] + 1

        prefs[max(l, 0)] += 1
        if r <= n-1: 
            prefs[r] += -1
            
    for i in range(1, n):
        prefs[i] += prefs[i-1]
        totsum += prefs[i]
    
    if sum(prefs) == n*n:
        print(*prefs)
        exit()
    
    intensity = prefs
    count += 1

print(*prefs)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
opes = [tuple(map(int, input().split())) for _ in range(M)]
opes.sort(key=lambda x: -x[1])
D = [C for B, C in opes for _ in range(B)]

A.sort()
for i, d in enumerate(D):
    if i >= len(A) or A[i] >= d:
        break
    A[i] = d

print(sum(A))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
opes = [tuple(map(int, input().split())) for _ in range(M)]
opes.sort(key=lambda x:-x[1])

D = []
lenD = 0
for B, C in opes:
    D += [C]*B
    lenD += B
    if lenD >= N:
        break

A.sort()
for i, d in enumerate(D[:N]):
    if A[i] >= d:
        break
    A[i] = d

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

N = int(input())
S = [input() for i in range(N)]
count = 0
for i, s in enumerate(S):
    for j in range(i+1, N):
        for c in s:
            if s.count(c) != S[j].count(c):
                break
        else:
            count += 1
print(count)


### FIXED CODE ###

N = int(input())
S = [input() for i in range(N)]

count = 0
appeared = {}
for i in range(N):
    S[i] = "".join(sorted(list(S[i])))
    if S[i] in appeared:
        count += appeared[S[i]]
        appeared[S[i]] += 1
    else:
        appeared[S[i]] = 1
print(int(count))
### BUGGY CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, W):
    dp = [-1] * (W + 1)
    dp[0] = 0
    for i in range(n):
        wi, vi = map(int, input().split())
        dp_ = list(dp)
        for w in range(W + 1):
            if dp[w] >= 0:
                w_ = w + wi
                v_ = dp[w] + vi
                if w_ <= W and dp[w_] < v_:
                    dp_[w_] = v_
        dp = dp_
    return(max(dp))

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5

print(f(n, w))


### FIXED CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wlimit):
    dp = [-1] * (wlimit + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        wi, vi = map(int, input().rstrip().split())
        dp_ = list(dp)
        for w in range(wlimit + 1):
            if dp[w] >= 0:
                w_ = w + wi
                v_ = dp[w] + vi
                if w_ <= wlimit and dp[w_] < v_:
                    dp_[w_] = v_
        dp = dp_
    return(max(dp))

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5

print(f(n, w))
### BUGGY CODE ###

import numpy as np

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

after_cumsum_RGB = {}
R, G, B = np.zeros(N+1), np.zeros(N+1), np.zeros(N+1)

def rgb_hash(a):
  if S[i] == 'R':
    return 0
  elif S[i] == 'G':
    return 1
  elif S[i] == 'B':
    return 2
  
def ci_hash(a):
  if 'R' not in a:
    return 0
  elif 'G' not in a:
    return 1
  elif 'B' not in a:
    return 2

def c_hash(a):
  if 'R' not in a:
    return 'R'
  elif 'G' not in a:
    return 'G'
  elif 'B' not in a:
    return 'B'
  
for i in range(N):
  if S[i] == 'R':
    R[i] = 1
  if S[i] == 'G':
    G[i] = 1
  if S[i] == 'B':
    B[i] = 1
after_cumsum_RGB = {'R': R[::-1].cumsum()[::-1], 'G': G[::-1].cumsum()[::-1], 'B': B[::-1].cumsum()[::-1]}

ans = 0
for i in range(0, N-2):
  for j in range(i+1, N-1):
    if S[i] != S[j]:
      c = c_hash([S[i], S[j]])
      ans += after_cumsum_RGB[c][j+1]
      if 2*j-i <= N-1:
        if S[2*j-i] == c:
          ans -= 1
print(int(ans))
      
    

### FIXED CODE ###

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

R = S.count('R')
G = S.count('G')
B = N - R - G

ans = R * G * B

for i in range(0, N-2):
  for j in range(i+1,N-1):
    k = 2 * j - i
    if k >= N:
      break
    else:
      if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        ans -= 1

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

def comp(a,b):
  r=""
  for x,y in zip(a,b):
    if x==y:
      r += x
    elif y=="?":
      r += x
    elif x=="?":
      r += y
    else:
      return False
  return r

def merge(a,b):
  for i in range(len(a)-len(b)+1):
    m = comp(a[i:],b)
    if m:
      yield a[:i]+m+a[i+len(b):]
  
  for i in range(1,len(b)):
    m = comp(b[i:], a)
    if m:
      yield  b[:i]+m+a[len(b)-i:]
    m = comp(b, a[-len(b)+i:])
    if m:
      yield a[:-len(b)+i]+m+b[-i:]
  yield a+b
  yield b+a

def min_merge(a,b,c):
  a,b,c=sorted([a,b,c],key=len,reverse=True)
  ab = len(a)+len(b)
  abc = float("inf")
  for d in merge(a,b):
    if len(d) > abc:
      break
    l = len(next(merge(d, c)))
    abc = min(abc, l)
  if abc <= ab:
    return abc
  
  for i in range(1,min(len(c),abc-ab)):
    for j in range(1,len(c)):
      if comp(a[-j:]+"?"*i+b, c):
        return ab+i
      if comp(b[-j:]+"?"*i+a, c):
        return ab+i
  return abc

a=input()
b=input()
c=input()

print(min_merge(a,b,c))



### FIXED CODE ###

from itertools import *
from heapq import *

def comp(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def comp3(a,b,c):
  return 

def comp3(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k]))

def _merge_mid(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    if comp(a[i:],b):
      yield i

def merge_mid(a,b):
  return list(_merge_mid(a,b))

def _merge_right(a,b):
  la, lb = map(len,[a,b])
  for i in range(max(la-lb+1, 1),la):
    if comp(b, a[i-la:]):
      yield i
  yield la

def merge_right(a,b):
  return list(_merge_right(a,b))

class K(int):
  def __new__(cls, *args, **kwargs):
    cb = kwargs.pop("cb")
    i = int.__new__(cls, *args, **kwargs)
    i.cb = cb
    return i

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]):
        return len_keys[0]
  
  def candicates(a,b,c):
    return chain(
      (K(i+len_keys[b], cb=lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp3(0,i,j,keys[a],keys[b],keys[c]) for j in dropwhile((i-len_keys[c]).__gt__, mid[a,c]+right[a,c]))
      )) for i in dropwhile((len_keys[c]-len_keys[b]+1).__gt__, right[a,b])),
      (K(min(i+next(dropwhile((len_keys[a]-i+1).__gt__, y))+len_keys[b] for i in x), cb=lambda:True) for (x, y) in [sorted((right[a,c], right[c,b]), key=len)]),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k
  
  return sum(len_keys)

a=input()
b=input()
c=input()

print(min_merge(a,b,c))
### BUGGY CODE ###

from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = {}
sorted_querys = sorted(querys)
check_points = sorted(check_points, key=itemgetter(2))
for q in querys:
    time[q] = -1
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(sorted_querys, start)
    right = b_left(sorted_querys, end)
    for q in sorted_querys[left:right]:
        time[q] = x
    sorted_querys = sorted_querys[:left] + sorted_querys[right:]
    if len(sorted_querys) == 0:
        break
for q in querys:
    print(time[q])


### FIXED CODE ###

from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1 for _ in range(Q)]
jump = [-1 for _ in range(Q)]
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)
### BUGGY CODE ###

#入力部
H, W = [int(i) for i in input().split()]
#mapの入力
mymap = [] #mapの配列
for i in range(H):
    mymap.append(list(input()))
Lmap = list(list(-1 for a in range(W)) for b in range(H)) #列探索配列
Rmap = list(list(-1 for a in range(W)) for b in range(H)) #列探索配列（逆順）
Umap = list(list(-1 for a in range(W)) for b in range(H)) #行探索配列
Dmap = list(list(-1 for a in range(W)) for b in range(H)) #行探索配列（逆順）

#Lmap
for i in range(H):
  mycnt = 1
  for j in range(W):
    if mymap[i][j] == '#':
      Lmap[i][j] = 0
      mycnt = 1
    else: 
      Lmap[i][j] = mycnt
      mycnt += 1

#Rmap
for i in range(H):
  mycnt = 1
  for j in reversed(range(W)):
    if mymap[i][j] == '#':
      Rmap[i][j] = 0
      mycnt = 1
    else: 
      Rmap[i][j] = mycnt
      mycnt += 1

#Dmap & 最大値の探索
for i in range(W):
  mycnt = 1
  for j in reversed(range(H)):
    if mymap[j][i] == '#':
      Dmap[j][i] = 0
      mycnt = 1
    else: 
      Dmap[j][i] = mycnt
      mycnt += 1

#Umap
for i in range(W):
  mycnt = 1
  for j in range(H):
    if mymap[j][i] == '#':
      Umap[j][i] = 0
      mycnt = 1
    else: 
      Umap[j][i] = mycnt
      mycnt += 1

      
#Lmap  & 最大値の検索
mymax = -99
for i in range(H):
  mycnt = 1
  for j in range(W):
    if mymap[i][j] == '#':
      Lmap[i][j] = 0
      mycnt = 1
    else: 
      Lmap[i][j] = mycnt
      mycnt += 1
      #最大値の検索
      if Lmap[i][j]+ Rmap[i][j]+ Umap[i][j]+ Dmap[i][j] > mymax:
        mymax = Lmap[i][j]+ Rmap[i][j]+ Umap[i][j]+ Dmap[i][j] 
        
print(mymax-3)

### FIXED CODE ###

import numpy as np
 
H, W = map(int, input().split())
#mapの入力
mymap = [] 
for i in range(H):
    mymap.append(list(input()))

#探索可能性をブーリアン表記
mymap = (np.array(mymap) == ".")
  
L = np.zeros((H, W), dtype=int) #左側から探索した場合の配列
R = np.zeros((H, W), dtype=int) #右側から探索した場合の配列
U = np.zeros((H, W), dtype=int) #上側から探索した場合の配列
D = np.zeros((H, W), dtype=int) #下側から探索した場合の配列

#列ごとに左から
for j in range(W):
  if j == 0: #左端
    L[:, j] = mymap[:, j] #true = 1, false = 0
  else:
    L[:, j] = (L[:, j - 1] + 1) * mymap[:, j] #trueの場合は1つ左の列の値を加算しながら

#列ごとに右から
for j in range(W - 1, -1, -1): #(引数：開始数，終了数，加算数）
  if j >= W - 1: #右端
    R[:, j] = mymap[:, j]
  else:
    R[:, j] = (R[:, j + 1] + 1) * mymap[:, j] 

#行ごとに上から
for i in range(H):
  if i <= 0: #上端
    U[i, :] = mymap[i, :]
  else:
    U[i, :] = (U[i - 1, :] + 1) * mymap[i, :]

#行ごとに下から
for i in range(H - 1, -1, -1):
  if i >= H - 1: #下端
    D[i, :] = mymap[i, :]
  else:
    D[i, :] = (D[i + 1, :] + 1) * mymap[i, :]

#総和から重複分(=3)の差をとって，最大値を出力
print(np.max(L + R + U + D - 3))
### BUGGY CODE ###

n,q = map(int,input().split())
node = [[]for _ in range(n)]
looked = [0 for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    node[b-1].append(a-1)
    node[a-1].append(b-1)
counter = [0 for _ in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    counter[p-1] += x
queue = [0]
looked[0] = 1
while(len(queue)):
    now = queue.pop(0)
    for i in node[now]:
        if looked[i] == 0:
            queue.append(i)
            counter[i] += counter[now]
            looked[i] = 1
print(" ".join(list(map(str,counter))))

### FIXED CODE ###

from collections import deque
def main():
    n,q = map(int,input().split())
    node = [[]for _ in range(n)]
    looked = [1]*n
    for i in range(n-1):
        a,b = map(int,input().split())
        node[b-1].append(a-1)
        node[a-1].append(b-1)
    counter = [0]*n
    for i in range(q):
        p,x = map(int,input().split())
        counter[p-1] += x
    queue = deque([0])
    looked[0] = 0
    while(queue):
        now = queue.pop()
        for i in node[now]:
            if looked[i]:
                queue.append(i)
                counter[i] += counter[now]
                looked[i] = 0
    print(*counter)
main()
### BUGGY CODE ###

N, T = [int(s) for s in input().split()]
PS = [int(s) for s in input().split()]

def main():
    t = T
    ps = PS
    ans = 0
    while ps:
        p = ps.pop(0)
        ans += min(ps[0] - p, t) if ps else t
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque

N, T = [int(n) for n in input().split()]
Q = deque([int(n) for n in input().split()])

def main():
    ans = 0
    while Q:
        curr = Q.popleft()
        next = Q[0] if Q else float('inf')
        ans += min(T, next - curr)
    print(ans)

if __name__ == '__main__':
    main()