[Usaco2010 Jan]Cheese Towers

Farmer John 准备在地窖中建造一座奶酪塔，以储存奶牛们生产的奶酪。奶酪塔的总高度不能超过 $T$ 。

共有 $N$ 种奶酪，编号为 $1$ 到 $N$ ，每种奶酪都有无限多块。第 $i$ 种奶酪每块的价值为 $V_i$ ，高度为 $H_i$ 。所有奶酪块的高度都是 $5$ 的倍数。

高度不小于 $K$ 的奶酪块称为大奶酪。若一块奶酪的上方存在至少一块大奶酪，那么它会被压缩，高度变为原来的 $\frac{4}{5}$ ，但价值不变。无论其上方有多少块大奶酪，每块奶酪都至多被压缩一次。只有单块大奶酪能够压缩其下方的奶酪，奶酪塔的总高度不会影响某块奶酪是否被压缩。

请在奶酪塔总高度不超过 $T$ 的条件下，求能够获得的最大总价值。

输入格式

第一行包含三个整数 $N$ 、 $T$ 、 $K$ ，分别表示奶酪种类数、奶酪塔的最大高度，以及大奶酪的高度下限。

接下来 $N$ 行，第 $i$ 行包含两个整数 $V_i$ 、 $H_i$ ，分别表示第 $i$ 种奶酪每块的价值和高度。

输出一个整数，表示合法奶酪塔能够获得的最大总价值。

一种最优方案是从塔顶到塔底依次放置种类为 $1,2,3,3,3$ 的奶酪块。

最上方的第 $1$ 种奶酪高度为 $25$ ，属于大奶酪，因此其下方的所有奶酪块都会被压缩。压缩后，第 $2$ 种奶酪的高度变为 $4$ ，每块第 $3$ 种奶酪的高度变为 $8$ 。

奶酪塔的总高度为

25+4+8+8+8=53,

总价值为

100+20+40+40+40=240.

因此答案为 $240$ 。

本题为 USACO 2010 January 试题「Cheese Towers」，题面与测试数据整理自 BZOJ。