60011 가방 Platinum V

문제

상훈이는 가게에서 N개의 물건을 가지고 있으며, 각 물건의 무게는 A_i이다. 도둑은 K개의 물건을 훔쳐갈 예정인데, 훔쳐가는 물건의 무게 합을 최소화하려고 한다. (물건이 K개 미만이면 모두 훔쳐간다)

상훈이는 가방에 무게 합이 x 이하인 물건들을 담아서 들고 간 후, 남은 물건들 중에서 도둑이 K개를 선택한다. 상훈이의 목표는 도둑이 훔쳐가는 물건의 무게 합을 최대화하는 것이다.

모든 x = 1, 2, …, C에 대해 도둑이 훔쳐가는 물건 무게 합의 최댓값을 구하시오.

입력

첫째 줄에 N, K, C가 주어진다. (1 ≤ K ≤ N ≤ 5,000, 1 ≤ C ≤ 1,000,000)

둘째 줄에 N개의 정수 A_1, …, A_N이 주어진다. (1 ≤ A_i ≤ 1,000,000)

출력

C개의 줄에 각각 x = 1, 2, …, C일 때의 답을 출력한다.

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