우울한 방학
면접 대비시간 제한1초메모리 제한512 MB
M일의 방학 동안 순서가 정해진 N개의 약속을 배치해 우울감 제곱의 합이 최소가 되도록 한다. 약속이 없는 날에는 기분이 1씩 줄어든다.
문제
방학 동안 기숙사에 홀로 남은 인호는 우울하고 고독하다. 다행히 인호에게는 M일의 방학 동안 N개의 약속이 잡혀 있으므로, 약속 날짜를 효율적으로 배치해 방학 동안 느낄 우울함의 합을 최소화하려고 한다.
인호의 기분은 정수로 나타낼 수 있다. 기분이 0 미만인 날에 인호는 (기분)2만큼 우울함을 느낀다. 오늘 약속이 있다면 인호의 기분은 그 약속의 기대행복 값 Hi이고, 약속이 없으면 어제의 기분에서 1을 뺀 값이다.
인호는 하루에 최대 한 개의 약속을 소화할 수 있으며, N개의 약속은 주어진 순서대로 소화해야 한다.
방학은 내일부터 시작하고 오늘 인호의 기분은 0일 때, 약속을 적절히 배치해 인호가 방학 동안 느낄 우울함의 합을 최소화하자.
입력
첫 번째 줄에는 인호의 약속 개수인 음이 아닌 정수 N과 방학의 일수인 자연수 M이 공백으로 구분되어 주어진다. (0 ≤ N < M < 1000)
두 번째 줄에는 N개의 정수 H1, H2, ..., HN이 공백으로 구분되어 주어진다. Hi는 i 번째 약속의 기대행복 값이다. (1 ≤ H**i < 100)
출력
첫 번째 줄에 인호가 방학 동안 느낄 우울함의 합의 최솟값을 출력한다.