Receipt Selection Optimization

During a business trip, Xiao Ming lost his original receipts and now needs to submit alternative receipts for reimbursement. The finance department accepts other receipts provided that (i) the date difference between any two submitted receipts is at least \(K\) days, and (ii) the total amount does not exceed the actual travel cost \(M\). Note that if a receipt dated \(d\) is chosen, then any other receipt dated between \(d-K+1\) and \(d+K-1\) (inclusive) cannot be chosen. Also, since all receipts are from the same non‐leap year, receipts from December do not affect those from January.

You are given \(N\) receipts. Each receipt is represented by its date (as the day of the year, an integer between 1 and 365) and its amount. Your task is to select a set of receipts that satisfies the finance department's requirements and has a total amount as close to \(M\) as possible (i.e. the maximum total amount not exceeding \(M\)).

Input Constraints:

• \(1 \leq N \leq \text{small}\) (suitable for DP with state dimensions \(N\) and \(M\))
• \(1 \leq K \leq 365\)
• \(M\) is a non-negative integer.

inputFormat

The first line contains three integers \(N\), \(K\), and \(M\), where \(N\) is the number of receipts, \(K\) is the minimum allowed day gap between any two selected receipts, and \(M\) is the maximum total amount allowed.

Each of the next \(N\) lines contains two integers: day and amount. Here, day (1 ≤ day ≤ 365) represents the day of the year the receipt was issued, and amount represents its monetary value.

outputFormat

Output a single integer: the maximum total amount obtainable from a subset of receipts that meets the requirements, without exceeding \(M\).

sample

4 7 50
5 10
1 20
15 25
8 15

45