Jump Game Maximum Score

This problem is translated from the 2024 International Information Olympiad Representative Student Selection Contest (2nd Selection) T2 "Jump Game".

The KOI company has launched the Jump Game. In this game, there are N platforms arranged in a line and numbered from 0 to N-1 from left to right. The protagonist starts at platform 0 with an initial score of 0.

For each platform i (where 0 \le i \le N-1), the player can either take a step or perform a jump:

• Step: Move from platform i to platform i+1 without changing the score.
• Jump: Move from platform i to platform i+K and add a score of A[i] to the current score. Here, K is a given constant.

The game is completed successfully when the protagonist reaches any platform with an index \( \ge N \) (that is, after passing the last platform numbered N-1).

The array \(A\) is generated as follows. Initially, all \(A[i]\) are set to 0. Then, there are Q operations. In the \(j\)th operation (\(0 \le j \le Q-1\)), an interval \([L[j], R[j]]\) is chosen (with \(0 \le L[j] \le R[j] \le N-1\)), and for every index \(i\) in the interval \(L[j] \le i \le R[j]\), the value \(A[i]\) is increased by 1.

Your task is to compute the maximum score that can be obtained when finishing the game, by controlling the protagonist's moves optimally.

---

Function Specification

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 fixed constant that determines the jump length.
• L, R: Two arrays of size Q representing the intervals used to increment the scores on the platforms. After all operations, the value on platform i is the total number of operations that cover i.

The function should return the maximum score achievable when finishing the game. A finish is defined by making a move that lands the protagonist on a platform numbered \( \ge N \). Note that if a move would take you to a platform \( \ge N \), the game ends immediately, and no further moves are allowed.

Note on the moves:

• If a step is taken from platform i (where \(i + 1 \ge N\)), the game ends without any change in the score.
• If a jump is taken from platform i (where \(i + K \ge N\)), the game ends and the score increases by \(A[i]\).

Your solutions in all five languages must implement the same logic and pass the test cases provided.

inputFormat

The input consists of multiple lines:

1. The first line contains three space-separated integers: N, Q, and K.
2. The second line contains Q space-separated integers representing the array L.
3. The third line contains Q space-separated integers representing the array R.

It is guaranteed that \(0 \le L[j] \le R[j] \le N-1\) for all \(0 \le j \lt Q\).

outputFormat

Output a single integer representing the maximum score achievable when finishing the game.

sample

5 2 2
1 3
1 3

2