Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

During the Indian Programming Camp (IPC), there are N trainers. The camp runs for D days. Each day, there can be at most one lecture. The i-th trainer arrives on day D_{i} and then stays till the end of the camp. He also wants to teach exactly Ti lectures. For each lecture that a trainer was not able to teach, he will feel sad and his sadness level will be increased by S_{i}.

You are the main organizer of the contest. You want to find minimum total sadness of the trainers.

------ Input ------ 

The first line of the input contains an integer T, denoting the number of testcases.
For each test case, the first line contains two space separated integers, N, D.
The i-th of the next N lines will contain three space separated integers: D_{i}, T_{i}, S_{i} respectively.

------ Output ------ 

For each test case, output a single integer corresponding to the minimum total sadness of the trainers achievable.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N, D ≤ 10^{5}$
$1 ≤  D_{i},  T_{i} ≤ D$
$1 ≤  S_{i} ≤ 10^{5}$

------ Subtasks ------ 

Subtask #1 (40 points)

$1 ≤ T ≤ 10$
$1 ≤ N, D ≤ 10^{3}$
$1 ≤  D_{i},  T_{i} ≤ D$
$1 ≤  S_{i} ≤ 10^{3}$

Subtask #2 (60 points)

$Original constraints$

----- Sample Input 1 ------ 
3

2 3

1 2 300

2 2 100

2 3

1 1 100

2 2 300

2 3

3 2 150

1 1 200
----- Sample Output 1 ------ 
100

0

150
----- explanation 1 ------ 
Example case 1. Both the first and second trainer want to take exactly two lectures. The first trainer arrives on the 1st day and the second trainer arrives on the 2nd day. Consider a schedule where the first trainer takes the first two lectures, and the second trainer takes the last lecture on the day 3. This way the second trainer will take only one lecture but wanted to take two. Thus, his sadness will be 100. The first trainer took all the lectures that he wanted to take (ie. two lectures). Thus the total sadness is 100 + 0 = 100. You can check that no other way of assigning trainers to the days will give a better answer than this.

Example case 2. In this case, the trainers can all take all their ideal number of lectures.

Example case 3. In this case, the first trainer arrives on day 3 and wants to take two lectures. This is not possible as he can take at most one lecture on day 3 and the camp ends on day 3. The second trainer wants to take only one lecture which he can take on any one of the 1st or 2nd days. You can see that in one of the first or second days, no lecture will be held.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Mathematics

Data structures

Implementation


Solutions:
from heapq import heappush, heappop

def solve():
	(n, D) = map(int, input().split())
	data = {}
	heap = []
	for i in range(n):
		(d, t, s) = map(int, input().split())
		if d in data:
			data[d].append([t, s])
		else:
			data[d] = [[t, s]]
	for d in range(1, D + 1):
		if d in data:
			for v in data[d]:
				heappush(heap, [-1 * v[1], v[0]])
		if len(heap):
			x = heappop(heap)
			x[1] -= 1
			if x[1]:
				heappush(heap, x)
	ans = 0
	while len(heap):
		x = heappop(heap)
		ans += -1 * x[0] * x[1]
	return ans
for _ in range(int(input())):
	print(solve())


from heapq import heapify, heappop, heappush
import sys
input = sys.stdin.readline
from math import sqrt
from collections import defaultdict

def I():
	return list(map(int, input().split()))
for _ in range(int(input())):
	(n, d) = I()
	days = defaultdict(list)
	for i in range(n):
		(di, ti, si) = I()
		days[di].append((si, ti))
	heap = []
	for day in range(1, d + 1):
		for (si, ti) in days[day]:
			heappush(heap, (-si, -ti))
		if heap:
			(si, ti) = heappop(heap)
			if ti != -1:
				heappush(heap, (si, ti + 1))
	ans = 0
	for (si, ti) in heap:
		ans += -si * -ti
	print(ans)


from heapq import heappush, heappop
t = int(input())
for _ in range(t):
	(n, d) = map(int, input().split())
	days = {}
	for i in range(n):
		(a, b, c) = map(int, input().split())
		if a not in days:
			days[a] = []
		days[a].append((-1 * c, b))
	h = list()
	for i in range(1, d + 1):
		if i in days:
			for v in days[i]:
				heappush(h, v)
		if len(h) > 0:
			(y, z) = heappop(h)
			if z > 1:
				heappush(h, (y, z - 1))
	ans = 0
	for i in h:
		ans += -1 * i[0] * i[1]
	print(ans)


from collections import defaultdict
import heapq as hp
T = int(input())
for t in range(T):
	(n, d) = map(int, input().split())
	arr = []
	heap = defaultdict(list)
	for _ in range(n):
		(di, ti, si) = map(int, input().split())
		heap[di].append([-si, ti])
	for i in range(1, d + 1):
		for j in heap[i]:
			hp.heappush(arr, j)
		if len(arr):
			curr = hp.heappop(arr)
			curr[1] -= 1
			if curr[1] != 0:
				hp.heappush(arr, curr)
	ans = 0
	for i in arr:
		ans += -i[0] * i[1]
	print(ans)


from heapq import heappush, heappop
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(tuple(map(int, input().split())))
	arr.sort()
	hp = []
	j = 0
	for i in range(1, d + 1):
		while j < len(arr) and arr[j][0] <= i:
			heappush(hp, [-arr[j][2], arr[j][1]])
			j += 1
		if len(hp) > 0:
			hp[0][1] -= 1
			if hp[0][1] <= 0:
				heappop(hp)
	sum = 0
	for i in hp:
		sum += i[0] * i[1]
	print(abs(sum))


from heapq import *
t = int(input())
for _ in range(t):
	(n, d) = list(map(int, input().split()))
	ip = []
	total_sadness = 0
	for i in range(n):
		ip.append(list(map(int, input().split())))
		total_sadness += ip[i][2] * ip[i][1]
	ip.sort()
	ptr = 0
	hp = []
	for i in range(d):
		while ptr < len(ip) and ip[ptr][0] <= i + 1:
			heappush(hp, (-ip[ptr][2], ip[ptr][1]))
			ptr += 1
		if len(hp) != 0:
			(a, b) = heappop(hp)
			total_sadness += a
			b -= 1
			if b != 0:
				heappush(hp, (a, b))
	print(total_sadness)


from heapq import heappop, heappush
test = int(input())
for t in range(test):
	(N, D) = map(int, input().split())
	l = []
	ans = 0
	for i in range(N):
		(d, t, s) = map(int, input().split())
		ans = ans + t * s
		l.append([d, s, t])
	l.sort(key=lambda x: x[0])
	j = 0
	heap = []
	for i in range(1, D + 1):
		while j < N and l[j][0] == i:
			heappush(heap, (-l[j][1], l[j][2]))
			j += 1
		if heap != []:
			(val, t) = heappop(heap)
			ans += val
			t -= 1
			if t:
				heappush(heap, (val, t))
	print(ans)


import bisect
for _ in range(int(input())):
	(n, s) = map(int, input().split())
	l = []
	sol = 0
	for i in range(n):
		(di, ti, si) = map(int, input().split())
		l.append([di, ti, si])
	l.sort(key=lambda x: x[-1])
	l = l[::-1]
	tot = [i for i in range(s + 1)]
	for i in range(len(l)):
		if tot == [0]:
			break
		else:
			temp = bisect.bisect_left(tot, l[i][0])
			r = len(tot) - temp
			temp2 = temp + min(r, l[i][1])
			l[i][1] -= min(l[i][1], r)
			del tot[temp:temp2]
	for i in range(n):
		sol += l[i][1] * l[i][2]
	print(sol)


from collections import defaultdict
import heapq as hq
for i in range(int(input())):
	(n, d) = [int(number) for number in input().split()]
	h = []
	heap = defaultdict(list)
	for i in range(n):
		(di, nl, s) = [int(number) for number in input().split()]
		heap[di].append([-s, nl])
	for i in range(1, d + 1):
		for j in heap[i]:
			hq.heappush(h, j)
		if h != []:
			popva = hq.heappop(h)
			popva[1] -= 1
			if popva[1] != 0:
				hq.heappush(h, popva)
	print(sum([-i[0] * i[1] for i in h]))


from collections import defaultdict
import heapq as hp
for i in range(int(input())):
	(n, d) = [int(num) for num in input().split()]
	h = []
	heap = defaultdict(list)
	for i in range(n):
		(di, nl, s) = [int(num) for num in input().split()]
		heap[di].append([-s, nl])
	for i in range(1, d + 1):
		for j in heap[i]:
			hp.heappush(h, j)
		if h != []:
			p = hp.heappop(h)
			p[1] -= 1
			if p[1] != 0:
				hp.heappush(h, p)
	print(sum([-i[0] * i[1] for i in h]))


from collections import defaultdict
import heapq
for _ in range(int(input())):
	(n, d) = [int(x) for x in input().split()]
	h = []
	heap = defaultdict(list)
	for i in range(n):
		(di, nl, s) = [int(x) for x in input().split()]
		heap[di].append([-s, nl])
	for i in range(1, d + 1):
		for j in heap[i]:
			heapq.heappush(h, j)
		if h != []:
			pp = heapq.heappop(h)
			pp[1] -= 1
			if pp[1] != 0:
				heapq.heappush(h, pp)
	print(sum([-i[0] * i[1] for i in h]))


from heapq import *
tc = int(input())
for _ in range(tc):
	(n, d) = list(map(int, input().split()))
	dts = []
	total_sadness = 0
	for i in range(n):
		dts.append(list(map(int, input().split())))
		total_sadness += dts[i][2] * dts[i][1]
	dts.sort()
	ptr = 0
	hp = []
	for i in range(d):
		while ptr < len(dts) and dts[ptr][0] <= i + 1:
			heappush(hp, (-dts[ptr][2], dts[ptr][1]))
			ptr += 1
		if len(hp) != 0:
			(k, v) = heappop(hp)
			total_sadness += k
			v -= 1
			if v != 0:
				heappush(hp, (k, v))
	print(total_sadness)


import heapq

class Trainer:
	d: int
	t: int
	s: int

	def __init__(self, d: int, t: int, s: int):
		self.d = d
		self.t = t
		self.s = s

def minimum_sadness(n, d, trainers):
	trainers = sorted(trainers, key=lambda trainer: trainer.d)
	trainer_idx = 0
	h = []
	for di in range(1, d + 1):
		while trainer_idx < n and trainers[trainer_idx].d <= di:
			heapq.heappush(h, (-trainers[trainer_idx].s, trainer_idx, trainers[trainer_idx]))
			trainer_idx += 1
		if len(h) == 0:
			continue
		heap_element = heapq.heappop(h)
		trainer_id = heap_element[1]
		trainer = heap_element[2]
		trainer.t -= 1
		if trainer.t > 0:
			heapq.heappush(h, (-trainer.s, trainer_id, trainer))
	return sum([heap_element[2].s * heap_element[2].t for heap_element in h])
test = int(input())
for test in range(test):
	(n, d) = [int(x) for x in input().split(' ')]
	lst = []
	trainers = []
	for line in range(n):
		(di, ti, si) = [int(x) for x in input().split(' ')]
		trainers.append(Trainer(d=di, t=ti, s=si))
	print('%d' % minimum_sadness(n, d, trainers))


from collections import defaultdict
import heapq as hp
for _ in range(int(input())):
	(n, d) = [int(num) for num in input().split()]
	hl = []
	heap = defaultdict(list)
	for _ in range(n):
		(di, nl, sl) = [int(num) for num in input().split()]
		heap[di].append([-sl, nl])
	for i in range(1, d + 1):
		for j in heap[i]:
			hp.heappush(hl, j)
		if hl != []:
			popval = hp.heappop(hl)
			popval[1] -= 1
			if popval[1] != 0:
				hp.heappush(hl, popval)
	print(sum([-i[0] * i[1] for i in hl]))


import sys
import heapq
from collections import deque

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_list_strings():
	return list(map(str, sys.stdin.readline().strip().split()))

def solve(N, D, arr):
	heap = []
	arr.sort()
	queue = deque()
	for ele in arr:
		queue.append(ele)
	for i in range(1, D + 1):
		while queue:
			if queue[0][0] == i:
				heapq.heappush(heap, [-queue[0][2], -queue[0][1]])
				queue.popleft()
			else:
				break
		if len(heap) == 0:
			continue
		current = heapq.heappop(heap)
		s = abs(current[0])
		c = abs(current[1]) - 1
		if c > 0:
			heapq.heappush(heap, [-s, -c])
	ans = 0
	for ele in heap:
		ans += ele[0] * ele[1]
	print(ans)
	return
T = get_int()
while T:
	(N, D) = get_ints()
	tempN = N
	arr = []
	while tempN:
		(Di, Ti, Si) = get_ints()
		arr.append([Di, Ti, Si])
		tempN -= 1
	solve(N, D, arr)
	T -= 1


from heapq import heappush, heappop, heapify, heapreplace
T = int(input())
while T > 0:
	T -= 1
	minHeapDays = []
	maxHeapSadness = []
	(N, D) = [int(x) for x in input().split()]
	total = 0
	for i in range(N):
		(d, t, s) = [int(x) for x in input().split()]
		heappush(minHeapDays, (d, [d, t, s]))
		total += s * t
	sum1 = 0
	for i in range(1, D + 1):
		while len(minHeapDays) > 0 and minHeapDays[0][0] == i:
			x = heappop(minHeapDays)
			heappush(maxHeapSadness, (-x[1][2], x[1]))
		if len(maxHeapSadness) > 0:
			x = heappop(maxHeapSadness)
			x[1][1] -= 1
			if x[1][1] > 0:
				heappush(maxHeapSadness, x)
			sum1 += x[1][2]
	print(total - sum1)


import heapq
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	lst = []
	for i in range(n):
		(day, lec, sad) = map(int, input().split())
		lst.append([day, lec, sad])
	lst.sort()
	heap = []
	i = 0
	for day in range(1, d + 1):
		while i < n and lst[i][0] <= day:
			heapq.heappush(heap, (-lst[i][2], lst[i][1]))
			i += 1
		if len(heap) > 0:
			(sadness, lect) = heapq.heappop(heap)
			lect -= 1
			if lect > 0:
				heapq.heappush(heap, (sadness, lect))
	ans = 0
	for i in range(len(heap)):
		(sadness, lect) = heap[i]
		ans -= sadness * lect
	print(ans)


from heapq import heappop, heappush
test_cases = int(input())
for _ in range(test_cases):
	(size, days) = map(int, input().split())
	arr = []
	for __ in range(size):
		(day, lecture, sad) = map(int, input().split())
		arr.append([day, lecture, sad])
	arr.sort()
	heap = []
	i = 0
	for day in range(1, days + 1):
		while i < size and arr[i][0] <= day:
			heappush(heap, (-arr[i][2], arr[i][1]))
			i += 1
		if len(heap) > 0:
			(sadness, lect) = heappop(heap)
			lect -= 1
			if lect > 0:
				heappush(heap, (sadness, lect))
	ans = 0
	for i in range(len(heap)):
		(sadnees, lect) = heap[i]
		ans -= sadnees * lect
	print(ans)


import heapq
for i in range(int(input())):
	(n, da) = map(int, input().split())
	d = {}
	for i in range(n):
		(x, y, z) = map(int, input().split())
		if x not in d:
			d[x] = []
		d[x].append([-z, y])
	h = []
	for i in range(da):
		if i + 1 in d:
			for i in d[i + 1]:
				heapq.heappush(h, i)
		if h:
			k = heapq.heappop(h)
			if k[-1] > 1:
				k[-1] -= 1
				heapq.heappush(h, k)
	ans = 0
	for i in h:
		ans += i[0] * i[1]
	print(-ans)


import heapq
T = int(input())
for i in range(T):
	(n, d) = map(int, input().split())
	a = list()
	for i in range(n):
		temp = list(map(int, input().split()))
		a.append(temp)
	a = sorted(a, key=lambda x: x[0])
	h = []
	j = 0
	for i in range(1, d + 1):
		curr = []
		while j < n:
			if a[j][0] == i:
				curr.append(a[j])
			else:
				break
			j += 1
		for k in range(len(curr)):
			heapq.heappush(h, [-1 * curr[k][-1], curr[k]])
		if len(h) > 0:
			g = heapq.heappop(h)
			if g[1][1] > 1:
				g[1][1] -= 1
				heapq.heappush(h, g)
	hl = len(h)
	sadness = 0
	for i in range(hl):
		sadness += h[i][0] * -1 * h[i][1][1]
	print(sadness)


import heapq
from sys import stdin
input = stdin.readline

def answer():
	(q, ind) = ([], 0)
	for days in range(1, d + 1):
		while ind < n and a[ind][0] == days:
			heapq.heappush(q, [a[ind][2], a[ind][1]])
			ind += 1
		if len(q):
			(value, r) = heapq.heappop(q)
			r -= 1
			if r:
				heapq.heappush(q, [value, r])
	ans = 0
	while len(q):
		(value, r) = heapq.heappop(q)
		ans += value * r * -1
	return ans
for T in range(int(input())):
	(n, d) = map(int, input().split())
	a = []
	for i in range(n):
		(days, r, s) = map(int, input().split())
		a.append([days, r, -s])
	a.sort(key=lambda x: x[0])
	print(answer())


import heapq

def mhpu(hp, el):
	heapq.heappush(hp, el)

def mhpo(hp):
	if len(hp) == 0:
		return -1
	temp = heapq.heappop(hp)
	if temp[1] != 1:
		nt = (temp[0], temp[1] - 1)
		mhpu(hp, nt)
	return -temp[0]
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	tsum = 0
	dct = {}
	hp = []
	for i in range(n):
		(di, ti, si) = map(int, input().split())
		if di not in dct:
			dct[di] = []
		dct[di].append((-si, ti))
		tsum += ti * si
	for i in range(1, d + 1):
		if i in dct:
			for j in dct[i]:
				mhpu(hp, j)
		tmp = mhpo(hp)
		if tmp != -1:
			tsum -= tmp
	print(tsum)


import heapq as hp
for _ in range(int(input())):
	(n, m) = map(int, input().strip().split())
	schedule = [list(map(int, input().strip().split())) for i in range(n)]
	dic = {}
	for i in range(n):
		(d, t, s) = schedule[i]
		if d not in dic:
			dic[d] = []
		dic[d].append([-s, t])
	heap = []
	for i in range(m):
		if i + 1 in dic:
			for j in dic[i + 1]:
				hp.heappush(heap, j)
		if heap != []:
			k = hp.heappop(heap)
			k[1] -= 1
			if k[1] != 0:
				hp.heappush(heap, k)
	ans = 0
	for k in heap:
		ans += -k[0] * k[1]
	print(ans)


from collections import defaultdict as dd
import heapq as hp
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	l = dd(list)
	for i in range(n):
		(a, b, c) = map(int, input().split())
		l[a].append([-c, b])
	h = []
	for i in range(1, d + 1):
		for j in l[i]:
			hp.heappush(h, j)
		if h != []:
			k = hp.heappop(h)
			k[1] -= 1
			if k[1] != 0:
				hp.heappush(h, k)
	ans = 0
	for i in h:
		ans += -i[0] * i[1]
	print(ans)


import heapq
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = []
	for i in range(n):
		t = list(map(int, input().split()))
		a.append(t)
	a.sort(key=lambda x: x[0])
	j = 0
	heap = []
	for i in range(1, d + 1):
		aux = []
		while j < n:
			if a[j][0] == i:
				aux.append(a[j])
			else:
				break
			j += 1
		for k in range(len(aux)):
			heapq.heappush(heap, [-1 * aux[k][-1], aux[k]])
		if len(heap) > 0:
			t_1 = heapq.heappop(heap)
			if t_1[1][1] > 1:
				t_1[1][1] -= 1
				heapq.heappush(heap, t_1)
	res = 0
	for i in range(len(heap)):
		res += -1 * heap[i][0] * heap[i][1][1]
	print(res)


def binary_search(arr, n, x):
	l = 0
	r = n - 1
	ans = -1
	while l <= r:
		mid = int((l + r) / 2)
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			l = mid + 1
		else:
			ans = mid
			r = mid - 1
	return ans
t = int(input())
while t:
	trainers = []
	(n, d) = map(int, input().strip().split())
	for _ in range(n):
		trainers.append([int(i) for i in input().strip().split()])
	trainers.sort(key=lambda k: k[2], reverse=True)
	lec_days = []
	for _ in range(d):
		lec_days.append(_)
	sadness = 0
	for i in range(n):
		days = len(lec_days)
		if days == 0:
			for k in range(i, n):
				sadness += trainers[k][1] * trainers[k][2]
			break
		fday = trainers[i][0]
		tday = trainers[i][1]
		day = binary_search(lec_days, days, fday - 1)
		if day != -1:
			rem = days - day
			if rem >= tday:
				for k in range(day + tday - 1, day - 1, -1):
					del lec_days[k]
				tday = 0
			else:
				for k in range(len(lec_days) - 1, day - 1, -1):
					del lec_days[k]
				tday = tday - rem
		sadness += trainers[i][2] * tday
	print(sadness)
	t -= 1


class Heap:

	def __init__(slf):
		slf.lst = []
		slf.lst.append([-1, -1, -1])

	def insert(slf, l):
		slf.lst.append(l)
		i = len(slf.lst) - 1
		while int(i / 2) >= 1 and slf.lst[i][si] > slf.lst[int(i / 2)][si]:
			(slf.lst[i], slf.lst[int(i / 2)]) = (slf.lst[int(i / 2)], slf.lst[i])
			i = int(i / 2)

	def delete(slf):
		if len(slf.lst) <= 1:
			return
		slf.lst[1][ti] -= 1
		if slf.lst[1][ti] != 0:
			return
		slf.lst[1] = slf.lst[-1]
		slf.lst.pop()
		i = 1
		while i * 2 + 1 < len(slf.lst) and (slf.lst[i * 2][si] > slf.lst[i][si] or slf.lst[i * 2 + 1][si] > slf.lst[i][si]):
			if slf.lst[i * 2][si] > slf.lst[i * 2 + 1][si]:
				(slf.lst[i * 2], slf.lst[i]) = (slf.lst[i], slf.lst[i * 2])
				i *= 2
			else:
				(slf.lst[i * 2 + 1], slf.lst[i]) = (slf.lst[i], slf.lst[i * 2 + 1])
				i *= 2 + 1
		if i * 2 < len(slf.lst) and slf.lst[i * 2][si] > slf.lst[i][si]:
			(slf.lst[i * 2], slf.lst[i]) = (slf.lst[i], slf.lst[i * 2])

	def calc(slf):
		slf.lst.pop(0)
		summ = 0
		for i in range(len(slf.lst)):
			summ += slf.lst[i][si] * slf.lst[i][ti]
		return summ
(di, ti, si) = (0, 1, 2)
for _ in range(int(input())):
	heap = Heap()
	(n, d) = map(int, input().split())
	lst = []
	for _ in range(n):
		lst.append(list(map(int, input().split())))
	lst.sort()
	i = 0
	for k in range(1, d + 1):
		while i < n and lst[i][di] == k:
			heap.insert(lst[i])
			i += 1
		heap.delete()
	print(heap.calc())


import heapq
try:

	class Trainer:

		def __init__(self, d, l, s):
			self.d = d
			self.l = l
			self.s = s

		def takeLecture(self):
			self.l -= 1

		def calculateSadness(self):
			return self.l * self.s

		def __lt__(self, other):
			return self.d < other.d
	t = int(input())
	output = []
	while t > 0:
		t -= 1
		(n, d) = map(int, input().split())
		firstHeap = []
		secondHeap = []
		while n > 0:
			n -= 1
			(a, b, c) = map(int, input().split())
			trainer = Trainer(a, b, c)
			firstHeap.append((trainer.d, trainer))
		heapq.heapify(firstHeap)
		i = 0
		while d > 0:
			d -= 1
			i += 1
			while len(firstHeap) > 0 and firstHeap[0][1].d == i:
				p = heapq.heappop(firstHeap)[1]
				heapq.heappush(secondHeap, (-1 * p.s, p))
			if len(secondHeap) > 0:
				q = heapq.heappop(secondHeap)[1]
				q.takeLecture()
				if q.l != 0:
					heapq.heappush(secondHeap, (-1 * q.s, q))
		total = 0
		for value in secondHeap:
			total += value[1].calculateSadness()
		output.append(total)
	for value in output:
		print(value)
except:
	w = 0


from collections import defaultdict
import sys

def range_intersection(a, b, c, d):
	if a >= c - 1 and a <= d or (b >= c - 1 and b <= d):
		return True
	if c >= a - 1 and c <= b or (d >= a - 1 and d <= b):
		return True
	return False

def merge_ranges(a, b, c, d):
	k = a if a < c else c
	tot_dist = b - a + (d - c) + 1
	return (k, k + tot_dist)

def find_index(list, len_list, start):
	l = 0
	r = len_list
	while l < r:
		mid = (l + r) // 2
		if list[mid][0] <= start:
			l = mid + 1
		else:
			r = mid
	return l

class add_lec:

	def __init__(self, max_range):
		self.list = []
		self.max_Range = max_range
		self.total_sad = 0

	def add_sadness(self, start, lectures, sadness):
		if self.list == []:
			if start + lectures - 1 > self.max_Range:
				self.total_sad += (start + lectures - 1 - self.max_Range) * sadness
				self.list.append([start, self.max_Range])
			else:
				self.list.append([start, start + lectures - 1])
		else:
			len_list = len(self.list)
			index = find_index(self.list, len_list, start)
			(a, b) = (self.list[index - 1][0], self.list[index - 1][1])
			(c, d) = (start, start + lectures - 1)
			added = False
			while range_intersection(a, b, c, d):
				added = True
				(r1, r2) = merge_ranges(a, b, c, d)
				del self.list[index - 1]
				if index > len(self.list) or index <= 0:
					break
				(a, b) = (self.list[index - 1][0], self.list[index - 1][1])
				(c, d) = (r1, r2)
			if index < len_list and added is False:
				(a, b) = (self.list[index][0], self.list[index][1])
				while range_intersection(a, b, c, d):
					added = True
					(r1, r2) = merge_ranges(a, b, c, d)
					del self.list[index]
					if index >= len(self.list):
						break
					(a, b) = (self.list[index][0], self.list[index][1])
					(c, d) = (r1, r2)
			if added is True:
				if r2 > self.max_Range:
					insert_index = find_index(self.list, len(self.list), r1)
					self.total_sad += (r2 - self.max_Range) * sadness
					self.list.insert(insert_index, [r1, self.max_Range])
				else:
					insert_index = find_index(self.list, len(self.list), r1)
					self.list.insert(insert_index, [r1, r2])
			if added is False:
				if d > self.max_Range:
					self.total_sad += (d - self.max_Range) * sadness
					self.list.insert(index, [c, self.max_Range])
				else:
					self.list.insert(index, [c, d])

	def print_var(self):
		print('LIST =', self.list)
		print('TOTAL SADNESS =', self.total_sad)
		print('RANGE ALLOWED = ', self.max_Range)
n = int(input())
for i in range(n):
	(l1, l2) = map(int, input().split(' '))
	my_dict = defaultdict(list)
	rep = add_lec(l2)
	for r in range(l1):
		(start, lect, sadness) = map(int, input().split(' '))
		my_dict[sadness].append([start, lect])
	for (k, v) in sorted(my_dict.items(), reverse=True):
		for j in v:
			rep.add_sadness(j[0], j[1], k)
	print(rep.total_sad)


import sys
from heapq import heapify, heappush, heappop
from math import sqrt, floor, factorial, gcd
from collections import deque, Counter, defaultdict
inp = sys.stdin.readline
read = lambda : list(map(int, inp().strip().split()))

def solve():
	ans = ''
	for _ in range(int(inp())):
		(n, d) = read()
		dic = [[] for i in range(d)]
		for i in range(n):
			(di, t, s) = read()
			dic[di - 1].append([-s, t])
		arr = []
		heapify(arr)
		for i in range(d):
			for j in dic[i]:
				heappush(arr, j)
			if arr:
				elem = heappop(arr)
				elem[1] -= 1
				if elem[1] > 0:
					heappush(arr, elem)
			else:
				pass
		rem = 0
		for i in arr:
			rem += -i[0] * i[1]
		ans += str(rem) + '\n'
	print(ans)
solve()


from heapq import *
T = int(input())
for i in range(T):
	(N, D) = map(int, input().split())
	s = []
	for i in range(N):
		(a, b, c) = map(int, input().split())
		s.append((a, b, c))
	s.sort()
	d = {}
	ind = 0
	h = []
	for i in range(1, D + 1):
		while ind < len(s) and s[ind][0] == i:
			(a, b, c) = s[ind]
			if c not in d:
				d[c] = 0
				heappush(h, -c)
			d[c] += b
			ind += 1
		if len(h) == 0:
			continue
		val = h[0] * -1
		d[val] -= 1
		if d[val] == 0:
			heappop(h)
			del d[val]
	sad = 0
	for i in d:
		sad += i * d[i]
	print(sad)


import sys
import math
from collections import defaultdict
import bisect
import heapq

def alele():
	return list(map(int, sys.stdin.readline().strip().split()))

def ilele():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 1000000000 + 7
for _ in range(int(input())):
	(N, D) = ilele()
	mark = {}
	A = defaultdict(list)
	for i in range(N):
		(DI, T, S) = ilele()
		mark[i + 1] = (-1 * S, T, i + 1)
		A[DI].append(i + 1)
	mylist = []
	heapq.heapify(mylist)
	for d in range(1, D + 1):
		if A.get(d, -1) != -1:
			for i in A[d]:
				heapq.heappush(mylist, mark[i])
		if len(mylist) != 0:
			Z = heapq.heappop(mylist)
			if Z[1] == 1:
				mark[Z[2]] = (Z[0], 0, Z[2])
			else:
				mark[Z[2]] = (Z[0], Z[1] - 1, Z[2])
				heapq.heappush(mylist, (Z[0], Z[1] - 1, Z[2]))
	Ans = 0
	for (i, j, k) in mark.values():
		Ans += abs(i) * j
	print(Ans)


from heapq import heappush, heappop
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	day = [[] for i in range(d)]
	for i in range(n):
		(di, ti, si) = map(int, input().split())
		day[di - 1].append((-1 * si, ti))
	h = []
	for i in day:
		if len(i) != 0:
			for j in range(len(i)):
				heappush(h, i[j])
		else:
			pass
		if len(h) != 0:
			x = h[0]
			heappop(h)
			if x[1] != 1:
				heappush(h, (x[0], x[1] - 1))
	ans = 0
	for i in range(len(h)):
		ans += -1 * h[i][0] * h[i][1]
	print(ans)


from operator import itemgetter
import heapq
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	l = []
	for i in range(n):
		l.append([int(x) for x in input().split()])
	l = sorted(l, key=itemgetter(0))
	for i in range(n):
		m = -l[i][2]
		l[i].insert(0, m)
	i = 0
	j = 1
	heap = []
	heapq.heapify(heap)
	while j <= d:
		if i < n:
			while j >= l[i][1]:
				heapq.heappush(heap, l[i])
				i += 1
				if i == n:
					break
		if heap:
			k = heapq.heappop(heap)
		if k[2] == 1 or k[2] == 0:
			k[2] = 0
		else:
			k[2] -= 1
			heapq.heappush(heap, k)
		j += 1
	sm = 0
	while heap:
		h = heapq.heappop(heap)
		sm += h[2] * h[3]
	print(sm)


import heapq
t = int(input())

def sort0(x):
	return x[0]
while t > 0:
	(n, d) = map(int, input().split())
	l = [] * d
	ts = 0
	for i in range(n):
		s = list(map(int, input().split()))
		l.append(s)
		ts += s[2] * s[1]
	l.sort(key=sort0)
	h = []
	heapq.heapify(h)
	j = 0
	s = 0
	for i in range(d):
		if j < n:
			while l[j][0] == i + 1:
				heapq.heappush(h, [-l[j][2], l[j][1]])
				j += 1
				if j >= n:
					break
		if len(h) > 0:
			x = heapq.heappop(h)
			x[1] -= 1
			ts += x[0]
			if x[1] > 0:
				heapq.heappush(h, x)
	print(ts)
	t -= 1


def ipctrain(n, d, m):
	import heapq
	h = []
	for i in range(1, d + 1):
		if i in m:
			for n in m[i]:
				heapq.heappush(h, n)
		if h:
			n = heapq.heappop(h)
			n[1] = n[1] - 1
			if n[1]:
				heapq.heappush(h, n)
	sadness = 0
	for item in h:
		sadness += -item[0] * item[1]
	return sadness
t = int(input())
for _ in range(t):
	(n, d) = map(int, input().split())
	m = {}
	for _ in range(n):
		(di, ti, si) = map(int, input().split())
		if di not in m:
			m[di] = [[-si, ti]]
		else:
			m[di].append([-si, ti])
	print(ipctrain(n, d, m))


from heapq import heapify, heappush, heappop
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	li = []
	for i in range(n):
		temp = list(map(int, input().split()))
		li.append(temp)
	li.sort()
	cur = 0
	sadh = []
	for i in range(1, d + 1):
		while cur < len(li) and li[cur][0] == i:
			temp = [-1 * li[cur][-1], li[cur][1]]
			cur += 1
			heappush(sadh, temp)
		if len(sadh) > 0:
			sadh[0][1] -= 1
			if sadh[0][1] == 0:
				heappop(sadh)
	ans = 0
	while len(sadh) > 0:
		ans += sadh[0][1] * sadh[0][0]
		heappop(sadh)
	print(-1 * ans)


import heapq
for i in range(int(input())):
	(n, d) = map(int, input().split(' '))
	di = [[] for i in range(d + 1)]
	q = []
	for i in range(n):
		(w, x, y) = map(int, input().split(' '))
		di[w].append([-1 * y, x])
	for i in range(1, d + 1):
		for j in range(len(di[i])):
			heapq.heappush(q, di[i][j])
		if len(q) > 0:
			q[0][1] = q[0][1] - 1
			if q[0][1] == 0:
				heapq.heappop(q)
	sum = 0
	for i in range(len(q)):
		sum = sum + q[i][0] * q[i][1]
	print(-1 * sum)


from heapq import heappush, heappop
from collections import defaultdict
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	dl = []
	for i in range(d + 1):
		dl.append([])
	for ni in range(n):
		(di, ti, si) = map(int, input().split())
		dl[di].append([ti, -si])
	dd = defaultdict(int)
	heap = []
	hl = 0
	for i in range(1, d + 1):
		for j in dl[i]:
			if dd[j[1]] == 0:
				heappush(heap, j[1])
				hl += 1
			dd[j[1]] += j[0]
		if hl > 0:
			dd[heap[0]] -= 1
			if dd[heap[0]] == 0:
				heappop(heap)
				hl -= 1
	s = 0
	for i in heap:
		s += -i * dd[i]
	print(s)


import heapq
t = int(input())
for i in range(t):
	(n, d) = [int(i) for i in input().split()]
	arr = []
	for i in range(n):
		(di, ti, si) = [int(i) for i in input().split()]
		arr.append([di, ti, -si])
	arr.sort(key=lambda x: x[0])
	day = 1
	heap = []
	ptr = 0
	while day <= d:
		while ptr < n and arr[ptr][0] == day:
			heapq.heappush(heap, [arr[ptr][2], arr[ptr][1]])
			ptr += 1
		if len(heap) != 0:
			heap[0][1] -= 1
			if heap[0][1] == 0:
				heapq.heappop(heap)
		day += 1
	ans = 0
	while len(heap) != 0:
		temp = heapq.heappop(heap)
		ans += temp[0] * temp[1]
	print(-ans)


import bisect

def Sort_Tuple(tup):
	tup.sort(key=lambda x: x[-1])
	return tup[::-1]
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	l = []
	ans = 0
	for x in range(n):
		(di, ti, si) = map(int, input().split())
		l.append([di, ti, si])
	l = Sort_Tuple(l)
	days = [x for x in range(d + 1)]
	for x in range(len(l)):
		if days == [0]:
			break
		else:
			ind = bisect.bisect_left(days, l[x][0])
			remaining = len(days) - ind
			end = ind + min(remaining, l[x][1])
			l[x][1] -= min(l[x][1], remaining)
			del days[ind:end]
	for x in range(n):
		ans += l[x][1] * l[x][2]
	print(ans)


from sys import stdin
from collections import defaultdict

class MaxHeap:

	def __init__(self):
		self.heapList = []
		self.currentSize = 0

	def percolate_up(self, i):
		while (i - 1) // 2 >= 0:
			if self.heapList[i] > self.heapList[(i - 1) // 2]:
				temp = self.heapList[i]
				self.heapList[i] = self.heapList[(i - 1) // 2]
				self.heapList[(i - 1) // 2] = temp
			i = (i - 1) // 2

	def insert_element(self, element):
		self.heapList.append(element)
		self.currentSize += 1
		self.percolate_up(self.currentSize - 1)

	def peek(self):
		return self.heapList[0]

	def max_child(self, i):
		if i * 2 + 2 > self.currentSize - 1:
			return i * 2 + 1
		elif self.heapList[i * 2 + 1] > self.heapList[i * 2 + 2]:
			return i * 2 + 1
		else:
			return i * 2 + 2

	def percolate_down(self, i):
		while i * 2 + 1 < self.currentSize:
			maxChild = self.max_child(i)
			if self.heapList[i] < self.heapList[maxChild]:
				temp = self.heapList[i]
				self.heapList[i] = self.heapList[maxChild]
				self.heapList[maxChild] = temp
			i = maxChild

	def delete_max(self):
		self.heapList[0] = self.heapList[self.currentSize - 1]
		self.heapList.pop()
		self.currentSize -= 1
		self.percolate_down(0)

	def build_heap(self, alist):
		i = len(alist) // 2
		self.currentSize = len(alist)
		self.heapList = alist
		while i > 0:
			self.percolate_down(i - 1)
			i = i - 1

def calculate_minimum_sadness(N, D, info_dict):
	pq = MaxHeap()
	for i in range(D):
		if i + 1 in info_dict:
			if len(info_dict[i + 1]) == 1:
				pq.insert_element((info_dict[i + 1][0][1], info_dict[i + 1][0][0], i + 1))
			elif len(info_dict[i + 1]) > 1:
				for j in info_dict[i + 1]:
					pq.insert_element((j[1], j[0], i + 1))
		if pq.currentSize > 0:
			pq.heapList = teach_a_lecture(pq)
	minimumSadness = 0
	for j in pq.heapList:
		minimumSadness += j[0] * j[1]
	return minimumSadness

def teach_a_lecture(pq):
	heapList = pq.heapList
	if heapList[0][1] > 1:
		reducedDay = list(heapList[0])
		reducedDay[1] = reducedDay[1] - 1
		pq.heapList[0] = tuple(reducedDay)
	else:
		pq.delete_max()
	return pq.heapList
t = int(stdin.readline())
for i in range(t):
	(N, D) = map(int, stdin.readline().strip('').split(' '))
	info_dict = defaultdict(list)
	for j in range(N):
		(d, t, s) = map(int, stdin.readline().strip().split(' '))
		if d in info_dict:
			ne = info_dict[d]
			ne.append((t, s))
			info_dict[d] = ne
		else:
			info_dict[d] = [(t, s)]
	print(calculate_minimum_sadness(N, D, info_dict))


import heapq

def solve(arr, d):
	heap = []
	heapq.heapify(heap)
	arr.sort()
	ind = 0
	schedule = [0] * (d + 1)
	ans = 0
	for i in range(1, d + 1):
		while ind < len(arr):
			if arr[ind][0] > i:
				break
			heapq.heappush(heap, arr[ind][::-1])
			ind += 1
		if len(heap):
			heap[0][1] -= 1
			if heap[0][1] == 0:
				heapq.heappop(heap)
	for ele in heap:
		ans += -1 * ele[0] * ele[1]
	return ans
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
		arr[i][-1] *= -1
	print(solve(arr, d))


import sys
import heapq
t = int(sys.stdin.readline())
for _ in range(t):
	(n, d) = map(int, sys.stdin.readline().split())
	days = [[] for i in range(d)]
	a = [0] * n
	for i in range(n):
		(dd, t, s) = map(int, sys.stdin.readline().split())
		a[i] = [-s, t]
		days[dd - 1].append(i)
	seq = []
	for i in range(d):
		for idx in days[i]:
			entry = a[idx]
			heapq.heappush(seq, entry)
		if seq:
			ele = heapq.heappop(seq)
			ele[1] -= 1
			if ele[1] != 0:
				heapq.heappush(seq, ele)
	sadness = sum((-ele[0] * ele[1] for ele in seq))
	print(sadness)


import bisect
t = int(input())
for i in range(t):
	(n, D) = map(int, input().split())
	A = []
	for j in range(n):
		(d, t, s) = map(int, input().split())
		A.append((d, t, s))
	A.sort(key=lambda a: a[0])
	pk = 0
	schd = []
	d = {}
	for j in range(1, D + 1):
		while pk < n and A[pk][0] == j:
			a = bisect.bisect(schd, A[pk][2])
			if schd == [] or a == 0 or schd[a - 1] != A[pk][2]:
				bisect.insort(schd, A[pk][2])
			try:
				d[A[pk][2]] += A[pk][1]
			except:
				d[A[pk][2]] = A[pk][1]
			pk += 1
		if schd == []:
			continue
		d[schd[-1]] -= 1
		if d[schd[-1]] == 0:
			schd.pop()
	ans = 0
	for j in schd:
		ans += j * d[j]
	print(ans)


import heapq
p = int(input())
while p:
	(n, d) = map(int, input().split())
	total = 0
	trainees = []
	for _ in range(n):
		(x, t, s) = map(int, input().split())
		trainees.append([s, t, x])
		total += s * t
	trainees = sorted(trainees, key=lambda x: x[2])
	heap = []
	s = 0
	i = 0
	for current_day in range(1, d + 1):
		while i < n and trainees[i][2] == current_day:
			heapq.heappush(heap, [-trainees[i][0], trainees[i][1], trainees[i][2]])
			i += 1
		if not heap:
			continue
		elem = heapq.heappop(heap)
		s += -elem[0]
		elem[1] -= 1
		if elem[1] > 0:
			heapq.heappush(heap, elem)
	print(total - s)
	p -= 1


import heapq
from collections import defaultdict
for _ in range(int(input())):
	(n, D) = [int(s) for s in input().split()]
	dct = defaultdict(list)
	cnt = dict()
	sumi = 0
	for i in range(n):
		d = [int(s) for s in input().split()]
		dct[d[0]].append([-1 * d[2], d[1]])
		cnt[d[0]] = d[1]
		sumi += d[2]
	rq = []
	for i in range(1, D + 1):
		if i in dct.keys():
			for j in dct[i]:
				heapq.heappush(rq, j)
		if rq:
			curr = heapq.heappop(rq)
			curr[1] -= 1
			if curr[1] != 0:
				heapq.heappush(rq, curr)
	ans = 0
	for i in rq:
		ans += i[0] * i[1]
	print(-1 * ans)


from heapq import heappush, heappop

class Trainer:

	def __init__(self, d, t, s):
		self.d = d
		self.t = t
		self.s = s

	def __gt__(self, other):
		return self.s < other.s

def func(trnr):
	return trnr.d
t = int(input())
for tc in range(0, t):
	(n, d) = input().split()
	(n, d) = (int(n), int(d))
	trnrs = []
	for trnr in range(0, n):
		(di, ti, si) = input().split()
		(di, ti, si) = (int(di), int(ti), int(si))
		trnrs.append(Trainer(di, ti, si))
	trnrs.sort(key=func)
	indx = 0
	availT = []
	for day in range(1, d + 1):
		while indx < n:
			if trnrs[indx].d <= day:
				heappush(availT, trnrs[indx])
				indx += 1
				continue
			break
		if not availT:
			continue
		if availT[0].t > 1:
			availT[0].t -= 1
		else:
			heappop(availT)
	ans = 0
	for trnr in availT:
		ans += trnr.t * trnr.s
	print(ans)


import heapq
t = int(input())
while t != 0:
	h = []
	(n, d) = map(int, input().split())
	a = []
	ans = 0
	for i in range(n):
		temp = list(map(int, input().split()))
		ans = ans + temp[1] * temp[2]
		temp[-1] = -temp[-1]
		a.append(temp)
	a = sorted(a, key=lambda x: x[0])
	nn = a[-1][0]
	j = 0
	for i in range(d + 1):
		while j < n:
			temp = a[j]
			if temp[0] != i:
				break
			else:
				(temp[-1], temp[0]) = (temp[0], temp[-1])
				heapq.heappush(h, temp)
				j += 1
		if len(h) > 0:
			z = heapq.heappop(h)
			ans = ans + z[0]
			z[1] -= 1
			if z[1] > 0:
				heapq.heappush(h, z)
	print(ans)
	t -= 1


from heapq import heappush, heappop, heapify
t = int(input())
for ijk in range(0, t):
	inp = []
	(n, d) = map(int, input().strip().split())
	for m in range(0, n):
		inp.append(list(map(int, input().strip().split())))
	inp = sorted(inp, key=lambda x: x[0])
	j = 0
	h = []
	for i in range(1, d + 1):
		cur = []
		while j < n and inp[j][0] == i:
			cur.append(inp[j])
			j += 1
		for val in cur:
			heappush(h, (-1 * val[2], val))
		if len(h) > 0:
			first = h[0]
			if first[1][1] == 1:
				heappop(h)
			else:
				h[0] = (first[0], [first[1][0], first[1][1] - 1, first[1][2]])
	ans = 0
	for left in h:
		ans += left[1][1] * left[1][2]
	print(ans)


import heapq
for _ in range(int(input())):
	(teacher, days) = map(int, input().split())
	final = [None for x in range(teacher)]
	total = 0
	for i in range(teacher):
		final[i] = [int(x) for x in input().split()]
		total += final[i][1] * final[i][2]
	final.sort()
	sums = 0
	j = 0
	hh = []
	for i in range(1, days + 1):
		if j < teacher:
			while final[j][0] <= i:
				heapq.heappush(hh, [-final[j][2], final[j][1]])
				j += 1
				if j == teacher:
					break
		if hh:
			if hh[0][1] > 1:
				hh[0][1] -= 1
				sums += hh[0][0]
			else:
				sums += hh[0][0]
				heapq.heappop(hh)
	print(total + sums)


import heapq
for _ in range(int(input())):
	(N, D) = input().split()
	N = int(N)
	D = int(D)
	a = [None] * N
	total = 0
	for i in range(N):
		a[i] = [int(x) for x in input().split()]
		total += a[i][1] * a[i][2]
	a.sort()
	sums = 0
	j = 0
	hh = []
	for i in range(1, D + 1):
		if j < N:
			while a[j][0] <= i:
				heapq.heappush(hh, [-a[j][2], a[j][1]])
				j += 1
				if j == N:
					break
		if hh:
			if hh[0][1] > 1:
				hh[0][1] -= 1
				sums += hh[0][0]
			else:
				sums += hh[0][0]
				heapq.heappop(hh)
	print(total + sums)


import heapq
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	allt = [None] * n
	sad = 0
	for i in range(n):
		allt[i] = [int(o) for o in input().split()]
		sad += allt[i][1] * allt[i][2]
	allt = sorted(allt)
	i = 1
	j = 0
	h = []
	s = 0
	while i <= d:
		if j < n:
			while allt[j][0] <= i:
				heapq.heappush(h, [-allt[j][2], allt[j][1]])
				j += 1
				if j == n:
					break
		if h:
			if h[0][1] > 1:
				h[0][1] -= 1
				s += h[0][0]
			else:
				s += h[0][0]
				heapq.heappop(h)
		i += 1
	print(sad + s)


from heapq import *
t = int(input())
for _ in range(t):
	(n, day) = map(int, input().split())
	s = {}
	d = {}
	for i in range(n):
		(dd, tt, ss) = map(int, input().split())
		s[i] = [tt, ss]
		try:
			d[dd].append(i)
		except:
			d[dd] = [i]
	heap = []
	for i in range(1, day + 1):
		try:
			for ii in d[i]:
				heappush(heap, (-s[ii][1], ii))
		except:
			pass
		try:
			k = heap[0]
		except:
			continue
		if s[k[1]][0] == 1:
			heappop(heap)
		s[k[1]][0] -= 1
	tot = 0
	for i in s:
		tot += s[i][0] * s[i][1]
	print(tot)


import heapq

def main():
	t = int(input())
	for _ in range(t):
		(N, D) = map(int, input().split())
		day = {}
		for tr in range(1, N + 1):
			(Di, Ti, Si) = map(int, input().split())
			if Di not in day:
				day[Di] = []
			day[Di].append((-1 * Si, Ti))
		arr = []
		for i in range(1, D + 1):
			if i in day:
				for record in day[i]:
					heapq.heappush(arr, record)
			if len(arr) != 0:
				element = heapq.heappop(arr)
				if element[1] > 1:
					heapq.heappush(arr, (element[0], element[1] - 1))
		sadness = 0
		for element in arr:
			sadness += -1 * element[0] * element[1]
		print(sadness)
import profile
main()


import heapq as pq
from collections import defaultdict
for _ in range(int(input())):
	(N, D) = map(int, input().split())
	dl = defaultdict(list)
	for a1 in range(N):
		(Di, Ti, Si) = map(int, input().split())
		dl[Di].append((-1 * Si, Ti))
	heap = []
	res = 0
	for i in range(1, D + 1):
		for ele in dl[i]:
			pq.heappush(heap, ele)
		while heap:
			ele = pq.heappop(heap)
			if ele[1] > 1:
				res += ele[0]
				pq.heappush(heap, (ele[0], ele[1] - 1))
				break
			elif ele[1] == 1:
				res += ele[0]
				break
	for k in dl:
		for ele in dl[k]:
			res += -1 * ele[0] * ele[1]
	print(res)


import heapq
for z in range(int(input())):
	(n, d) = tuple(map(int, input().split()))
	sad = [tuple(map(int, input().split())) for i in range(n)]
	sad.sort()
	heap = []
	heapq.heapify(heap)
	j = 0
	for i in range(1, d + 1):
		if j < n and sad[j][0] == i:
			while j < n and sad[j][0] == i:
				heapq.heappush(heap, (-sad[j][2], sad[j][1]))
				j += 1
		if len(heap) > 0:
			tu = heapq.heappop(heap)
			tu1 = (tu[0], tu[1] - 1)
			if tu1[1] > 0:
				heapq.heappush(heap, tu1)
	heapl = list(heap)
	tot = 0
	for i in range(len(heapl)):
		tot -= heapl[i][0] * heapl[i][1]
	print(tot)


import heapq
t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	l = [[] for j in range(d)]
	for i in range(n):
		(a, b, c) = map(int, input().split())
		l[a - 1].append([-c, b, a])
	total = 0
	heap = []
	for i in l:
		for j in i:
			heapq.heappush(heap, j)
		if len(heap) > 0:
			z = heapq.heappop(heap)
			z[1] -= 1
			if z[1] > 0:
				heapq.heappush(heap, z)
	for i in heap:
		total += i[0] * (-1 * i[1])
	print(total)


import heapq
t = int(input())
for _ in range(t):
	(n, d) = map(int, input().split())
	day = [[] for i in range(d)]
	for i in range(n):
		(di, ti, si) = map(int, input().split())
		day[di - 1].append([-si, di, ti])
	heap = []
	for d in day:
		for e in d:
			heapq.heappush(heap, e)
		if len(heap) > 0:
			ans = heapq.heappop(heap)
			ans[2] -= 1
			if ans[2] > 0:
				heapq.heappush(heap, ans)
	ans = 0
	for e in heap:
		ans += -e[0] * e[2]
	print(ans)


class BinHeap:

	def __init__(self):
		self.heaplist = [0]
		self.currentSize = 0

	def percUp(self, i):
		while i // 2 > 0:
			if self.heaplist[i][1] < self.heaplist[i // 2][1]:
				(self.heaplist[i], self.heaplist[i // 2]) = (self.heaplist[i // 2], self.heaplist[i])
			i = i // 2

	def minChild(self, i):
		if i * 2 + 1 > self.currentSize:
			return i * 2
		elif self.heaplist[i * 2][1] < self.heaplist[i * 2 + 1][1]:
			return i * 2
		else:
			return i * 2 + 1

	def percDown(self, i):
		while i * 2 <= self.currentSize:
			mc = self.minChild(i)
			if self.heaplist[i][1] > self.heaplist[mc][1]:
				(self.heaplist[i], self.heaplist[mc]) = (self.heaplist[mc], self.heaplist[i])
			i = mc

	def insert(self, k):
		self.heaplist.append(k)
		self.currentSize += 1
		self.percUp(self.currentSize)

	def delMin(self):
		retval = self.heaplist[1]
		self.heaplist[1] = self.heaplist[self.currentSize]
		self.currentSize -= 1
		self.heaplist.pop()
		self.percDown(1)
		return retval

	def buildHeap(self, alist):
		self.heaplist = [0] + alist[:]
		self.currentSize = len(alist)
		i = len(alist) // 2
		while i > 0:
			self.percDown(i)
			i -= 1
for _ in range(int(input().strip())):
	(n, d) = map(int, input().strip().split())
	trainers = []
	for i in range(n):
		(d_i, t_i, s_i) = map(int, input().strip().split())
		trainers.append([d_i, -1 * s_i, t_i])
	trainers.sort(reverse=True)
	bh = BinHeap()
	for day_num in range(1, d + 1):
		while trainers and trainers[-1][0] == day_num:
			bh.insert(trainers.pop())
		if len(bh.heaplist) > 1:
			bh.heaplist[1][2] -= 1
			if bh.heaplist[1][2] == 0:
				bh.delMin()
	answer = 0
	while len(bh.heaplist) > 1:
		remaining = bh.heaplist.pop()
		answer += remaining[1] * remaining[2]
	print(abs(answer))


from heapq import *

def soln(d, inputlist):
	ans = 0
	j = 0
	heap = []
	for i in range(1, d + 1):
		while j < len(inputlist) and inputlist[j][0] <= i:
			(days, lectures, sadness) = inputlist[j]
			heappush(heap, [-1 * sadness, lectures])
			j += 1
		if len(heap) <= 0:
			continue
		current = heap[0]
		current[1] -= 1
		if current[1] <= 0:
			k = heappop(heap)
	for i in heap:
		ans += -1 * i[0] * i[1]
	return ans
t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	l = []
	for j in range(n):
		l.append(list(map(int, input().split())))
	ans = soln(d, sorted(l))
	print(ans)


t = int(input())
for _ in range(t):
	finalAnswer = 0
	(n, day) = [int(x) for x in input().strip().split()]
	valf = [int(i) for i in range(day + 1)]
	dt = []
	si = []
	for i in range(n):
		(d, t, s) = [int(x) for x in input().strip().split()]
		dt.append((d - 1, t))
		si.append((s, i))
	si = sorted(si)
	for i in range(n - 1, -1, -1):
		remaining = dt[si[i][1]][0]
		tmp = remaining
		j = 0
		while j <= day:
			if tmp > valf[tmp]:
				j += 1
				tmp = valf[tmp]
			else:
				j = day + 1
		j = 0
		while j <= day:
			if tmp != valf[tmp]:
				j += 1
				tmp = valf[tmp]
			else:
				j = day + 1
		training = dt[si[i][1]][1]
		while day > tmp:
			training -= 1
			valf[tmp] = remaining
			tmp += 1
			if training <= 0:
				break
			j = 0
			while j <= day:
				if tmp > valf[tmp]:
					tmp = valf[tmp]
					j += 1
				else:
					j = day + 1
			j = 0
			while j <= day:
				if tmp != valf[tmp]:
					j += 1
					tmp = valf[tmp]
				else:
					j = day + 1
		valf[remaining] = tmp
		finalAnswer += training * si[i][0]
	print(finalAnswer)


from heapq import heappush, heappop, heapify

def solve(N, D, arr):
	heapify(arr)
	h = []
	for i in range(1, D + 1):
		cur_list = []
		while len(arr) > 0:
			if arr[0][0] == i:
				cur_list.append(heappop(arr))
			else:
				break
		if len(cur_list) == 0:
			pass
		else:
			for e in cur_list:
				heappush(h, (-1 * e[2], (e[0], e[1], e[2])))
		if len(h) > 0:
			min_e = h[0]
			if min_e[1][1] == 1:
				heappop(h)
			else:
				h[0] = (min_e[0], (min_e[1][0], min_e[1][1] - 1, min_e[1][2]))
	sad = 0
	for x in h:
		sad += x[1][1] * x[1][2]
	return sad
T = int(input())
for t in range(T):
	inp_1 = list(map(int, input().split()))
	N = inp_1[0]
	D = inp_1[1]
	arr = []
	for n in range(N):
		r = list(map(int, input().split()))
		arr.append(r)
	print(solve(N, D, arr))


import heapq
mx = 99999999
for i in range(int(input())):
	(n, d) = [int(x) for x in input().split()]
	(data, hp) = ([], [])
	for i in range(n):
		(days, num_lec, sad) = [int(x) for x in input().split()]
		data.append([days, num_lec, sad])
	data = sorted(data)
	data.append([mx, mx, mx])
	person = 0
	for day in range(1, d + 1):
		while data[person][0] <= day:
			heapq.heappush(hp, (-data[person][2], data[person][1]))
			person += 1
		if len(hp):
			(sad, lec_remaining) = heapq.heappop(hp)
			if lec_remaining > 1:
				lec_remaining -= 1
				heapq.heappush(hp, (sad, lec_remaining))
	ans = 0
	for i in hp:
		ans += -i[0] * i[1]
	print(ans)


from heapq import *
t = int(input())
for tc in range(t):
	(n, d) = map(int, input().split())
	trd = []
	for dy in range(d):
		trd.append([])
	trainers = {}
	x = []
	for i in range(n):
		(da, t, s) = map(int, input().split())
		trd[da - 1].append(i)
		trainers[i] = [da, t, s]
	for i in range(d):
		for e in trd[i]:
			heappush(x, [-trainers[e][2], trainers[e][1]])
		if len(x) > 0:
			if x[0][1] - 1 == 0:
				heappop(x)
			else:
				x[0][1] -= 1
	ts = 0
	for e in x:
		ts += -e[0] * e[1]
	print(ts)