60011 가방 Platinum V

문제

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

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

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

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

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

입력

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

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

출력

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

제한

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

서브태스크

번호	배점	제한
1	13	$N ≤ 10$, $A ≤ 10\, 000$, $C ≤ 10\, 000$
2	17	$N ≤ 80$, $A ≤ 10\, 000$, $C ≤ 10\, 000$
3	23	$A_i ≤ 10\, 000$, $C ≤ 10\, 000$
4	16	$K = 1$
5	31	추가 제약 조건 없음

5 1 6
1 2 3 4 5

2
2
3
3
3
4

5 2 5
2 3 5 7 11

5
8
8
8
12

3 2 3
1 1 7

8
8
8