시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 41 3 3 12.500%

문제

호토 코코아(이하, 코코아)는 아침의 하루를 커피를 마시는 것으로 시작한다.

코코아의 찬장에는 N 종류의 커피가 있고, i번의 커피는 ci 잔 분이 남아있으며, 오늘부터 유통기한까지 ti 일 남았다. 그녀는 i번 (1 ≤ i ≤ N) 종류의 커피를 1잔 마시면, si만큼의 만족도를 얻는다. 유통기한이 지난 커피는 마실 수 없다. (그러나, 딱 ti일째에는 그 커피를 마실 수 있다.)

예를 들어, ti=1인 경우, 오늘 중에 그 커피를 마시던가, 버리던가 해야 한다.

코코아는 커피를 하루에 한잔, 아침에밖에 마시지 않는다. 찬장에 커피가 하나도 없으면, 만족도를 얻을수 없다. 오늘부터 시작해서 커피를 마시는 것으로, K일에 코코아가 얻을수 있는 만족도 합계의 최대를 구하라.

입력

입력의 제일 첫 줄은 테스트케이스 T이다, 그 뒤로 T개의 테스트 케이스가 입력된다. 각각의 테스트케이스는 1개의 공백으로 구분된 2개의 양의 정수가 포함된 행으로 시작한다.  첫 정수는 커피의 종류 N을 의미하며, 다음 정수는 최대로 얻을 수 있는 만족도를 계산할 날짜인 K를 의미한다. 그 뒤에 N개의 커피 종류에 대한 남아있는 커피 갯수, 유통기한, 만족도를 아래의 포맷으로 입력받는다.

ci ti si

값의 범위

  • 1 ≤ T ≤ 100
  • 1 ≤ ci ≤ K
  • 1 ≤ ti ≤ K
  • 1 ≤ si ≤ 1000
  • 1 ≤ N ≤ 100
  • 1 ≤ K ≤ 2 * 1012 (32bit 정수형을 초과하는 것에 주의)

출력

각 테스트 케이스마다

Case #X: Y

을 1행씩 출력한다, X는 테스트 케이스의 번호, Y는 만족도 합계의 최대를 표시한다.

예제 입력

3
2 3
2 2 2
3 3 1
2 3
1 3 2
1 3 1
5 5
5 5 1
4 4 2
3 3 3
2 2 4
1 1 5

예제 출력

Case #1: 5
Case #2: 3
Case #3: 15

힌트