AT_awc0001_d 街道の商人

Takahashi is a merchant doing business along a highway that extends from east to west. There are $ N $ towns lined up in a row along this highway, numbered $ 1 $ , $ 2 $ , ..., $ N $ from west to east. Doing business in the $ i $ -th town yields a profit of $ A_i $ , but costs $ B_i $ yen as accommodation expenses. Takahashi has decided to select some of these towns to do business in. However, Takahashi's carriage has the following restriction: - The towns visited do not need to have consecutive numbers, but when the visited town numbers are arranged in ascending order, the difference between any two adjacent numbers must be at most $ K $ . In other words, if the visited town numbers in ascending order are $ p_1, p_2, \ldots, p_m $ , then $ p_{j+1} - p_j \leq K $ must hold for all $ 1 \leq j \leq m - 1 $ . This is because the carriage has a limit on the distance it can travel at once. The total accommodation expenses Takahashi can prepare is $ M $ yen. When selecting towns such that the total accommodation expenses of visited towns is at most $ M $ yen, find the maximum possible total profit. Note that if no town is visited, the total profit is $ 0 $ .

> $ N $ $ M $ $ K $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ : $ A_N $ $ B_N $ - The first line contains $ N $ representing the number of towns, $ M $ representing the total accommodation expenses available, and $ K $ representing the maximum number of towns that can be traveled at once, separated by spaces. - From the 2nd line to the $ (N + 1) $ -th line, information about each town is given. - The $ (1 + i) $ -th line contains the profit $ A_i $ obtainable in the $ i $ -th town and the accommodation expense $ B_i $ , separated by spaces.

Output in one line the maximum possible total profit when selecting towns that satisfy the conditions.

### Constraints - $ 1 \leq N \leq 200 $ - $ 1 \leq M \leq 200 $ - $ 1 \leq K \leq N $ - $ 1 \leq A_i \leq 10^9 $ - $ 1 \leq B_i \leq M $ - All inputs are integers