19756번 - стандартный ввод 다국어

Джон --- фанат сериала <<Во все престолы>>. Совсем скоро выходит новый сезон, и Джон хочет его посмотреть.

Серии будут выходить по одной в день. Джону не хочется скачивать их каждый раз вручную, поэтому он собирается написать программу, которая будет делать это за него. Каждая серия --- это отдельный файл, размер файла, содержащего $i$-ю серию, равен $s_i$ байт.

Программа Джона будет действовать следующим образом. Она один за другим будет отправлять на сервер запросы, где $j$-й запрос представляет собой <<загрузить очередные $x_j$ байт>>. В ответ на такой запрос сервер возвращает пакет данных, содержащий очередные $x_j$ байт файла, а также заголовок, содержащий $k$ байт различной служебной информации. Таким образом, размер пакета равен $x_j+k$ байт, при этом значение $k$ одно и то же для всех запросов.

Когда в результате некоторого запроса скачивается последний байт файла, программа завершает свою работу и не делает дальнейших запросов к серверу. Однако протокол устроен таким образом, что размер пакета равен $x_j+k$, даже если был достигнут конец файла и в действительности было загружено меньше $x_j$ байт полезной информации.

Джон ничего не знает в программировании, поэтому он может написать только простую программу, которая для загрузки каждой серии будет обращаться к серверу с одинаковой последовательностью запросов. Интернет у него медленный, поэтому он хочет, чтобы суммарный размер всех загруженных пакетов был как можно меньше.

Из-за утечки информации от создателей сериала Джону известен размер каждой серии. Помогите ему узнать, какой миниальный суммарный размер пакетов придётся загрузить, чтобы скачать все серии.

В первой строке входного файла заданы целые числа $n$ и $k$ --- количество серий и размер заголовка пакета ($1 \le n \le 10000$; $0 \le k \le 10^9$).

Во второй строке задано $n$ целых чисел $s_i$ --- размеры серий ($1 \le s_i \le 10^9$).

Выведите одно число --- минимальный суммарный размер пакетов, которые придётся загрузить.

В первом примере можно сначала загрузить 200 байт, а затем 600. Тогда первые три серии будут скачаны после первого запроса и на каждую из них будет потрачено по $200 + 1000 = 1200$ байт. Последняя серия будет скачана за два запроса, на нее будет потрачено $(200 + 1000) + (600 + 1000) = 2800$ байт. Итого $1200 + 1200 + 1200 + 2800 = 6400$ байт.

Во втором примере заголовка нет, поэтому можно не бояться делать много запросов. Например, можно загружать блоками по 100 байт.