Problem description

W tym roku komitet główny Bitockiej Olimpiady Informatycznej Juniorów postanowił ustawić wielki wyświetlacz, na którym pokazane zostaną wyniki wszystkich zawodników, również Twoje. W trakcie zawodów do pokonania będzie N zadań wartych odpowiednio w₁, …, w_N punktów. Ponadto, każde zadanie można rozwiązać jedynie w pełni poprawnie lub błędnie, co skutkuje tym, że za i-te zadanie możesz otrzymać dokładnie 0 lub dokładnie w_i punktów. Twoim wynikiem w zawodach jest suma zdobytych punktów.

Zauważyłeś, że wyświetlacz jest zepsuty – jeżeli wynik danego zawodnika dzieli się przez K, wyświetlacz zawsze pokaże, że dany zawodnik otrzymał 0 punktów! Chcesz tego uniknąć za wszelką cenę w swoim przypadku (co pomyślą sobie koledzy, kiedy zobaczą 0 przy Twoim nazwisku?). Zastanawiasz się, jaki jest najwyższy możliwy do osiągnięcia wynik, który poprawnie wyświetli się na wyświetlaczu?

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz K. W następnym wierszu znajduje się N liczb naturalnych w₁, …, w_N.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę oznaczającą największy możliwy wynik, który poprawnie wyświetli się na wyświetlaczu.

Ograniczenia

1 ≤ N ≤ 1 000 000, 1 ≤ K ≤ 10⁹, 1 ≤ w_i ≤ 10⁹ dla i = 1, …, N.

Podzadania

Każde podzadanie odpowiada jednej grupie testowej spełniającej warunki podzadania.

Przykład

3 10
10 15 20

45

2 5
15 25

0