Jump Game

KOI Corp's jump game asks the player to cross $N$ platforms arranged in a row, using several jumps. The $N$ platforms sit on a vertical line and are numbered $0, 1, \dots, N-1$ from left to right. At the start, the player stands on platform 0, the leftmost one, with a score of 0.

For every $0 \le i \le N-1$, the player chooses either walk or jump on platform $i$. Walking moves the player to platform $i+1$ and leaves the score unchanged. Jumping moves the player to platform $i+K$ and increases the score by $A[i]$, where $K$ is a fixed number. The game ends successfully once the player moves past platform $N-1$. Platforms numbered $N, N+1, \dots$ do not exist, but reaching any of them counts as moving past platform $N-1$. The goal is to steer the player so that the final score is as large as possible and the game ends.

The KOI developers could not design so many platforms by hand, so they built them with a simple method. They set every $A[i]$ to 0, then perform $Q$ operations. 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 each of $A[L[j]], A[L[j]+1], \dots, A[R[j]]$ by 1. After all operations, the array $A$ gives the score earned by jumping from each platform.

You are making a video about computer science that explains how to finish the KOI jump game with the maximum score. The game has up to $N = 10^{12}$ platforms, so you need an efficient algorithm.

• $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$