에피소드 다운로드

Джон은 <<왕좌의 모든 것>>이라는 드라마의 팬이다. 곧 새 시즌이 공개될 예정이고, Джон은 그것을 보고 싶어 한다.

에피소드는 하루에 하나씩 공개된다. Джон은 매번 직접 내려받는 것이 귀찮아서, 대신 내려받아 줄 프로그램을 작성하려고 한다. 각 에피소드는 별도의 파일이고, $i$번째 에피소드가 담긴 파일의 크기는 $s\_i$바이트이다.

Джон의 프로그램은 다음과 같이 동작한다. 서버에 요청을 하나씩 보내는데, $j$번째 요청은 <<다음 $x\_j$바이트를 내려받기>>이다. 이런 요청에 대한 응답으로 서버는 파일의 다음 $x\_j$바이트가 담긴 데이터 패킷과 $k$바이트의 각종 부가 정보가 담긴 헤더를 보낸다. 따라서 패킷의 크기는 $x\_j+k$바이트이고, $k$의 값은 모든 요청에서 동일하다.

어떤 요청의 결과로 파일의 마지막 바이트까지 내려받으면, 프로그램은 작업을 끝내고 서버에 더 이상 요청을 보내지 않는다. 하지만 프로토콜 구조상 파일의 끝에 도달해 실제로 내려받은 유효 정보가 $x\_j$바이트보다 적더라도 패킷의 크기는 $x\_j+k$이다.

Джон은 프로그래밍을 전혀 몰라서, 각 에피소드를 내려받을 때 서버에 항상 같은 요청 순서를 보내는 단순한 프로그램만 작성할 수 있다. 인터넷이 느려서 그는 내려받은 모든 패킷 크기의 합이 가능한 한 작기를 원한다.

제작진의 정보 유출 덕분에 Джон은 각 에피소드의 크기를 알고 있다. 모든 에피소드를 내려받기 위해 내려받아야 할 패킷 크기의 최소 합을 구하도록 도와주자.

첫째 줄에 정수 $n$과 $k$가 주어진다. $n$은 에피소드의 수, $k$는 패킷 헤더의 크기이다 ($1 \le n \le 10000$; $0 \le k \le 10^9$).

둘째 줄에 $n$개의 정수 $s\_i$가 주어진다. $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바이트씩 블록으로 내려받을 수 있다.