상훈이는 KOI 도시에서 상점을 운영하고 있는 시민이다.

상훈이의 상점은 N개의 물건을 가지고 있으며, 이 중 i번째 물건의 무게는 A_i이다.

상훈이는 도둑 김기범이 본인의 상점을 노리고 있다는 첩보를 들었고, 이에 대비해 피해를 최소화하려고 한다.

도둑 김기범은 가게에서 K개의 물건을 훔쳐갈 것인데, 물건이 무거울 경우 훔쳐가기 어렵고 경찰한테 걸릴 가능성이 높다.

고로, 도둑 김기범은 훔쳐가는 물건의 무게의 합을 최소화한다.

만약 가게에 있는 물건의 개수가 K개 미만일 경우, 도둑 김기범은 가게에 있는 모든 물건을 훔쳐간다.

상훈이는 도둑 김기범이 가게를 도착하기 전에, 가방에 상점의 물건들을 몇 개 담아서 들고 갈 것이다.

이후, 도둑 김기범은 상훈이가 들고 가지 않은 물건들에 대해 위에 설명한 방식으로 범죄를 저지른다.

상훈이는 가방에 물건을 적당히 담아서 도둑 김기범이 훔쳐가는 물건의 무게 합을 최대화하려고 한다.

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

제약 조건

가방 timer 1s memory 1024MB