안테나 설치

아름다운 도시 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)$

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

세기 5인 안테나로 1번 집부터 2번 집까지 연결 속도 4를, 3번 집부터 5번 집까지 연결 속도 3을 제공하고, 세기 4인 안테나로 6번 집에 연결 속도 4를, 세기 5인 안테나로 7번 집에 연결 속도 5를 제공한다. 안테나 세기의 합은 19이며, 이로써 모든 집의 요구 사항을 만족시킬 수 있다.