import sys
import heapq

input = sys.stdin.readline


def solve():
    t = int(input())
    out = []

    for _ in range(t):
        n, k = map(int, input().split())
        days = [tuple(map(int, input().split())) for _ in range(n)]

        cnt = {}
        low = []
        high = []
        kept = 0
        profit = 0

        def add(value, num):
            nonlocal kept
            if num <= 0:
                return
            cnt[value] = cnt.get(value, 0) + num
            kept += num
            heapq.heappush(low, value)
            heapq.heappush(high, -value)

        def clean_low():
            while low and cnt.get(low[0], 0) == 0:
                heapq.heappop(low)

        def clean_high():
            while high and cnt.get(-high[0], 0) == 0:
                heapq.heappop(high)

        def use_buy(cost, limit):
            nonlocal kept, profit
            used = 0
            while used < limit:
                clean_high()
                if not high:
                    break
                value = -high[0]
                if value <= cost:
                    break

                have = cnt[value]
                take = min(have, limit - used)

                cnt[value] = have - take
                kept -= take
                used += take
                profit += (value - cost) * take

            if used:
                add(cost, used)

        def trim_small(extra):
            nonlocal kept
            while extra > 0:
                clean_low()
                value = low[0]
                have = cnt[value]
                drop = min(have, extra)
                cnt[value] = have - drop
                kept -= drop
                extra -= drop

        for a, b, c, d in reversed(days):
            add(c, d)
            use_buy(a, b)
            if kept > k:
                trim_small(kept - k)

        out.append(str(profit))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()