기업 평판

당신은 방금 회사를 창업했다. 당신은 그 회사가 하는 일이 그다지 인기가 없다는 것을 알고 있다. 앞으로 $n$일 동안 매일 $i$, 당신의 평판은 주어진 값 $r_i$만큼 나빠질 것으로 예상된다. 그런 다음 당신은 평판이 나쁜 정도만큼의 돈도 잃게 된다. 밤에는 회사의 이름을 바꾸어 평판을 초기화할 수 있다. 이는 몇 번이든 할 수 있지만, 고정된 금액 $k$이 든다.

달성할 수 있는 최소 손실은 얼마인가?

점수

당신의 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$12$| $2 \le n \le 20$

$2$ |$17$| $2 \le n \le 1000$

$3$ |$25$| $k \le 1000$, $r_i \le 1000$

$4$ |$23$| 모든 $r_i$이 같다

$5$ |$23$| 추가 제한 없음

첫째 줄에 두 정수 $n$, 그리고 $k$가 주어진다 ($2 \leq n \leq 4 \cdot 10^5$, $0 \leq k \leq 2 \cdot 10^9$). 둘째 줄에 $n$개의 수 $r_i$가 주어진다 ($1 \le r_i \le 10^7$). 이는 $i$일째에 당신의 평판이 당신의 평판이 얼마나 나빠지는지를 나타낸다.

달성할 수 있는 최소 손실을 나타내는 정수 하나를 출력한다.

여기서는 첫째, 둘째, 셋째 날 밤에 총 세 번 이름을 바꾸는 것이 최적이다.

여기서는 15일째와 16일째 사이의 밤에 한 번 이름을 바꾸는 것이 최적이다.