28405번 - 안테나 설치

문제

아름다운 도시인 UCPC시에는 총 $N$개의 집이 있으며, 각 집은 일직선 상에 동일한 간격으로 배치되어 있다. 이 도시의 시장으로 새로 취임한 도훈이는 시민들의 원활한 네트워크 연결을 위해 신형 안테나를 설치하려고 한다.

세기가 $x$인 안테나를 설치하면, 연속하는 $l$개의 집에 각각 $x-l+1$만큼의 네트워크 연결 속도가 제공된다. 이때, 네트워크를 제공하는 집의 개수 $l$은 $x$ 이하의 정수로 안테나를 설치할 때 직접 설정할 수 있으며, 안테나마다 서로 다른 값으로 설정하는 것도 가능하다. 단, 기술의 한계로 인해 안테나 하나의 최대 세기는 $P$이며, 전파 간섭을 막기 위해 두 개 이상의 안테나가 같은 집에 네트워크를 제공하지 않도록 안테나를 설치해야 한다.

모든 시민들을 만족시키기 위해, 도훈이는 각 집에서 요구하는 네트워크 연결 속도를 모두 제공해주려 한다. 또한, 도시의 예산을 아끼기 위해 설치하는 안테나의 세기의 합을 최소화하고자 한다. 도훈이를 위해 각 집에서 요구하는 네트워크 연결 속도를 제공하기 위한 안테나 세기의 합의 최솟값을 구해주자.

입력

첫 번째 줄에 도시에 있는 집의 개수 $N$과 안테나 하나의 최대 세기 $P$가 공백으로 구분되어 정수로 주어진다. $(1\leq N\leq 500,円 000;$ 1ドル\leq P\leq 10^9)$

두 번째 줄에 각 집에서 요구하는 네트워크 연결 속도를 나타내는 정수 $a_i$가 공백으로 구분되어 순서대로 주어진다. $(1\leq a_i\leq P)$

출력

모든 집에서 요구하는 네트워크 연결 속도를 제공하기 위한 안테나 세기의 합의 최솟값을 출력한다.

제한

노트

1ドル$번째 집부터 2ドル$번째 집까지 4ドル$의 연결 속도를 제공하는 세기 5ドル$의 안테나를, 3ドル$번째 집부터 5ドル$번째 집까지 3ドル$의 연결 속도를 제공하는 세기 5ドル$의 안테나를, 6ドル$번째 집에 4ドル$의 연결 속도를 제공하는 세기 4ドル$의 안테나를, 7ドル$번째 집에 5ドル$의 연결 속도를 제공하는 세기 5ドル$의 안테나를 설치하면 안테나 세기의 합은 19ドル$로 모든 집의 요구사항을 만족시킬 수 있다.