Billboard Placement for Maximum Revenue

You are given a highway represented as a number line from 0 to n. Along the highway, there are billboard spots located at specific positions, each generating a certain revenue if a billboard is placed there. However, to avoid distractions, no two billboards can be placed within k miles of each other.

Your task is to choose a set of billboards to place along the highway so that the total revenue is maximized.

The problem can be modeled using dynamic programming. Let \(dp[i]\) be the maximum revenue achievable up to mile i and note that if a billboard is placed at position \(p\) with revenue \(r\), then if \(p \ge k+1\), the recurrence is given by:

[ \text{dp}[i] = \max \left{ \text{dp}[i-1], r + \text{dp}[p-k-1] \right} ]

Otherwise, if \(p < k+1\) then:

[ \text{dp}[i] = \max \left{ \text{dp}[i-1], r \right} ]

Determine the maximum revenue possible under the given constraints.

inputFormat

The input is given via standard input (stdin) in the following format:

n k m
pos1 r1
pos2 r2
... 
posm rm

where:

• n is the length of the highway.
• k is the minimum distance required between any two billboards.
• m is the number of available billboards.
• Each of the next m lines contains two integers: the position of the billboard (pos) and its associated revenue (r).

outputFormat

Output a single integer to standard output (stdout) which is the maximum revenue that can be obtained by optimally placing the billboards under the constraint that no two billboards are within k miles of each other.

## sample

10 5 4
6 5
7 6
2 10
9 8

18

</p>