계절 이야기

당신은 채소 씨앗과 무한히 넓은 농장을 가진 슈퍼 농부이다. 사실 당신은 농부일 뿐만 아니라 남몰래 슈퍼 프로그래머이기도 하다! 슈퍼 프로그래머로서, 프로그래밍 기술을 활용해 농사 수익을 최대화하려 한다.

하루에 쓸 수 있는 에너지가 제한되어 있으므로, 매일 최대 $\mathbf{X}$개의 씨앗을 심을 수 있다. 처음에는 $\mathbf{N}$종류의 채소 씨앗을 가지고 있다. $i$번째 종류의 채소 씨앗은 $\mathbf{Q_i}$개이며, 이 종류의 씨앗은 각각 심은 날부터 성숙하기까지 $\mathbf{L_i}$일이 필요하다. 성숙하면 $\mathbf{V_i}$달러에 팔 수 있다. 채소를 수확하고 판매하는 데에는 에너지나 시간이 전혀 필요하지 않다고 가정한다. 또한 농장은 무한히 넓으므로 자라는 채소들이 서로의 공간을 차지하지 않는다.

농장의 면적은 무한하지만, 씨앗을 심을 수 있는 날의 수는 제한되어 있음에 유의하라. 따뜻한 계절은 $\mathbf{D}$일 동안만 지속되며, 그 뒤에는 혹독한 겨울이 찾아온다. 아직 성숙하지 않은 채소는 모두 즉시 죽으며 수익으로 바꿀 수 없다. 심지 않고 남은 씨앗 역시 수익으로 바꿀 수 없다.

슈퍼 농부이자 슈퍼 프로그래머인 당신은 수익을 최대화하는 완벽한 파종 계획을 세우려 한다. 얻게 될 총수익을 구하라.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{V_i} \le 10^6$. 모든 $i$에 대해 $1 \le \mathbf{L_i} \le \mathbf{D}$.

테스트 세트 1

시간 제한: 20초. $2 \le \mathbf{D} \le 1000$. $1 \le \mathbf{N} \le 15$. $\mathbf{X} = 1$. 모든 $i$에 대해 $\mathbf{Q_i} = 1$.

테스트 세트 2

시간 제한: 60초. $2 \le \mathbf{D} \le 10^5$. $1 \le \mathbf{N} \le 10^5$. $1 \le \mathbf{X} \le 10^9$. 모든 $i$에 대해 $1 \le \mathbf{Q_i} \le 10^6$.

테스트 세트 3

시간 제한: 60초. $2 \le \mathbf{D} \le 10^{12}$. $1 \le \mathbf{N} \le 10^5$. $1 \le \mathbf{X} \le 10^9$. 모든 $i$에 대해 $1 \le \mathbf{Q_i} \le 10^6$. $\mathbf{D} \times \mathbf{X} \le 10^{18}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 세 정수 $\mathbf{D}$, $\mathbf{N}$, $\mathbf{X}$가 주어진다. 이들은 각각 따뜻한 계절의 일수, 처음에 가지고 있는 채소 씨앗 종류의 수, 매일 심을 수 있는 씨앗의 최대 개수이다. 다음 $\mathbf{N}$개의 줄은 씨앗을 설명한다. $i$번째 줄에는 세 정수 $\mathbf{Q_i}$, $\mathbf{L_i}$, $\mathbf{V_i}$가 주어진다. 이들은 각각 이 종류의 씨앗 수, 성숙하는 데 필요한 일수, 성숙한 식물 하나의 가치이다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며(시작 번호는 1), $y$는 농사 계획을 최적화하여 벌 수 있는 최대 금액이다.

예제 케이스 #1에서는 날이 $\mathbf{D} = 5$일이고 채소가 $\mathbf{N} = 4$종류이며, 매일 최대 $\mathbf{X} = 1$개의 씨앗을 심을 수 있다. $4$종류의 채소가 시금치, 호박, 당근, 양배추라고 가정하면 다음과 같다.

• 시금치는 자라는 데 $2$일이 필요하고, 성숙한 시금치 하나의 가치는 $3$달러이며, 처음에 시금치 씨앗 $1$개를 가지고 있다.

• 호박은 자라는 데 $3$일이 필요하고, 성숙한 호박 하나의 가치는 $10$달러이며, 처음에 호박 씨앗 $1$개를 가지고 있다.

• 당근은 자라는 데 $4$일이 필요하고, 성숙한 당근 하나의 가치는 $5$달러이며, 처음에 당근 씨앗 $1$개를 가지고 있다.

• 양배추는 자라는 데 $2$일이 필요하고, 성숙한 양배추 하나의 가치는 $2$달러이며, 처음에 양배추 씨앗 $1$개를 가지고 있다.

얻을 수 있는 최대 수익은 $18$달러이다. 사용할 수 있는 일정 중 하나는 다음과 같다.

• 1일: 당근 $1$개를 심는다

• 2일: 호박 $1$개를 심는다

• 3일: 시금치 $1$개를 심는다

• 4일: 양배추 $1$개를 심는다

• 5일: 아무것도 하지 않는다

이 일정을 따르면 채소는 다음 날들에 성숙하여 수익이 된다.

• 1일: 아무것도 수확하지 않는다

• 2일: 아무것도 수확하지 않는다

• 3일: 아무것도 수확하지 않는다

• 4일: 아무것도 수확하지 않는다

• 5일: 시금치 $1$개, 호박 $1$개, 당근 $1$개를 수확하여 $18$달러를 번다

양배추는 $6$일에 성숙할 예정이지만, 실제로는 겨울 때문에 죽는다는 점에 유의하라.

추가 예제 - 테스트 세트 2

추가 예제 케이스 #1에서는 날이 $\mathbf{D} = 5$일이고 채소가 $\mathbf{N} = 3$종류이며, 매일 최대 $\mathbf{X} = 4$개의 씨앗을 심을 수 있다. $3$종류의 채소가 시금치, 호박, 당근이라고 가정하면 다음과 같다.

• 시금치는 자라는 데 $2$일이 필요하고, 성숙한 시금치 하나의 가치는 $3$달러이며, 처음에 시금치 씨앗 $5$개를 가지고 있다.

• 호박은 자라는 데 $3$일이 필요하고, 성숙한 호박 하나의 가치는 $10$달러이며, 처음에 호박 씨앗 $2$개를 가지고 있다.

• 당근은 자라는 데 $4$일이 필요하고, 성숙한 당근 하나의 가치는 $5$달러이며, 처음에 당근 씨앗 $2$개를 가지고 있다.

얻을 수 있는 최대 수익은 $45$달러이다. 사용할 수 있는 일정 중 하나는 다음과 같다.

• 1일: 호박 $1$개, 당근 $2$개, 시금치 $1$개를 심는다

• 2일: 시금치 $2$개와 호박 $1$개를 심는다

• 3일: 시금치 $2$개를 심는다

• 4일: 아무것도 하지 않는다

• 5일: 아무것도 하지 않는다

이 일정을 따르면 채소는 다음 날들에 성숙하여 수익이 된다.

• 1일: 아무것도 수확하지 않는다

• 2일: 아무것도 수확하지 않는다

• 3일: 시금치 $1$개를 수확하여 $3$달러를 번다

• 4일: 시금치 $2$개와 호박 $1$개를 수확하여 $16$달러를 번다

• 5일: 시금치 $2$개, 호박 $1$개, 당근 $2$개를 수확하여 $26$달러를 번다