Biznes#517

Biznes

1 saniyə
256 meqabayt
Hard

Səksən yaşına yaxınlaşan cənab Ben etməli işləri bitirdiyi üçün yeni bir biznes açmağa qərar verdi. Bu dəfə o, ən yaxın ticarət mərkəzində soda maşını yerləşdirdi, 1-dən -ə qədər nömrələndi. Hər bir soda maşını maksimum dollar saxlaya bilər və bəzilərində cənab Ben artıq dəyişiklik vermək üçün bir az pul qoymuşdur. Xüsusilə, nömrəli soda maşınında (1 \leq i \leq n) artıq a_i (0 \leq a_i < x) pul var.

Gələcək 10^{100} gün ərzində, hər günün sonunda aşağıdakılar baş verir:

  1. Hər soda maşınındakı pul miqdarı artır.

  2. Əgər artırmadan sonra soda maşınındakı pul miqdarı -dən az olmayacaqsa, cənab Benin köməkçisi bu maşından bütün pulu çıxaracaq, beləliklə, o, dollar olacaq.

Cənab Benin mühasibi olaraq, indi sizin işiniz günündən sonra bütün soda maşınlarında olan maksimum pul miqdarını tapmaqdır, burada tam ədədi (1 \leq t \leq 10^{100}).

Input

Girişin birinci sətrində iki tam ədəd (1 \leq n \leq 2 \cdot 10^5, 2 \leq x \leq 10^{12}) — soda maşınlarının sayı və maksimum pul tutumu, müvafiq olaraq.

Girişin ikinci sətrində tam ədəd a_1, a_2, \ldots, a_n (0 \leq a_i < x) — hər soda maşınındakı ilkin pul miqdarı.

Output

Bir tam ədəd çıxarın — müəyyən bir gündən sonra bütün soda maşınlarında olan maksimum pul miqdarı.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Birinci nümunədə, -ci gündən sonra maşınlardakı pul miqdarları () olur, beləliklə, ümumi pul 1+2+2=5 olur ki, bu da bütün günlərdə maksimumdur.

İkinci nümunədə, -cü gündən sonra maşınlardakı pul miqdarları (2,2,2,5,5,5,6,6) olur, beləliklə, ümumi pul olur ki, bu da bütün günlərdə maksimumdur. Məsələn, digər günlərdə maşınlardakı pul miqdarları aşağıdakılardır:

  • -ci gündən sonra pul miqdarları (6,6,6,2,2,2,3,3) olur, beləliklə, ümumi pul olur.

  • -cü gündən sonra pul miqdarları (1,1,1,4,4,4,5,5) olur, beləliklə, ümumi pul olur.

  • -cı gündən sonra pul miqdarları (4,4,4,0,0,0,1,1) olur, beləliklə, ümumi pul olur.

Scoring

  1. ( bal) x = 2;

  2. ( bal) n \leq 1000, x \leq 1000;

  3. ( bal) n \leq 100;

  4. ( bal) x \leq 10^5;

  5. ( bal) əlavə məhdudiyyət yoxdur.