무지개 너머 어딘가

시간 제한: 2000 ms. 메모리 제한: 512 MB.

무지개를 그리고 싶다. 무지개는 정수 높이로 이루어진 수열 $a_0, a_1, \ldots, a_m$으로 나타낼 수 있으며, 다음 조건을 만족해야 한다.

• $a_0 = a_m = 0$ (무지개 양 끝의 높이는 지평선 위 0미터이다)
• 모든 $0 < i < m$에 대해 $2a_i > a_{i-1} + a_{i+1}$이다 (무지개는 볼록하다)
• $n$개의 쌍 $(x_i, y_i)$에 대해 $a_{x_i} \ge y_i$이다.

무지개가 차지하는 공간을 최소로 하고 싶다. $\sum a_i$의 최솟값을 구하라. 값이 매우 클 수 있으므로 998244353으로 나눈 나머지를 출력한다.

첫 줄에 양의 정수 $n$과 $m$ ($1 \le n \le 2 \cdot 10^5$, $1 \le m \le 10^9$)이 주어진다. $n$은 제약 조건의 개수, $m$은 수열의 길이다.

이어지는 $n$개의 줄마다 정수 $x_i$ ($1 \le x_i \le m - 1$)와 $y_i$ ($1 \le y_i \le 10^{18}$)가 주어지며, 이는 $a_{x_i} \ge y_i$ 조건을 뜻한다.

$x_1 < x_2 < \ldots < x_n$이 보장된다.

정수 하나를 출력한다. $\sum a_i$의 최솟값을 998244353으로 나눈 나머지이다.

입력 예시에서 최적의 높이 수열 중 하나는 $(0, 100, 82, 63, 43, 22, 0)$이다.