18631번 - Somewhere Over the Rainbow 다국어

You want to draw a rainbow. The rainbow can be represented as a sequence of integer heights a₀, a₁,. . . , a_m and must satisfy the following constraints:

• a₀ = a_m = 0 (the endpoints of the rainbow are 0 meters above the horizon),
• 2a_i > a_i−1 + a_i+1 for all 0 < i < m (the rainbow is convex),
• a_xi ≥ y_i for n given pairs (x_i, y_i).

You also want the rainbow to take as little space as possible, so please find the minimum possible value of Σa_i. Since the answer may be very large, output it modulo 998 244 353.

The first line of input contains two positive integers n and m (1 ≤ n ≤ 2 · 10⁵, 1 ≤ m ≤ 10⁹): the number of constraints and the length of the sequence.

Each of the next n lines contains two integers x_i (1 ≤ x_i ≤ m − 1) and y_i (1 ≤ y_i ≤ 10¹⁸), which set conditions a_xi ≥ y_i.

It is guaranteed that x₁ < x₂ < . . . < x_n.

Print one integer: the minimum value of Σa_i modulo 998 244 353.

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