회사 평판

시간 제한1초메모리 제한1024 MB

요약

매일 누적되는 평판 악화 수치와 하룻밤에 누적값을 0으로 되돌리는 고정 비용이 주어질 때, 잃는 돈의 최솟값을 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그리디, 누적 합, 수학
정답자: 아직 제출이 없습니다

문제

당신은 방금 회사를 세웠다. 그 회사가 하는 일이 그다지 인기가 없다는 것을 알고 있다. 앞으로 $n$ 일 동안, 매일 $i$ 일에 당신의 평판은 주어진 값 $r_i$ 만큼 나빠질 것이다. 그러면 당신은 그날 평판이 나쁜 만큼 돈을 잃는다. 밤에는 회사 이름을 바꿔 평판을 0으로 되돌릴 수 있다. 이는 몇 번이든 할 수 있지만, 고정된 비용 $k$ 가 든다.

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

입력

첫째 줄에 두 정수 $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^6$ ). 이는 $i$ 일째에 당신의 평판이 얼마나 나빠지는지를 나타낸다.

출력

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

예제2

예제 1
입력
```
5 3
5 4 3 2 1
```
예상 출력
```
26
```

예제 2

입력

30 999999999
10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000

예상 출력

3399999999