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:
Liczba pieniędzy w każdym automacie zwiększa się o .
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}).
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.
Wypisz jedną liczbę całkowitą — maksymalną łączną kwotę pieniędzy we wszystkich automatach po pewnym dniu.
Przykład 1
Przykład 2
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 .
( punktów) x = 2;
( punktów) n \leq 1000, x \leq 1000;
( punktów) n \leq 100;
( punktów) x \leq 10^5;
( punktów) bez dodatkowych ograniczeń.