Somewhere Over the Rainbow

Time limit: 2000 ms. Memory limit: 512 MB.

You want to draw a rainbow. The rainbow can be represented as a sequence of integer heights $a_0, a_1, \ldots, a_m$ that must satisfy the following constraints:

• $a_0 = a_m = 0$ (both endpoints are 0 meters above the horizon)
• $2a_i > a_{i-1} + a_{i+1}$ for all $0 < i < m$ (the rainbow is convex)
• $a_{x_i} \ge y_i$ for $n$ given pairs $(x_i, y_i)$.

You also want the rainbow to take as little space as possible. Find the minimum possible value of $\sum a_i$. Since the answer may be very large, output it modulo 998244353.

The first line contains two positive integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$, $1 \le m \le 10^9$): the number of constraints and the length of the sequence.

Each of the next $n$ lines contains two integers $x_i$ ($1 \le x_i \le m - 1$) and $y_i$ ($1 \le y_i \le 10^{18}$), which set the condition $a_{x_i} \ge y_i$.

It is guaranteed that $x_1 < x_2 < \ldots < x_n$.

Print one integer: the minimum value of $\sum a_i$ modulo 998244353.

In the sample case, one optimal height sequence is $(0, 100, 82, 63, 43, 22, 0)$.