Cheese Tower

Farmer John has a cellar with room for one tower of cheese blocks with a maximum height of \( T \). He has a virtually unlimited supply of \( N \) different types of cheese blocks. Each cheese block type \( i \) has a height \( H_i \) (a multiple of 5) and a value \( V_i \). A cheese block is considered large if its height is at least \( K \). When a large block is placed, it crushes every block below it in the tower. A crushed block retains its original value, but its height is reduced to \( \frac{4}{5} \) of its original height (which is still an integer).

Farmer John wants to build a cheese tower with total height at most \( T \) while maximizing the total value. The tower is built by stacking blocks from bottom to top. Note that if no large block is used then all blocks remain uncrushed, and their height counts fully. However, if at least one large block is used, then every block below the top-most large block is considered crushed (using reduced height), while blocks placed above are not crushed.

The task is to determine the maximum total value Farmer John can achieve.

Example:

Suppose \( T = 53 \), \( K = 25 \), and there are 3 types of cheese blocks:

Block type 1 is large (since \( 25 \ge K \)) and, when used at the top of the tower, it remains uncrushed. The optimal tower from top to bottom is:

Top:      [Type 1]   Height = 25, Value = 100 (uncrushed)
          [Type 2]   Crushed height = 4, Value = 20
          [Type 3]   Crushed height = 8, Value = 40
          [Type 3]   Crushed height = 8, Value = 40
Bottom:   [Type 3]   Crushed height = 8, Value = 40

Total height: \( 25 + 4 + 8 + 8 + 8 = 53 \)

Total value: \( 100 + 20 + 40 + 40 + 40 = 240 \)

This is the best possible value under the constraints.

inputFormat

The first line contains three integers \( T \), \( K \), and \( N \) (with \( 1 \le T \le 1000 \), \( 1 \le N \le 100 \)). Each of the following \( N \) lines contains two integers \( H_i \) and \( V_i \) (with \( H_i \) a multiple of 5, \( 5 \le H_i \le T \) and \( 1 \le V_i \le 1{,}000{,}000 \)).

You have a virtually unlimited number of blocks of each type.

outputFormat

Output a single integer which is the maximum total value of a cheese tower of height at most \( T \), built under the rules described.

sample

53 25 3
25 100
5 20
10 40

240