젤리

시간 제한3초메모리 제한1024 MB

요약

모든 색의 개수가 같도록 사탕을 골라, 전체 무게를 m으로 나눈 나머지가 r인 경우의 최소 가격을 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 최단 경로
정답자: 아직 제출이 없습니다

문제

Bajtek은 젤리를 아주 좋아한다. 새로 문을 연 가게에서는 젤리만 판매하며, 젤리는 n종류가 있다. i번째 종류는 색 k_i, 무게 m_i(바이트그램), 가격 c_i(바이트그로시)로 설명된다. 젤리는 낱개로 팔리고, 각 종류의 재고는 무제한이다. 색은 1부터 k까지의 번호로 나타낸다.

Bajtek은 1부터 k까지 모든 색의 젤리를 같은 개수씩 포함하는 다중집합만 산다. 각 정수 r(범위는 $[0, m-1]$ )에 대해, 총무게를 m으로 나눈 나머지가 r이 되는 다중집합을 사는 데 드는 최소 가격을 구하라.

입력

첫 줄에 세 정수 n, k, m이 주어진다( $1 \le n, k, m \le 7000$ ). 이어지는 n줄에는 각각 세 정수 k_i, m_i, c_i가 주어진다( $1 \le k_i \le k$ , $1 \le m_i \le m$ , $1 \le c_i \le 10^9$ ).

출력

m줄을 출력한다. i번째 줄에는 총무게를 m으로 나눈 나머지가 i-1인 조건을 만족하는 다중집합의 최소 가격을 쓴다. 그런 다중집합이 없으면 -1을 쓴다.

예제2

예제 1
입력
```
3 2 6
1 2 1
2 2 2
1 1 5
```
예상 출력
```
0
10
6
7
3
13
```
예제 2
입력
```
2 3 3
1 1 1
3 1 1
```
예상 출력
```
0
-1
-1
```