Background

Special for beginners, ^_^

Description

给定 N(1 <= N <=100)种不同的面包，每种面包数量不限，每种面包的高度为 Hi(5 <=Hi <= T)，价值为Vi（1 <= Vi<= 1,000,000），现在要用这些面包垒高度不超过 T (1 <= T<= 1,000)的面包塔，假设面包无限宽，可以一个叠一个，不考虑塔会倒掉。一个高度>=K(1<= K <= T)的面包会挤压它下面的所有面包，所有被挤压的面包价值不变，但是高度会变成原来的 4/5（原来的高度是 5的倍数，既使被多次挤压，也仅会变成原来高度的 4/5）。现 在问你，能垒出高度不超过 T的，价值最大的塔的价值是多少。

Format

Input

第一行为 N，T，K，如题意，以下 N 行，每行两个用空格间隔开的整数，分别表示 Vi和 Hi。

Output

最大的价值

Samples

3 53 25 
100 25 
20 5 
40 10

240

Limitation

1s, 1024KiB for each test case.