الأعمال#517

الأعمال

ثانية
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. ( نقاط) لا قيود إضافية.