A - バスの出発時刻 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 233 点

問題文

高橋君は遠足の引率教員として、すべての生徒がバスに乗り込んだ後に出発の合図を出す役割を担っています。

この遠足には N 人の生徒が参加しており、各生徒 i (1 \leq i \leq N) は時刻 T_i にバスへの乗り込みを完了します。ここで、時刻はある基準時点からの経過時間を分単位の非負整数で表したものです。

すべての生徒がバスに乗り込み終わるのは、T_1, T_2, \ldots, T_N の最大値の時刻です。高橋君は、その時刻からちょうど K 分後に出発の合図を出すことになっています。

高橋君が出発の合図を出す時刻を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq K \leq 10^4
  • 0 \leq T_i \leq 10^9 (1 \leq i \leq N)
  • T_1, T_2, \ldots, T_N は昇順とは限らず、同じ値が複数含まれることもある
  • 入力はすべて整数

入力

N K
T_1 T_2 \ldots T_N
  • 1 行目には、生徒の人数を表す整数 N と、すべての生徒が乗り込み終わってから出発の合図を出すまでの時間（分）を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各生徒 i がバスへの乗り込みを完了する時刻を表す整数 T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。

出力

高橋君が出発の合図を出す時刻を、基準時点からの経過時間（分）を表す整数として 1 行に出力せよ。

入力例 1

3 5
10 25 15

出力例 1

30

入力例 2

5 10
100 50 200 150 75

出力例 2

210

入力例 3

8 1000
500000000 123456789 999999999 1 0 876543210 500000001 999999998

出力例 3

1000000999

Score : 233 pts

Problem Statement

Takahashi is a chaperone teacher on a field trip, and his role is to give the departure signal after all students have boarded the bus.

There are N students participating in this field trip, and each student i (1 \leq i \leq N) finishes boarding the bus at time T_i. Here, time is represented as a non-negative integer in minutes, measuring the elapsed time from a certain reference point.

All students finish boarding the bus at the time equal to the maximum value among T_1, T_2, \ldots, T_N. Takahashi is supposed to give the departure signal exactly K minutes after that time.

Find the time at which Takahashi gives the departure signal.

Constraints

  • 1 \leq N \leq 10^5
  • 0 \leq K \leq 10^4
  • 0 \leq T_i \leq 10^9 (1 \leq i \leq N)
  • T_1, T_2, \ldots, T_N are not necessarily in ascending order, and may contain duplicate values
  • All input values are integers

Input

N K
T_1 T_2 \ldots T_N
  • The first line contains an integer N representing the number of students and an integer K representing the time in minutes from when all students finish boarding until the departure signal is given, separated by a space.
  • The second line contains integers T_1, T_2, \ldots, T_N representing the time at which each student i finishes boarding the bus, separated by spaces.

Output

Print the time at which Takahashi gives the departure signal, as an integer representing the elapsed time in minutes from the reference point, on a single line.

Sample Input 1

3 5
10 25 15

Sample Output 1

30

Sample Input 2

5 10
100 50 200 150 75

Sample Output 2

210

Sample Input 3

8 1000
500000000 123456789 999999999 1 0 876543210 500000001 999999998

Sample Output 3

1000000999