你想画一道彩虹。彩虹可以用一个整数高度序列 $a_0, a_1, \dots, a_m$ 来表示，且必须满足以下约束：

• $a_0 = a_m = 0$（彩虹的端点位于地平线上方 0 米处），
• $2a_i > a_{i-1} + a_{i+1}$，对于所有 $0 < i < m$ 成立（彩虹是凸的），
• $a_{x_i} \ge y_i$，对于给定的 $n$ 个数对 $(x_i, y_i)$ 成立。

你还希望彩虹占用的空间尽可能小，因此请找到 $\sum_{i=0}^{m} a_i$ 的最小值。 由于答案可能非常大，请将其对 $998\,244\,353$ 取模后输出。

输入格式

第一行包含两个正整数 $n$ 和 $m$ ($1 \le n \le 2 \cdot 10^5, 1 \le m \le 10^9$)：约束的数量和序列的长度。 接下来的 $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 < \dots < x_n$。

输出格式

输出一个整数：$\sum_{i=0}^{m} a_i$ 的最小值，对 $998\,244\,353$ 取模。

样例

样例输入 1

3 6
1 100
4 42
5 22

样例输出 1

310

说明

在样例中，一个最优的高度序列是 $(0, 100, 82, 63, 43, 22, 0)$。