시리즈

존은 <<왕좌의 게임>> 시리즈의 팬이다. 곧 새 시즌이 나오고, 존은 이 시즌을 보고 싶어 한다.

에피소드는 하루에 한 편씩 공개된다. 존은 매번 직접 내려받기 싫어서 대신 해 줄 프로그램을 작성하려고 한다. 각 에피소드는 별도의 파일이며, $i$번째 에피소드 파일의 크기는 $s_i$바이트다.

프로그램은 다음과 같이 동작한다. $j$번째 요청은 다음 $x_j$바이트를 내려받으라는 뜻이다. 서버는 이 요청에 대해 파일의 다음 $x_j$바이트와 $k$바이트의 부가 정보(헤더)를 담은 패킷을 돌려준다. 따라서 패킷의 크기는 $x_j+k$바이트이고, $k$는 모든 요청에서 같다.

어떤 요청에서 파일의 마지막 바이트를 내려받으면 프로그램은 종료되고 더 이상 요청을 보내지 않는다. 다만 프로토콜상 파일 끝에 도달해 실제 유효 데이터가 $x_j$바이트보다 적더라도 패킷 크기는 여전히 $x_j+k$바이트다.

존은 프로그래밍을 잘 모른다. 그래서 모든 에피소드를 같은 요청 순서로 내려받는 단순한 프로그램만 쓸 수 있다. 인터넷 속도가 느리므로, 내려받는 패킷들의 전체 크기 합이 최소가 되기를 원한다.

제작진의 정보 유출 덕분에 존은 각 에피소드의 크기를 알고 있다. 모든 에피소드를 내려받는 데 필요한 패킷 크기 합의 최솟값을 구하시오.

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

둘째 줄에는 각 에피소드의 크기 $s_i$가 $n$개 주어진다($1 \le s_i \le 10^9$).

모든 에피소드를 내려받는 데 필요한 패킷 크기 합의 최솟값을 한 줄에 출력한다.

첫 번째 예시에서는 먼저 200바이트를 요청하고, 그다음 600바이트를 요청할 수 있다. 그러면 처음 세 에피소드는 첫 요청으로 내려받아 각각 $200+1000=1200$바이트가 든다. 마지막 에피소드는 요청 두 번으로 받아 $(200+1000)+(600+1000)=2800$바이트가 든다. 합계는 $1200+1200+1200+2800=6400$바이트다.

두 번째 예시에는 헤더가 없으므로 요청을 많이 보내도 괜찮다. 예를 들어 100바이트씩 나누어 요청할 수 있다.