Задача №113320. Сериал
Джон — фанат сериала «Во все престолы». Совсем скоро выходит новый сезон, и Джон хочет его посмотреть.
Серии будут выходить по одной в день. Джону не хочется скачивать их каждый раз вручную, поэтому он собирается написать программу, которая будет делать это за него. Каждая серия — это отдельный файл, размер файла, содержащего \(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 байт.