시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 153 37 28 38.356%

문제

요즘 스트레스를 많이 받는 인호에게 돈은 스트레스 해소 그 자체이다. 그 때문인지 인호는 어제 돈을 썼던만큼 오늘 쓰지 못하면, 만 원 단위로 표현한 차액의 제곱만큼 박탈감을 느낀다. 보다 엄밀히 서술하자면 다음과 같다.

만약 i번째 날 지출이 a 만 원, (i+1)번째 날 지출이 b 만 원이었다면, (i+1)번째 날에

  1. ab라면 아무런 박탈감을 느끼지 않는다.
  2. a > b라면 (a - b)2만큼의 박탈감을 느낀다.

인호는 앞으로 N일 동안의 예상 통장 지출 내역을 살펴보고 있다. 인호의 통장에는 예상 지출과 별개로 여유롭게 사용할 수 있는 M 만 원의 돈이 남아있다. 인호는 이 M 만 원을 앞으로의 지출 내역에 효율적으로 분배하여, 앞으로 N일 동안 느낄 박탈감의 합(즉, 내일의 박탈감, 모레의 박탈감, ..., N일 후의 박탈감의 합)을 최소화하고자 한다. 이 통장 잔고의 최소 인출 단위는 만 원이기 때문에, 분배는 만 원 단위로만 할 수 있다. 습하고 더운 날씨 속에서 인호가 박탈감을 덜 받을 수 있게 도와주자.

입력

첫 번째 줄에는 정산할 날짜의 수와 통장 잔고(만 원 단위)를 의미하는 두 자연수 NM이 공백으로 구분되어 주어진다. (1 ≤ N < 1000, 0 ≤ M < 200)

두 번째 줄에는 N일 동안 지출할 예상 비용을 의미하는 N개의 정수 C1, C2, ..., CN가 공백으로 구분되어 주어진다. (0 ≤ Ci ≤ 10)

Cii 번째 날에 지출할 비용이 Ci 만 원임을 의미한다. 0번째 날에 지출한 비용은 0으로 간주한다.

출력

첫 번째 줄에 통장 잔고를 N일간의 예상 지출액에 분배 하여 인호가 앞으로의 N일 동안 느낄 박탈감의 총합의 최솟값을 출력한다.

예제 입력 1

3 1
3 2 1

예제 출력 1

1

인호는 3일동안 각각 3, 2, 1만 원을 지출할 예정이고, 추가로 사용 가능한 잔액 1만 원이 남아있다.

원래는 총 2만큼의 박탈감을 느껴야 하지만 마지막 날에 1만 원을 추가한다면, [3, 2, 2]가 되어 1만큼의 박탈감만을 느끼게 해줄 수 있다 (둘째 날에만 1을 느낀다).

3일 동안만의 박탈감을 따지는 것이기 때문에 4번째 날의 비용을 상정할 필요가 없음에 유의해야 한다.

이와 별개로, 기존의 예상 지출 자체를 재분배할 수는 없다. 예를 들어 [3, 2, 1]을 [2, 2, 2]로 바꾸는 것은 허용되지 않는다.

노트

flex는 본디 구부리다, (준비 운동으로) 몸을 풀다의 뜻을 가지고 있는 영단어인데, 운동하며 나오는 근육을 과시함을 뜻하는 관용구 'flex your muscles'로도 쓰인다.

최근에는 몸풀기로 근육을 자랑하는 게 아니라 돈 등의 물질적인 자원을 자랑하는 은어로 사용되고 있다.