Biznes#517

Biznes

1 sekunda
256 megabajtów
Trudne

Wkrótce Ben skończy osiemdziesiąt lat, nie ma już żadnych zajęć, więc postanowił otworzyć kolejny biznes. Tym razem umieścił automatów z napojami gazowanymi w najbliższym centrum handlowym i ponumerował je od do . Każdy automat może pomieścić do dolarów, a w niektórych z nich Ben wcześniej umieścił pieniądze, aby wydawać resztę. W szczególności automat o numerze (1 \leq i \leq n) początkowo zawiera a_i dolarów (0 \leq a_i < x).

Przez następne 10^{100} dni, na końcu każdego dnia dzieją się następujące rzeczy:

  1. Liczba pieniędzy w każdym automacie zwiększa się o .

  2. Jeśli po tym zwiększeniu liczba pieniędzy w danym automacie staje się większa lub równa , asystent Bena zabiera z niego wszystkie pieniądze, a w automacie zostaje dolarów.

Jako księgowy Bena, znajdź maksymalną łączną kwotę pieniędzy we wszystkich automatach po dniach dla wszystkich liczb naturalnych (1 \leq t \leq 10^{100}).

Dane wejściowe

Pierwszy wiersz zawiera dwie liczby całkowite (1 \leq n \leq 2 \cdot 10^5, 2 \leq x \leq 10^{12}) — liczba automatów i maksymalna suma pieniędzy w jednym automacie.

Drugi wiersz zawiera liczb całkowitych a_1, a_2, \ldots, a_n (0 \leq a_i < x) — początkową liczbę pieniędzy w każdym automacie.

Dane wyjściowe

Wypisz jedną liczbę całkowitą — maksymalną łączną kwotę pieniędzy we wszystkich automatach po pewnym dniu.

Przykłady

Przykład 1

Loading
Loading

Przykład 2

Loading
Loading

Uwaga

W pierwszym przykładzie po -szym dniu liczba pieniędzy w automatach wynosi (), więc łączna liczba pieniędzy wynosi 1+2+2=5, i jest to maksymalna wartość wśród wszystkich dni.

W drugim przykładzie po -tym dniu liczba pieniędzy w automatach wynosi (2,2,2,5,5,5,6,6), więc łączna liczba pieniędzy wynosi , i jest to maksymalna wartość wśród wszystkich dni. Przykładowa liczba pieniędzy w automatach w innych dniach jest następująca:

  • Po -szym dniu liczba pieniędzy wynosi (6,6,6,2,2,2,3,3), więc łączna liczba pieniędzy wynosi .

  • Po -im dniu liczba pieniędzy wynosi (1,1,1,4,4,4,5,5), więc łączna liczba pieniędzy wynosi .

  • Po -tym dniu liczba pieniędzy wynosi (4,4,4,0,0,0,1,1), więc łączna liczba pieniędzy wynosi .

Punktacja

  1. ( punktów) x = 2;

  2. ( punktów) n \leq 1000, x \leq 1000;

  3. ( punktów) n \leq 100;

  4. ( punktów) x \leq 10^5;

  5. ( punktów) bez dodatkowych ograniczeń.