모닝커피 (Large)

코코아는 아침마다 커피를 한 잔 마시면서 하루를 시작한다.

찬장에는 커피가 $N$종류 있다. $i$번 커피는 $c_i$잔 남아 있고, 오늘을 1일째로 두면 $t_i$일째까지 마실 수 있다. 유통기한이 지난 커피는 마실 수 없지만, 딱 $t_i$일째에는 아직 마실 수 있다. 예를 들어 $t_i = 1$이면 그 커피는 오늘 안에 마시거나 버려야 한다.

$i$번 커피를 한 잔 마시면 만족도 $s_i$를 얻는다. 코코아는 하루에 아침 한 번, 한 잔만 마신다. 마실 커피가 남아 있지 않은 날에는 만족도를 얻지 못한다. 1일째부터 $K$일째까지 커피를 마실 때 얻을 수 있는 만족도 합의 최댓값을 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 공백 하나로 구분된 두 양의 정수, 커피의 종류 수 $N$과 계산할 날짜 수 $K$가 주어진다. 이어지는 $N$개의 줄에는 커피 한 종류마다 남은 잔 수, 마실 수 있는 마지막 날, 만족도가 다음 형식으로 주어진다.

ci ti si

값의 범위는 다음과 같다.

• $1 \le T \le 100$
• $1 \le N \le 100$
• $1 \le K \le 2 \times 10^{12}$
• $1 \le c_i \le K$
• $1 \le t_i \le K$
• $1 \le s_i \le 1000$

$K$는 32비트 정수의 범위를 넘을 수 있다.

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case #X: Y

$X$는 1부터 시작하는 테스트 케이스의 번호이고, $Y$는 만족도 합의 최댓값이다.