The Jump Game released by KOI is a game where you pass through $N$ platforms arranged in a line by performing several jumps. Specifically, there are $N$ platforms on a number line, and each platform is numbered $0, 1, \dots, N-1$ from left to right. At the beginning of the game, the protagonist is on the leftmost platform, platform 0, and starts with a score of 0.

For every $0 \le i \le N-1$, the protagonist chooses one of two actions on platform $i$: walking or jumping. If the protagonist chooses to walk, they move to platform $i+1$, and the score does not change. If the protagonist chooses to jump, they move to platform $i+K$, and the score increases by $A[i]$. Here, $K$ is a predetermined number. The game ends successfully when the protagonist moves to the right of platform $N-1$. In the game, this is treated as reaching platforms $N, N+1, \dots$ — platforms with a number $N$ or greater do not actually exist, but are considered to be to the right of platform $N-1$. The goal of the game is to control the protagonist appropriately to maximize the score and finish the game.

Sang-hyeok, who enjoys internet broadcasting as a hobby, occasionally plays KOI's Jump Game. Although Sang-hyeok enjoys the game in his own way, it unfortunately does not receive a very good response from his viewers. The reason the Jump Game is not popular with viewers is that the game is extremely difficult and boring. First, the number of platforms in this game can reach as many as $10^{12}$. Second, even the excellent developers at KOI could not design all these platforms, so they constructed each platform in a somewhat simple way. After initially setting all $A[i]$ to 0, the developers at KOI perform the following operation $Q$ times: for each $j$ ($0 \le j \le Q-1$), they choose an interval $0 \le L[j] \le R[j] \le N-1$ and increase $A[L[j]], A[L[j]+1], A[L[j]+2], \dots, A[R[j]]$ by 1. The array $A$ after all operations are completed becomes the score obtained when choosing to jump from each platform in the game.

As someone who creates videos about computer science, you thought about making a video on how to finish KOI's Jump Game with the maximum score. You think this video will be very popular with the fans who enjoy Sang-hyeok's internet broadcasts, but you are worried that the game is too large for an efficient algorithm to exist. Let's overcome all difficulties and become the best at this game within the given 5 hours.

Implementation Details

You must implement the following function:

long long play_game(long long N, int Q, long long K, vector<long long> L,
vector<long long> R)

• $N$: The number of platforms in the game.
• $Q$: The number of operations performed by the developers.
• $K$: The parameter that determines the next platform reached after a jump.
• $L, R$: Integer arrays of size $Q$.
• This function returns a single integer representing the maximum score that can be obtained when the jump game ends.
• This function is called exactly once for each test case.

You must not execute any input/output functions in any part of your submitted source code.

Constraints

• $1 \le N \le 10^{12}$
• $1 \le Q \le 250\,000$
• $1 \le K \le N$
• For all $0 \le j \le Q-1$, $0 \le L[j] \le R[j] \le N-1$

Subtasks

1. (6 points) $N \le 250\,000$
2. (2 points) $K = 1$
3. (13 points) $2K \ge N$
4. (15 points) $5K \ge N$
5. (16 points) $Q \le 500$
6. (7 points) $Q \le 5\,000$
7. (41 points) No additional constraints.

Examples

Input 1

3 5 2
0 2
0 2
1 1
1 1
1 1

Output 1

5

Note

The array obtained after performing $Q$ operations is $[2, 5, 2]$. In this case, the maximum score that can be obtained is 5. One way to obtain a score of 5 is as follows: Walk on platform 0. Jump from platform 1 and gain 5 points. * Since $3 \ge N$, the game ends.

Input 2

250 8 50
0 200
40 140
49 49
50 150
100 190
149 199
199 199
75 249

Output 2

17

Input 3

250 8 49
0 200
40 140
49 49
50 150
100 190
149 199
199 199
75 249

Output 3

19

Input 4

100 6 50
0 99
0 70
0 10
20 30
40 50
60 70

Output 4

6

Input 5

1000000000000 2 1
0 999999999999
0 999999999999

Output 5

2000000000000

The sample grader receives input in the following format:

• Line 1: $N \ Q \ K$
• Line 2 + $i$ ($0 \le i \le Q-1$): $L[i] \ R[i]$

The sample grader outputs the following:

• Line 1: The value returned by play_game

Note that the sample grader may differ from the grader used in actual grading.