햄스터

헥토르(Hektor)의 햄스터는 여러 세대에 걸쳐 독특한 식습관을 이어 온 시리아 햄스터 명문가 출신입니다. 이 햄스터는 하루에 오직 한 끼만 먹으며, 한 끼는 한 종류의 먹이로만 이루어집니다.

헥토르는 햄스터를 위해 $N$가지 먹이를 준비했습니다. 그는 개봉한 봉지를 여러 개 두는 것을 싫어해서, 지금 열려 있는 봉지를 다 먹거나 버리기 전에는 새 봉지를 열지 않습니다. 각 먹이는 세 개의 수로 표현됩니다: 며칠 뒤에 상하는지, 몇 끼를 먹을 수 있는지, 그리고 그 먹이의 품질입니다.

어떤 먹이가 $p$끼 분량이고 $q$일째에 개봉되면, (그 전에 상하지 않는 한) $p + q - 1$일째 식사를 마친 직후에 다 떨어집니다. 어떤 먹이가 $k$일 뒤에 상한다면, 늦어도 $k$일째 그날 식사를 마친 직후에는 버려야 합니다. 즉, 언제 개봉했든 $k$일째가 그 먹이를 먹을 수 있는 마지막 날입니다.

헥토르가 첫 $M$일 동안 햄스터에게 차려 줄 수 있는 식사 품질의 합의 최댓값을 구하세요. 사 온 먹이 외에도 헥토르에게는 절대 상하지 않는 군용 식량이 얼마든지 있지만, 햄스터가 몹시 싫어해서 품질이 $0$입니다. 덕분에 사 온 먹이가 다 떨어져도 햄스터가 굶을 일은 없습니다.

첫째 줄에 테스트 케이스의 수 $Z$가 주어집니다 ($1 \le Z \le 10$).

각 테스트 케이스의 첫째 줄에는 두 정수 $N$과 $M$이 주어집니다 ($1 \le N, M \le 2000$).

이어지는 $N$개의 줄에는 각각 한 종류의 먹이가 $2001$보다 작은 세 개의 음이 아닌 정수로 주어집니다: 며칠 뒤에 상하는지, 몇 끼를 먹을 수 있는지, 그 먹이 한 끼의 품질입니다.

각 테스트 케이스마다, 헥토르가 첫 $M$일 동안 햄스터에게 차려 줄 수 있는 식사 품질의 합의 최댓값을 한 줄에 출력하세요.