가방

상훈이는 KOI 도시에서 상점을 운영하고 있는 시민이다. 상훈이의 상점은 $N$개의 물건을 가지고 있으며, 이 중 $i$번째 물건의 무게는 $A_i$이다. 상훈이는 도둑 김기범이 본인의 상점을 노리고 있다는 첩보를 들었고, 이에 대비해 피해를 최소화하려고 한다.

도둑 김기범은 가게에서 $K$개의 물건을 훔쳐갈 것인데, 물건이 무거울 경우 훔쳐가기 어렵고 경찰한테 걸릴 가능성이 높다. 고로, 도둑 김기범은 훔쳐가는 물건의 무게의 합을 최소화한다. 만약 가게에 있는 물건의 개수가 $K$개 미만일 경우, 도둑 김기범은 가게에 있는 모든 물건을 훔쳐간다.

상훈이는 도둑 김기범이 가게를 도착하기 전에, 가방에 상점의 물건들을 몇 개 담아서 들고 갈 것이다. 이후, 도둑 김기범은 상훈이가 들고 가지 않은 물건들에 대해 위에 설명한 방식으로 범죄를 저지른다. 상훈이는 가방에 물건을 적당히 담아서 도둑 김기범이 훔쳐가는 물건의 무게 합을 최대화하려고 한다.

상훈이의 가방이 감당할 수 있는 무게는 한정되어 있다. 입력으로 최댓값 $C$가 주어졌을 때, 모든 $x = 1, 2, \ldots, C$에 대해 다음 질문에 답하라:

• 상훈이가 가방에 담을 수 있는 물건들의 무게 합이 $x$ 이하여야 한다는 조건하에, 도둑 김기범이 훔쳐가는 물건들의 무게 합의 최댓값은 얼마인가?

• 주어지는 모든 수는 정수이다.
• $1 \le K \le N \le 5\,000$
• $1 \le C \le 1\,000\,000$
• 모든 $i$ ($1 \le i \le N$) 에 대해 $1 \le A_i \le 1\,000\,000$

1. (13점) $N \le 10, A_i \le 10\,000, C \le 10\,000$
2. (17점) $N \le 80, A_i \le 10\,000, C \le 10\,000$
3. (23점) $A_i \le 10\,000, C \le 10\,000$
4. (16점) $K = 1$
5. (31점) 추가 제약 조건 없음

첫 번째 줄에 $N, K, C$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N$ 개의 정수 $A_1, A_2, \ldots, A_N$이 공백으로 구분되어 주어진다.

$C$ 개의 줄을 출력한다. $i$ 번째 줄에는, $x = i$일 때 도둑 김기범이 훔쳐가는 물건들의 무게 합의 최댓값을 출력한다.