Cheese Towers

You want to store blocks of cheese as a single tower whose total height is at most $T$ ($1 \le T \le 1000$).

There are $N$ ($1 \le N \le 100$) types of cheese, numbered $1$ through $N$, and you have an unlimited supply of blocks of every type. A block of type $i$ has value $V_i$ ($1 \le V_i \le 10^6$) and height $H_i$ ($5 \le H_i \le T$), where every $H_i$ is a multiple of $5$.

Cheese compresses. A block whose height is at least $K$ ($1 \le K \le T$) is called large. A large block crushes every block located below it in the tower, including other large blocks. A crushed block keeps its full value, but its height shrinks to exactly $4/5$ of its original height. Because every height is a multiple of $5$, a crushed height is always an integer. Crushing is all-or-nothing: a block is either crushed or not, and having several large blocks above it does not crush it any further. Whether a block is large depends only on that block's own height, never on the overall height of the tower.

Build a tower of total height at most $T$ that maximizes the sum of the values of its blocks, and output that maximum total value.

For example, suppose the tower may be at most $53$ tall, a block is large when its height is at least $25$, and there are three types of cheese:

Type    Value    Height
  1      100       25
  2       20        5
  3       40       10

One possible tower is:

          Type  Height  Value
   top -> [1]     25     100
          [2]      4      20   (crushed by [1] above)
          [3]      8      40   (crushed by [1] above)
          [3]      8      40   (crushed by [1] above)
bottom -> [3]      8      40   (crushed by [1] above)

The large block on top crushes every block beneath it. The total height is $25 + 4 + 8 + 8 + 8 = 53 \le 53$, so the tower is legal, and the total value is $100 + 20 + 40 + 40 + 40 = 240$. This is the best tower for this set of blocks.

• Line $1$: three space-separated integers $N$, $T$, and $K$.
• Lines $2$ through $N+1$: line $i+1$ contains two space-separated integers $V_i$ and $H_i$.

• One line: the maximum total value of a tower you can build.