25763번 - Standard Problem 다국어

You are given $n$ segments $[l_i,r_i]$ ($1 \le l_i \le r_i \le m$). Each segment has a weight $c_i$.

Let us choose a subsequence of segments, from each chosen segment choose an integer and arrange them in the same order as initial segments. By this operation we will get an integer sequence. We say that a subsequence of segments is good if we can construct a nondecreasing integer subsequence from it.

Let $k$ be the maximum weight of a good subsequence (the sum of weights of all segments in the subsequence). Calculate $k$ and the number of good subsequences of weight $k$. Since the number of subsequences can be large, calculate it modulo $998\,244\,353$.

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) --- the number of test cases. Description of test cases follows.

The first line of each test case contains two integers $n$, $m$ ($1 \le n, m \le 2 \cdot 10^5$).

Each of the next $n$ lines contains three integers $l_i$, $r_i$, $c_i$ ($1 \le l_i \le r_i \le m$, $1 \le c_i \le 10^9$) --- description of the $i$-th segment.

It is guaranteed that both the sum of $n$ and the sum of $m$ for all test cases do not exceed $2 \cdot 10^5$.

For each test case, print two integers --- the maximum weight of a good subsequence and the number of good subsequences with maximum weight (the second number modulo $998\,244\,353$).