Problem Description

After finishing a business trip, Xiaoming returned to the city where the company is located. When filling out the travel reimbursement application, careless Xiaoming found that he lost the receipts from the trip.

To make up for Xiaoming’s loss, the company agrees that Xiaoming can use other receipts for reimbursement. However, the finance department requires that, among the receipts Xiaoming submits, the date difference between any two receipts must be at least $K$ days, and the total amount must not exceed the actual travel cost $M$.

For example, when the finance department requires $K=7$, if Xiaoming submits a receipt dated January 8, then he cannot submit any other receipt dated from January 2 to January 14. Receipts dated January 1 or earlier, and January 15 or later, can be submitted.

Xiaoming’s colleagues collected $N$ receipts for him. Now Xiaoming wants you to help him organize them: choose a set of receipts that satisfies the finance requirements, and make the total amount as close to $M$ as possible.

Note that since all these receipts are from the same year, receipts at the end of December will not affect whether receipts at the beginning of January can be submitted. This year is not a leap year.

Input Format

Line $1$: $3$ integers, $N, M, K$.

Lines $2 \ldots N+1$: each line contains $3$ integers $m_{i}, d_{i}, v_{i}$. Line $i+1$ describes the $i$-th receipt: its month $m_{i}$, day $d_{i}$, and face value $v_{i}$.

Output Format

Line $1$: $1$ integer, the maximum total reimbursement amount Xiaoming can achieve.

4 16 3
1 1 1
1 3 2
1 4 4
1 6 8

10

Hint

Sample Explanation

Choose the receipts dated January 3 and January 6.

Test Case Scale and Constraints

For $100\%$ of the test cases, $1 \leq N \leq 1000, 1 \leq M \leq 5000, 1 \leq K \leq 50, 1 \leq m_{i} \leq 12, 1 \leq d_{i} \leq 31, 1 \leq v_{i} \leq 400$.

The dates are guaranteed to be valid.

Lanqiao Cup 2022 National Contest, Group B, Problem F.

Translated by ChatGPT 5