A - Sushi 2

Time Limit: 1 sec / Memory Limit: 256 MB

配点:200

問題文

E869120 は, AtCoder 回転寿司という店に行った.
この店には, N 個の寿司がある. 寿司にはそれぞれ 1, 2, 3, \cdots, N の番号がつけられている. 寿司 i は, 彼が来店してから a_i+kT 秒後 (k0 以上の整数) のみに取ることができる.

彼は, 寿司 1 → 寿司 2 → … → 寿司 N という順番で食べたいと思っている. しかし, 彼は貪欲なので, 寿司を一度取ってしまうとすぐに食べてしまう. 彼が N 個の寿司を食べ終わるまで, 来店してから最短何秒かかるか求めよ. ただし, 寿司を取る時間・食べる時間は無視して良いものとし, 彼は来店して 0 秒後に来る寿司も取ることができるものとする.

入力

入力は以下の形式で標準入力から与えられる.

N T
a_1 a_2 a_3 ... a_N

出力

全ての寿司を決められた順番で食べるとき, 食べ終わるまでにかかる最短の秒数を出力せよ.


制約

  • N1 以上 100 以下の整数.
  • T1 以上 100 以下の整数.
  • a_i0 以上 T-1 以下の整数 (1 \leq i \leq N).
  • 1 \leq i < j \leq N に対し, a_i \neq a_j.

小課題

小課題 1 [100 点]

  • N = 1.

小課題 2 [100 点]

  • 追加の制約はない.

入力例 1

1 6
4

出力例 1

4

この場合, 寿司 1 は来店してから 4, 10, 16, 22, 28, \cdots 秒後に取ることができる. 一番早いのは 4 秒後である.


入力例 2

3 10
3 7 2

出力例 2

12

寿司 1, 2, 3 をそれぞれ 3, 7, 12 秒後に取るのが最短である.


入力例 3

6 15
8 6 9 1 2 0

出力例 3

45

配点:200

Problem Statement

E869120 went to a famous sushi restaurant: "AtCoder Kuru-kuru Sushi".
In this restaurant, N sushi is being sold. They are conveniently numbered 1 through N. He can pick sushi i at a_i+kT (k is non-negative integer) seconds after he came at "AtCoder Kuru-kuru Sushi". (Note that he can also pick a sushi right after he came)

He want to eat N sushi in ascending order: from sushi 1 to sushi N. In addition, since his eating speed is very fast, he can eat a sushi in 0 second. Moreover, he always eat sushi immediately when he pick a sushi because he is greedy.
How many seconds are needed to eat all sushi in order?

Input

Input is given from Standard Input in the following format:

N T
a_1 a_2 a_3 ... a_N

Output

Print the minimum number of seconds to eat all sushi in ascending order.


Constraints

  • 1 \leq N \leq 100
  • 1 \leq T \leq 100
  • 0 \leq a_i \leq T-1
  • a_i \neq a_j (i \neq j)
  • All input values are integers.

Subtasks

Subtask 1 [100 points]

  • N = 1

Subtask 2 [100 points]

  • There are no additional constraints.

Sample Input 1

1 6
4

Sample Output 1

4

He can pick sushi 1 at 4, 10, 16, 22, \cdots seconds after he came at the restaurant.
If he pick sushi 1 at 4 seconds after he came, he can eat all sushi in ascending order in 4 seconds!


Sample Input 2

3 10
3 7 2

Sample Output 2

12

He can pick and eat sushi 1 at 3 seconds, sushi 2 at 7 seconds, sushi 3 at 12 seconds after he came at the restaurant.
Also, he can pick sushi 3 at 2 seconds after he came, but because he is greed, he eat the sushi immediately. So to eat sushi in ascending order, it took at least 12 seconds.


Sample Input 3

6 15
8 6 9 1 2 0

Sample Output 3

45