Բիզնես#517

Բիզնես

1 վայրկյան
256 մեգաբայթ
Hard

Ութսուններին մոտեցող պարոն Բենը ավարտեց անելիքները, ուստի որոշեց բացել նոր բիզնես: Այս անգամ նա տեղադրեց սոդայի մեքենաներ ամենամոտ առևտրի կենտրոնում, որոնք թվագրված են -ից -ը: Յուրաքանչյուր սոդայի մեքենա կարող է պահել մինչև դոլար, և դրանցից որոշներում պարոն Բենն արդեն դրել է որոշ գումար, որպեսզի վերադարձնի փոխարենը: Հատկապես, համարի սոդայի մեքենայում (1 \leq i \leq n) արդեն կա a_i (0 \leq a_i < x) գումար:

Հաջորդ 10^{100} օրերի ընթացքում, յուրաքանչյուր օրվա վերջում տեղի է ունենում հետևյալը:

  1. Յուրաքանչյուր սոդայի մեքենայի մեջ գտնվող գումարը ավելանում է -ով:

  2. Եթե ավելացումից հետո սոդայի մեքենայի մեջ գտնվող գումարը դառնում է առնվազն , ապա պարոն Բենի օգնականը դուրս է բերում այդ մեքենայից ողջ գումարը, այնպես որ այն դառնում է դոլար:

Որպես պարոն Բենի հաշվապահ, ձեր աշխատանքն է գտնել բոլոր սոդայի մեքենաներում առկա առավելագույն գումարը օրերից հետո, որոշակի ամբողջ թիվ -ի համար (1 \leq t \leq 10^{100}):

Input

Մուտքի առաջին տողում կա երկու ամբողջ թիվ (1 \leq n \leq 2 \cdot 10^5, 2 \leq x \leq 10^{12}) — սոդայի մեքենաների քանակը և առավելագույն գումարի տարողությունը, համապատասխանաբար:

Մուտքի երկրորդ տողում կա ամբողջ թիվ a_1, a_2, \ldots, a_n (0 \leq a_i < x) — յուրաքանչյուր սոդայի մեքենայի մեջ սկզբնական գումարը:

Output

Արդյունքում տպեք մեկ ամբողջ թիվ — բոլոր սոդայի մեքենաներում առկա առավելագույն գումարը ինչ-որ քանակի օրերից հետո:

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Առաջին օրինակում, առաջին օրվա վերջում մեքենաների մեջ գումարները կազմում են (), այնպես որ ընդհանուր գումարը 1+2+2=5 է, որը առավելագույնն է բոլոր օրերի համար:

Երկրորդ օրինակում, չորրորդ օրվա վերջում մեքենաների մեջ գումարները կազմում են (2,2,2,5,5,5,6,6), այնպես որ ընդհանուր գումարը է, որը առավելագույնն է բոլոր օրերի համար: Օրինակ, այլ օրերի վերջում մեքենաների մեջ գումարները հետևյալն են.

  • Առաջին օրվա վերջում գումարները կազմում են (6,6,6,2,2,2,3,3), այնպես որ ընդհանուր գումարը է:

  • Երրորդ օրվա վերջում գումարները կազմում են (1,1,1,4,4,4,5,5), այնպես որ ընդհանուր գումարը է:

  • Վեցերորդ օրվա վերջում գումարները կազմում են (4,4,4,0,0,0,1,1), այնպես որ ընդհանուր գումարը է:

Scoring

  1. ( միավոր) x = 2;

  2. ( միավոր) n \leq 1000, x \leq 1000;

  3. ( միավոր) n \leq 100;

  4. ( միավոր) x \leq 10^5;

  5. ( միավոր) լրացուցիչ սահմանափակումներ չկան.