/ 
実行時間制限: 1 sec / メモリ制限: 256 MB
配点：200 点
問題文
E869120 は, AtCoder 回転寿司という店に行った.
この店には, N 個の寿司がある. 寿司にはそれぞれ 1, 2, 3, \cdots, N の番号がつけられている. 寿司 i は, 彼が来店してから a_i+kT 秒後 (k は 0 以上の整数) のみに取ることができる.
彼は, 寿司 1 → 寿司 2 → … → 寿司 N という順番で食べたいと思っている. しかし, 彼は貪欲なので, 寿司を一度取ってしまうとすぐに食べてしまう. 彼が N 個の寿司を食べ終わるまで, 来店してから最短何秒かかるか求めよ. ただし, 寿司を取る時間・食べる時間は無視して良いものとし, 彼は来店して 0 秒後に来る寿司も取ることができるものとする.
入力
入力は以下の形式で標準入力から与えられる.
N T a_1 a_2 a_3 ... a_N
出力
全ての寿司を決められた順番で食べるとき, 食べ終わるまでにかかる最短の秒数を出力せよ.
制約
- N は 1 以上 100 以下の整数.
- T は 1 以上 100 以下の整数.
- a_i は 0 以上 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