시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 271 95 82 34.167%

문제

방학동안 기숙사에 홀로 남겨진 인호는 우울하고 고독하다. 다행히 인호는 M일의 방학 동안 N개의 약속이 잡혀있기에, 약속 날짜의 효율적인 배치를 통해 방학 내에 느낄 우울함의 합을 최소화하려고 한다.

인호의 기분은 정수로 표현 가능하며, 기분이 0 미만인 날에 (기분)2 만큼 우울함을 느낀다. 인호의 기분은 오늘 약속이 있다면 약속의 기대행복 값인 Hi이며, 약속이 없으면 어제의 기분에서 1을 뺀 값이다.

인호는 하루에 최대 한 개의 약속을 소화할 수 있으며, N개의 약속들의 순서는 주어진 순서대로여야 한다.

방학은 내일부터 시작이며, 오늘 인호의 기분은 0일 때, 약속을 적절히 배치하여 인호가 방학 동안 느낄 우울함의 합을 최소화하자.

입력

첫 번째 줄에는 인호의 약속 개수인 자연수 N과 방학의 일수인 자연수 M이 공백으로 구분되어 주어진다. (0 ≤ N < M < 1000)

두 번째 줄에는 N개의 정수 H1, H2, ..., HN이 공백으로 구분되어 주어진다. Hii 번째 약속의 기대행복 값이다. (1 ≤ Hi < 100)

출력

첫 번째 줄에 인호가 방학 동안 느낄 우울함의 합의 최솟값을 출력한다.

예제 입력 1

3 10
2 2 1

예제 출력 1

2

1일, 5일, 8일에 약속을 순서대로 배치하면, 4일과 10일에 각각 1만큼의 우울함을 느끼게 되어, 총 2만큼의 우울함을 느끼게 된다. 이보다 덜 우울함을 느끼게 만드는 방법은 존재하지 않는다.