시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 (언어별 추가 시간 없음) 512 MB 40 24 9 47.368%

문제

사탕 가게에서 특가 상품을 판매한다고 한다. 특가 상품은 한 상자 안에 여러개의 라이언 모양 사탕이 들어 있는 형태이다. 총 N개의 특가 상품이 존재하는데, i번째 특가 상품에는 당도 ai의 사탕 mi개가 들어있으며, 가격은 ci이다.

종영이는 당이 떨어져 여러 특가 상품을 구매해 이를 해결하려고 한다. 1부터 L까지의 모든 k에 대해서, 당도의 합이 k가 되게 사탕을 먹을 수 있게 구매하는 최소의 비용을 구하여라. 한 특가 상품을 구매하면, 그 특가 상품 내의 사탕을 모두 먹을 필요는 없다.

입력

첫 줄에 N과 L이 공백으로 구분되어 주어진다. (1 ≤ N, L ≤ 10000)

N개의 줄에 걸쳐, ai, mi, ci가 공백으로 구분되어 주어진다. (1 ≤ ai, mi, c≤ 10000)

출력

1부터 L까지의 모든 k에 대해서, 당도의 합이 k가 되게 사탕을 먹을 수 있게 구매하는 최소의 비용을 순서대로 공백으로 구분하여 출력한다. 어떠한 k에 대해 가능한 방법이 없을 때에는 대신 −1을 출력하여라.

예제 입력 1

5 20
1 1 5
2 1 2
3 1 3
4 1 7
5 1 6

예제 출력 1

5 2 3 7 5 9 8 9 12 11 15 16 21 18 23 -1 -1 -1 -1 -1 

예제 입력 2

3 10
2 3 1
2 1 2
3 1 3

예제 출력 2

-1 1 3 1 4 1 4 3 4 -1 

출처