暂无测试数据。

题目描述

Farmer John wants to save some blocks of his cows' delicious Wisconsin cheese varieties in his cellar for the coming winter. He has room for one tower of cheese in his cellar, and that tower's height can be at most \(T (1 <= T <= 1,000)\). The cows have provided him with a virtually unlimited number of blocks of each kind of \(N (1 <= N <= 100)\) different types of cheese (conveniently numbered \(1,2,3,\cdots,N\)). He'd like to store (subject to the constraints of height) the most

valuable set of blocks he possibly can. The cows will sell the rest to support the orphan calves association.

Each block of the i-th type of cheese has some value \(V_i (1 \leq V_i \leq 1,000,000)\) and some height \(H_i (5 <= H_i <= T)\), which is always a multiple of \(5\).

Cheese compresses. A block of cheese that has height greater than or equal to \(K (1 \leq K \leq T)\) is considered 'large' and will crush any and all of the cheese blocks (even other large ones) located below it in the tower. A crushed block of cheese doesn't lose any value, but its height reduces to just \(\frac{4}{5}\) of its old height. Because the height of a block of cheese is always a multiple of \(5\), the height of a crushed block of cheese will always be an integer. A block of cheese is either crushed or not crushed; having multiple large blocks above it does not crush it more. Only tall blocks of cheese crush other blocks; aggregate height of a tower does not affect whether a block is crushed or not.

What is the total value of the best cheese tower FJ can construct?

输入

• Line \(1\): Three space-separated integers: \(N\), \(T\), and \(K\)
• Lines \(2\) to \(N+1\): Line \(i+1\) contains two space separated integers: \(V_i\) and \(H_i\).

输出

• Line \(1\): The value of the best tower FJ can build