Somewhere Over the Rainbow
시간 제한2초메모리 제한512 MB
양 끝이 0이고 주어진 위치에서 하한을 만족하는 볼록 정수 수열의 합의 최솟값을 998244353으로 나눈 나머지를 구한다.
문제
You want to draw a rainbow. The rainbow can be represented as a sequence of integer heights a0, a1,. . . , am and must satisfy the following constraints:
- a0 = am = 0 (the endpoints of the rainbow are 0 meters above the horizon),
- 2ai > ai−1 + ai+1 for all 0 < i < m (the rainbow is convex),
- axi ≥ yi for n given pairs (xi, yi).
You also want the rainbow to take as little space as possible, so please find the minimum possible value of Σai. 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 · 105, 1 ≤ m ≤ 109): the number of constraints and the length of the sequence.
Each of the next n lines contains two integers xi (1 ≤ xi ≤ m − 1) and yi (1 ≤ yi ≤ 1018), which set conditions axi ≥ yi.
It is guaranteed that x1 < x2 < . . . < xn.
출력
Print one integer: the minimum value of Σai modulo 998 244 353.
힌트
In the sample case, one optimal height sequence is (0, 100, 82, 63, 43, 22, 0).