Affaires#517

Affaires

1 seconde
256 mégaoctets
Hard

Approchant de ses quatre-vingts ans, M. Ben n'avait plus rien à faire, alors il a décidé d'ouvrir une autre entreprise. Cette fois, il a placé distributeurs de soda dans le centre commercial le plus proche, numérotés de à . Chacun des distributeurs de soda peut contenir jusqu'à dollars, et dans certains d'entre eux, M. Ben a déjà mis de l'argent pour rendre la monnaie. En particulier, le distributeur de soda numéro (1 \leq i \leq n) a déjà a_i (0 \leq a_i < x) en espèces.

Pour les prochains 10^{100} jours, à la fin de chaque jour, les événements suivants se produisent :

  1. Le montant d'argent dans chaque distributeur de soda augmente de .

  2. Si, après l'augmentation, le montant d'argent dans un distributeur de soda atteint au moins , alors l'assistant de M. Ben retirera tout l'argent de ce distributeur, le ramenant à dollars.

En tant que comptable de M. Ben, votre tâche est maintenant de trouver le montant total maximal d'argent contenu dans tous les distributeurs de soda après jours, pour un certain entier (1 \leq t \leq 10^{100}).

Input

La première ligne de l'entrée contient deux entiers (1 \leq n \leq 2 \cdot 10^5, 2 \leq x \leq 10^{12}) — le nombre de distributeurs de soda et la capacité maximale de liquidités, respectivement.

La deuxième ligne de l'entrée contient entiers a_1, a_2, \ldots, a_n (0 \leq a_i < x) — le montant initial d'argent dans chaque distributeur de soda.

Output

Affichez un seul entier — le montant total maximal d'argent contenu dans tous les distributeurs de soda après un certain jour.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Dans le premier exemple, après le jour , les montants d'argent dans les machines sont (), donc le total d'argent est 1+2+2=5, ce qui est le maximum sur tous les jours.

Dans le deuxième exemple, après le jour , les montants d'argent dans les machines sont (2,2,2,5,5,5,6,6), donc le total d'argent est , ce qui est le maximum sur tous les jours. Par exemple, après d'autres jours, les montants d'argent dans les machines sont les suivants :

  • Après le jour , les montants d'argent sont (6,6,6,2,2,2,3,3), donc le total d'argent est .

  • Après le jour , les montants d'argent sont (1,1,1,4,4,4,5,5), donc le total d'argent est .

  • Après le jour , les montants d'argent sont (4,4,4,0,0,0,1,1), donc le total d'argent est .

Scoring

  1. ( points) x = 2;

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

  3. ( points) n \leq 100;

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

  5. ( points) aucune restriction supplémentaire.