12019번 - 동아리방 청소!

문제

남규는 동아리 방 관리자이다. 요즘 동아리 방 사용자가 많아지고 동아리 방이 더러워져서 사람들이 불쾌함을 느끼고 있다.

한 사람이 느끼는 불쾌함은 동아리 방의 더러움과 같다. 즉, 동아리 방의 더러움이 3이고 그날 5명이 동아리방에 온다면 5명 모두 불쾌함을 3을 느끼게 되어 그 날 각 사람들이 느낀 불쾌함의 총합은 15가 된다. 그리고 동아리방의 더러움은 사람이 a명 들어오고 나가면 a만큼 증가한다. 그래서 사람들의 불쾌함을 최소로 하기 위해 동아리 방을 청소해야한다.

하지만 남규는 게을러서 총 N일중에 M번만 청소를 하려고 한다. 남규는 최대한 전체 사람들의 불쾌함의 총합이 적도록 청소 계획을 짜려한다.

N일 동안의 들어오는 사람을 미리 알 수 있다고 할 때, 어떻게 청소 하는 것이 불쾌함이 적어질지 남규는 몹시 궁금하다. 처음 시작의 동아리방의 더러움은 0이다.

입력

첫째 줄에는 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ min(10, N))이 주어진다. 그리고 두 번째 줄에는 그 날 출입하는 사람의 수 P_i (1 ≤ P_i ≤ 20)가 N개 주어진다.

출력

첫째 줄에는 N일 까지의 각 사람들이 느낀 불쾌함의 총합의 최솟값을 출력하고 두 번째 줄에는 그 때 청소한 날짜를 오름차순으로 출력한다. 정답이 여러 가지인 경우에는 사전 순으로 앞서는 것을 출력한다. 단, 청소는 항상 그 날 학생들이 다 나가고 난 후 저녁에 한다고 한다.

제한

힌트

N 1 2 3 4 5 6 7 8
더러움(아침) 0 5 13 0 10 11 0 3
불쾌함(당일) 0 40 78 0 10 165 0 27
불쾌함(누적) 0 40 118 118 128 293 293 320