hackercupai/hackercup huggingface dataset:
Metal Platforms, Inc. (a.k.a. Metal), formerly a mining company, now offers a service to facilitate sheet metal sales. It has \(N\) clients, where client \(i\) wants to buy *only on* day \(A_i\) for \(\$X_i\) per sheet, and sell *only on* a strictly later day \(B_i\) for \(\$Y_i\) per sheet.

Client \(i\) can sell to client \(j\) if \(B_i = A_j\), and if client \(j\) is buying for a *strictly higher* price than what client \(i\) is selling for, i.e. if \(X_j > Y_i\). If Metal facilitates the sale, they earn a profit of \(\$(X_j - Y_i)\).

A *path* is any ordered sequence of clients where each client can sell to the next. A path's profit is the total profit that Metal would make if a single sheet were theoretically sold along it.

Metal would like to know the total profit across the \(K\) most profitable paths (or across all distinct paths if there are fewer than \(K\)). Since this may be large, please print it modulo \(1{,}000{,}000{,}007\).

# Constraints

\(1 \le T \le 35\)
\(1 \le N, K \le 1{,}000{,}000\)
\(1 \le N * K \le 1{,}000{,}000\)
\(1 \le A_i < B_i \le 10^9\)
\(1 \le X_i, Y_i \le 10^9\)

The sum of \(N\) over all test cases is at most \(6{,}000{,}000\).
The sum of \(N*K\) over all cases is at most \(20{,}000{,}000\).

# Input Format

Input begins with a single integer \(T\), the number of test cases. For each test case, there is first a line containing two space-separated integers \(N\) and \(K\). Then, \(N\) lines follow, the \(i\)th of which contains four space-separated integers \(A_i\), \(B_i\), \(X_i\), and \(Y_i\).

# Output Format

For the \(i\)th test case, output a single line containing `"Case #i: "` followed by a single integer, the total profit of the \(K\) most profitable paths, modulo \(1{,}000{,}000{,}007\).

# Sample Explanation

The first case is depicted below, with buy prices in green and sell prices in red. The figure on the right outlines all potential sales, along with how much profit Metal would make.

{{PHOTO_ID:5415230591886835|WIDTH:700}}

The valid paths are:

- \(P_1 = [1, 2]\) with profit \(\$25 - \$20 = \$5\).
- \(P_2 = [1, 2, 4]\) with profit \((\$25 - \$20) + (\$35 - \$30)\) \(= \$10\).
- \(P_3 = [1, 2, 4, 6]\) with profit \((\$25 - \$20) + (\$35 - \$30) + (\$45 - \$20)\) \(= \$35\).
- \(P_4 = [2, 4]\) with profit \(\$5\).
- \(P_5 = [2, 4, 6]\) with profit \(\$5 + (\$45 - \$20)\) \(= \$30\).
- \(P_6 = [4, 6]\) with profit \(\$45 - \$20 = \$25\).
- \(P_7 = [5, 6]\) with profit \(\$45 - \$15 = \$30\).

Note that sales from clients \(3\) to \(4\) and clients \(6\) to \(7\) are not possible, since the buyers' prices must be strictly higher than the sellers'. Since there are fewer than \(K=10\) paths, the answer is just the sum of profits of all paths, equal to \(\$5 + \$10 + \$35 + \$5 + \$30 + \$25 + \$30 = \$140\).

The second case is the same as the first, except we're only interested in the top \(6\) most profitable paths, so we must exclude either \(P_1\) or \(P_4\) for a total profit of \(\$135\).

In the third case, no sales are possible, so we simply report \(\$0\).

In the fourth case, the only possible path is \([2, 1]\), with a profit of \(\$30 - \$20 = \$10\).