In a public bath, there is a shower which emits water for T seconds when the switch is pushed.
If the switch is pushed when the shower is already emitting water, from that moment it will be emitting water for T seconds.
Note that it does not mean that the shower emits water for T additional seconds.
N people will push the switch while passing by the shower.
The i-th person will push the switch t_i seconds after the first person pushes it.
How long will the shower emit water in total?

-----Constraints-----
 - 1 ≤ N ≤ 200,000
 - 1 ≤ T ≤ 10^9
 - 0 = t_1 < t_2 < t_3 < , ..., < t_{N-1} < t_N ≤ 10^9
 - T and each t_i are integers.

-----Input-----
Input is given from Standard Input in the following format:
N T
t_1 t_2 ... t_N

-----Output-----
Assume that the shower will emit water for a total of X seconds. Print X.

-----Sample Input-----
2 4
0 3

-----Sample Output-----
7

Three seconds after the first person pushes the water, the switch is pushed again and the shower emits water for four more seconds, for a total of seven seconds.

Difficulty: EASY

Starter code:

Solutions:
(n, T) = map(int, input().split())
t = list(map(int, input().split()))
ans = 0
for i in range(n - 1):
	ans += min(T, t[i + 1] - t[i])
print(ans + T)


(n, t) = map(int, input().split())
T = list(map(int, input().split()))
ans = 0
for i in range(1, n):
	if T[i] - T[i - 1] >= t:
		ans += t
	else:
		ans += T[i] - T[i - 1]
print(ans + t)


import math
(n, t) = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 0
a.append(math.inf)
for i in range(n):
	ans += min(t, a[i + 1] - a[i])
print(ans)


(n, t) = map(int, input().split())
ts = list(map(int, input().split()))
ans = 0
now = 0
for i in ts[1:]:
	if i <= now + t:
		ans += i - now
	else:
		ans += t
	now = i
print(ans + t)


(n, t) = map(int, input().split())
T = list(map(int, input().split()))
s = n * t
for i in range(1, n):
	if T[i] - T[i - 1] < t:
		s -= t - (T[i] - T[i - 1])
print(s)


(N, T) = map(int, input().split())
lsT = list(map(int, input().split()))
tend = T
ans = T
for i in range(1, N):
	if lsT[i] <= tend:
		ans += lsT[i] + T - tend
		tend = lsT[i] + T
	else:
		ans += T
		tend = lsT[i] + T
print(ans)


(N, T) = map(int, input().split())
t = list(map(int, input().split()))
ans = T
for i in range(N - 1):
	now = t[i + 1] - t[i]
	ans += min(now, T)
print(ans)


(N, T) = map(int, input().split())
L = list(map(int, input().split()))
ans = 0
for i in range(N - 1):
	ans += min(L[i + 1] - L[i], T)
print(ans + T)


(N, T) = [int(x) for x in input().split()]
t_list = [int(x) for x in input().split()]
t_s = t_e = ans = 0
for t in t_list:
	if t > t_e:
		ans += t_e - t_s
		t_s = t
	t_e = t + T
ans += t_e - t_s
print(ans)


(n, t) = list(map(int, input().split()))
tn = list(map(int, input().split()))
res = t
for i in range(1, n):
	tmp = min(tn[i] - tn[i - 1], t)
	res += tmp
print(res)


(n, t) = map(int, input().split())
T = tuple(map(int, input().split()))
ans = 0
for i in range(0, n - 1):
	dt = T[i + 1] - T[i]
	ans += min(dt, t)
print(ans + t)


(N, T) = map(int, input().split())
X = list(map(int, input().split()))
S = 0
for i in range(1, N):
	if X[i] - X[i - 1] >= T:
		S += T
	else:
		S += X[i] - X[i - 1]
print(S + T)


(N, T) = map(int, input().split())
t = list(map(int, input().split()))
ans = T
for i in range(N - 1):
	if t[i + 1] - t[i] >= T:
		ans += T
	else:
		ans += t[i + 1] - t[i]
print(ans)


(n, t) = map(int, input().split())
l = list(map(int, input().split()))
old = 0
ans = t
for i in range(1, n):
	ans += l[i] + t - max(old + t, l[i])
	old = l[i]
print(ans)


import sys
input = sys.stdin.readline
(N, T) = list(map(int, input().split()))
t = list(map(int, input().split()))
t_stop = []
for i in range(N):
	t_stop.append(t[i] + T)
cum_flow = T * N
for i in range(N - 1):
	cum_flow -= max(t_stop[i] - t[i + 1], 0)
print(cum_flow)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	(N, T, *t) = list(map(int, read().split()))
	ans = 0
	for i in range(N - 1):
		if t[i] + T > t[i + 1]:
			ans += t[i + 1] - t[i]
		else:
			ans += T
	ans += T
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):

	def assertIO(self, input, output):
		(stdout, stdin) = (sys.stdout, sys.stdin)
		(sys.stdout, sys.stdin) = (StringIO(), StringIO(input))
		resolve()
		sys.stdout.seek(0)
		out = sys.stdout.read()[:-1]
		(sys.stdout, sys.stdin) = (stdout, stdin)
		self.assertEqual(out, output)

	def test_入力例_1(self):
		input = '2 4\n0 3'
		output = '7'
		self.assertIO(input, output)

	def test_入力例_2(self):
		input = '2 4\n0 5'
		output = '8'
		self.assertIO(input, output)

	def test_入力例_3(self):
		input = '4 1000000000\n0 1000 1000000 1000000000'
		output = '2000000000'
		self.assertIO(input, output)

	def test_入力例_4(self):
		input = '1 1\n0'
		output = '1'
		self.assertIO(input, output)

	def test_入力例_5(self):
		input = '9 10\n0 3 5 7 100 110 200 300 311'
		output = '67'
		self.assertIO(input, output)

def resolve():
	(N, T) = list(map(int, input().split()))
	t = list(map(int, input().split()))
	ans = T
	for i in range(N - 2, -1, -1):
		ans += min(T, t[i + 1] - t[i])
	print(ans)

def __starting_point():
	resolve()
__starting_point()


import numpy as np

def main():
	(n, t) = list(map(int, input().split()))
	ts = list(map(int, input().split()))
	ans = t
	for i in range(n - 1):
		now = ts[i + 1] - ts[i]
		ans += min(now, t)
	print(ans)

def __starting_point():
	main()
__starting_point()


(N, T) = map(int, input().split())
t_List = [int(x) for x in input().split()]
pre = 0
ans = T
for t in t_List:
	if t - pre <= T:
		ans += t - pre
	else:
		ans += T
	pre = t
print(ans)


def main():
	(n, t) = map(int, input().split())
	s = list(map(int, input().split()))
	cnt = n * t
	for i in range(n - 1):
		if s[i + 1] - s[i] < t:
			cnt -= s[i] + t - s[i + 1]
	else:
		print(cnt)
main()


(N, T) = map(int, input().split())
time = [int(x) for x in input().split()]
ans = 0
for i in range(N - 1):
	ans += min(T, time[i + 1] - time[i])
ans += T
print(ans)


(n, t) = map(int, input().split())
T = list(map(int, input().split()))
(prev, now, ans) = (T[0], 0, 0)
for i in range(n):
	if not i:
		continue
	now = T[i]
	if now - prev > t:
		ans += t
	else:
		ans += now - prev
	prev = now
ans += t
print(ans)


(N, T) = list(map(int, input().split()))
t = list(map(int, input().split()))
d = []
for i in range(N - 1):
	tmp = t[i + 1] - t[i]
	if tmp > T:
		d.append(T)
	else:
		d.append(tmp)
print(sum(d) + T)


(n, t) = map(int, input().split())
time = [int(i) for i in input().split()]
sum = 0
for i in range(len(time) - 1):
	if time[i + 1] - time[i] < t:
		sum += time[i + 1] - time[i]
	else:
		sum += t
print(sum + t)


(n, t) = map(int, input().split())
lis = list(map(int, input().split()))
ans = t
for i in range(1, n):
	if lis[i] - lis[i - 1] >= t:
		ans += t
	else:
		ans += lis[i] - lis[i - 1]
print(ans)


(N, T) = map(int, input().split())
t = list(map(int, input().split()))
ans = 0
for i in range(N):
	if i == 0:
		start = t[i]
		finish = t[i] + T
		continue
	if t[i] < finish:
		finish = t[i] + T
		continue
	else:
		ans += finish - start
		start = t[i]
		finish = t[i] + T
ans += finish - start
print(ans)


(N, K) = (int(T) for T in input().split())
Per = [int(T) for T in input().split()]
Wat = 0
for X in range(0, N - 1):
	if Per[X] + K <= Per[X + 1]:
		Wat += K
	else:
		Wat += Per[X + 1] - Per[X]
print(Wat + K)


(n, t) = map(int, input().split())
l = list(map(int, input().split()))
s = 0
pre_end = 0
for tt in l:
	time = t - max(0, pre_end - tt)
	s += time
	pre_end = tt + t
print(s)


from typing import List

def answer(N: int, T: int, t: List[int]) -> int:
	ans = 0
	for i in range(N - 1):
		ans += min(T, t[i + 1] - t[i])
	return ans + T

def main():
	(N, T) = list(map(int, input().split()))
	t = list(map(int, input().split()))
	print(answer(N, T, t))

def __starting_point():
	main()
__starting_point()


(N, T) = map(int, input().split())
time = list(map(int, input().split()))
cnt = 0
for i in range(1, N):
	cnt += min(T, time[i] - time[i - 1])
print(cnt + T)


(n, t) = map(int, input().split())
lst = list(map(int, input().split())) + [10 ** 12]
sec = 0
for i in range(n):
	sec += min(t, lst[i + 1] - lst[i])
print(sec)


(n, t) = map(int, input().split())
arr = list(map(int, input().split()))
total = t
time = 0
for i in arr[1:]:
	total += min(t, i - time)
	time = i
print(total)


(n, t) = list(map(int, input().split()))
l = list(map(int, input().split()))
now = 0
latest = 0
ans = 0
for i in l:
	now = i
	if now - latest >= t:
		ans += t
	else:
		ans += now - latest
	latest = now
ans += t
print(ans)


(N, T) = map(int, input().split())
time = list(map(int, input().split()))
ans = 0
for i in range(N - 1):
	if time[i + 1] - time[i] >= T:
		ans += T
	else:
		ans += time[i + 1] - time[i]
print(ans + T)


(n, t) = map(int, input().split())
a = list(map(int, input().split()))
print(sum([min(t, a[i] - a[i - 1]) for i in range(1, n)]) + t)


import sys
sys.setrecursionlimit(10 ** 8)
ini = lambda : int(sys.stdin.readline())
inl = lambda : [int(x) for x in sys.stdin.readline().split()]
ins = lambda : sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print('\x1b[33m', *a, '\x1b[0m', **dict(file=sys.stderr, **kw))

def solve():
	(n, T) = inl()
	t = inl()
	assert len(t) == n
	assert t[0] == 0
	p = 0
	ans = 0
	for i in range(1, n):
		x = t[i]
		ans += min(x - p, T)
		p = x
	ans += T
	return ans
print(solve())


(n, t) = map(int, input().split())
l = list(map(int, input().split()))
total = 0
for i in range(n):
	if i == n - 1:
		total += t
		break
	if l[i + 1] - l[i] >= t:
		total += t
	else:
		total += l[i + 1] - l[i]
print(total)


(n, m) = map(int, input().split())
t = list(map(int, input().split()))
num = 0
for i in range(n - 1):
	if t[i + 1] - t[i] < m:
		num += t[i + 1] - t[i]
	else:
		num += m
print(num + m)


(n, t) = map(int, input().split())
arr = list(map(int, input().split()))
summ = t
for i in range(n - 1):
	summ += min(t, arr[i + 1] - arr[i])
print(summ)


(n, t) = map(int, input().split())
tlist = list(map(int, input().split()))
time = t
for i in range(0, n - 1):
	if tlist[i + 1] - tlist[i] <= t:
		time += tlist[i + 1] - tlist[i]
	else:
		time += t
print(time)


(N, T) = map(int, input().rstrip().split(' '))
t = list(map(int, input().rstrip().split(' ')))
ans = 0
for i in range(N - 1):
	ans += min(T, t[i + 1] - t[i])
ans += T
print(ans)


(N, T) = list(map(int, input().split()))
A = list(map(int, input().split()))
ans = 0
for i in range(len(A) - 1):
	ans += min(T, A[i + 1] - A[i])
print(ans + T)


(a, b) = input().split()
a = int(a)
b = int(b)
c = list(map(int, input().split()))
m = a * b
for i in range(a - 1):
	if c[i + 1] - c[i] < b:
		m = m - (b - (c[i + 1] - c[i]))
print(m)


(n, t) = map(int, input().split())
l = list(map(int, input().split()))
nums = [0] * (n - 1)
for i in range(n - 1):
	nums[i] = l[i + 1] - l[i]
ans = t
m = 0
for i in nums:
	ans += min(i, t)
print(ans)


(N, T) = map(int, input().split())
t = list(map(int, input().split()))
t.append(10 ** 10)
ans = 0
flg = 0
temp = 0
for i in range(N):
	if t[i] + T > t[i + 1]:
		if flg == 0:
			temp = t[i]
			flg = 1
		continue
	else:
		if flg == 0:
			ans += T
		else:
			ans += t[i] - temp + T
		flg = 0
print(ans)


import sys
import math
import itertools
import bisect
from copy import copy, deepcopy
from collections import deque, Counter
from decimal import Decimal

def s():
	return input()

def i():
	return int(input())

def S():
	return input().split()

def I():
	return map(int, input().split())

def L():
	return list(map(int, input().split()))

def l():
	return list(map(int, input().split()))

def lcm(a, b):
	return a * b // math.gcd(a, b)
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 9
mod = 10 ** 9 + 7
(N, T) = I()
t = l()
ans = T
for i in range(N - 1):
	ans += min(t[i + 1] - t[i], T)
print(ans)


(N, S) = map(int, input().split())
T = list(map(int, input().split()))
a = S
for n in range(N - 1):
	a += min(S, T[n + 1] - T[n])
print(a)


(n, t) = map(int, input().split())
tm = list(map(int, input().split()))
start_time = -1
stop_time = -1
ans = 0
for i in range(0, n):
	if start_time <= tm[i] <= stop_time:
		stop_time += t + tm[i] - stop_time
	else:
		ans += stop_time - start_time
		start_time = tm[i]
		stop_time = tm[i] + t
	if i == n - 1:
		ans += stop_time - start_time
print(ans)


import math
from math import gcd, pi, sqrt
INF = float('inf')
import sys
sys.setrecursionlimit(10 ** 6)
import itertools
from collections import Counter, deque

def i_input():
	return int(input())

def i_map():
	return list(map(int, input().split()))

def i_list():
	return list(i_map())

def i_row(N):
	return [i_input() for _ in range(N)]

def i_row_list(N):
	return [i_list() for _ in range(N)]

def s_input():
	return input()

def s_map():
	return input().split()

def s_list():
	return list(s_map())

def s_row(N):
	return [s_input for _ in range(N)]

def s_row_str(N):
	return [s_list() for _ in range(N)]

def s_row_list(N):
	return [list(s_input()) for _ in range(N)]

def main():
	(N, T) = i_map()
	t = i_list()
	ans = 0
	for (i, k) in enumerate(t[1:], start=1):
		if k - t[i - 1] <= T:
			ans += k - t[i - 1]
		else:
			ans += T
	ans += T
	print(ans)

def __starting_point():
	main()
__starting_point()


def test():
	arr = []
	ans = 0
	first_input = input()
	first_num = first_input.split()
	a = int(first_num[0])
	b = int(first_num[1])
	sec_input = input()
	sec_num = sec_input.split()
	if len(sec_num) == a:
		pass
	else:
		print('Wrong input')
	for i in sec_num:
		arr.append(int(i))
	for i in range(0, len(arr) - 1):
		num = arr[i]
		num_2 = arr[i + 1]
		if num_2 - num > b:
			ans += b
		else:
			ans += num_2 - num
	ans += b
	print(ans)
test()


(n, t) = list(map(int, input().split()))
l = list(map(int, input().split()))
s = 0
z = 0
for i in l:
	if z - i > 0:
		s += i + t - z
	else:
		s += t
	z = i + t
print(s)


(N, T, *t) = map(int, open(0).read().split())
ans = sum((y - x if y - x < T else T for (x, y) in zip(t[:N - 1], t[1:]))) + T
print(ans)


(N, T) = map(int, input().split())
t = list(map(int, input().split()))
(ans, now) = (0, 0)
for i in t:
	if i < now:
		ans -= now - i
	ans += T
	now = i + T
print(ans)


(N, T) = [int(i) for i in input().split(' ')]
t = [int(j) for j in input().split(' ')]
dt = []
for i in range(N - 1):
	dt.append(t[i + 1] - t[i])
else:
	dt.append(T)
print(sum([min([dti, T]) for dti in dt]))


(n, t) = map(int, input().split())
t_list = list(map(int, input().split()))
s = 0
for i in range(1, n):
	if t_list[i] - t_list[i - 1] >= t:
		s += t
	else:
		s += t_list[i] - t_list[i - 1]
print(s + t)


(n, t) = map(int, input().split())
a = list(map(int, input().split())) + [10 ** 10]
ans = 0
for i in range(n):
	ans += min(a[i + 1] - a[i], t)
print(ans)


(N, T) = [int(x) for x in input().split()]
t = [int(x) for x in input().split()]
T_start = 0
T_end = T
T_total = 0
for i in range(1, N):
	if t[i] <= T_end:
		T_end = t[i] + T
	else:
		T_total += T_end - T_start
		T_start = t[i]
		T_end = t[i] + T
T_total += T_end - T_start
print(T_total)


(n, t) = list(map(int, input().split()))
l = list(map(int, input().split()))
s = 0
for i in range(len(l) - 1):
	s += min(t, l[i + 1] - l[i])
s += t
print(s)


(N, T) = map(int, input().split())
N_List = list(map(int, input().split()))
ans = 0
for i in range(1, N):
	ans += (T, N_List[i] - N_List[i - 1])[N_List[i] - N_List[i - 1] <= T]
ans += T
print(ans)


(n, t) = map(int, input().split())
t_lst = list(map(int, input().split()))
accumulate = 0
for i in range(n - 1):
	time = t_lst[i + 1] - t_lst[i]
	accumulate += min(time, t)
accumulate += t
print(accumulate)


(N, T) = map(int, input().split())
t = list(map(int, input().split()))
X = T
for n in range(1, N):
	d = t[n] - t[n - 1]
	if d <= T:
		X += d
	else:
		X += T
print(X)


(n, t) = map(int, input().split())
l = list(map(int, input().split()))
ans = t
for i in range(n - 1):
	ans += min(t, l[i + 1] - l[i])
print(ans)


(N, T) = map(int, input().split())
List = list(map(int, input().split()))
res = 0
for i in range(1, N):
	sumsum = List[i] - List[i - 1]
	if sumsum >= T:
		res += T
	else:
		res += sumsum
res += T
print(res)


(N, T) = map(int, input().split())
time = list(map(int, input().split())) + [float('inf')]
now = 0
prev = 0
ans = 0
for t in time:
	if t - prev >= T:
		ans += T
	else:
		ans += t - prev
	prev = t
print(ans)


(N, T) = list(map(int, input().split()))
t = list(map(int, input().split()))
t.append(float('inf'))
ans = 0
for i in range(len(t) - 1):
	ans += min(T, t[i + 1] - t[i])
print(ans)


numbers = list([int(x) for x in input().split()])
nums = list([int(x) for x in input().split()])
t = numbers[1]
total = t
for i in range(1, len(nums)):
	check = nums[i] - nums[i - 1]
	total += check if check <= t else t
print(total)


from sys import stdin

def main():
	(N, T) = list(map(int, stdin.readline().strip().split()))
	t = list(map(int, stdin.readline().strip().split()))
	x = 0
	for i in range(N - 1):
		x += min(T, t[i + 1] - t[i])
	print(x + T)

def __starting_point():
	main()
__starting_point()


(n, k) = map(int, input().split())
t = list(map(int, input().split()))
ans = n * k
for i in range(1, n):
	diff = k - min(t[i] - t[i - 1], k)
	ans -= diff
print(ans)


(n, T) = list(map(int, input().split()))
t = list(map(int, input().split()))
ans = 0
for (i, j) in zip(t, t[1:]):
	ans += min(j - i, T)
print(ans + T)