费用报销 ### 问题描述 小明在出差结束后返回了公司所在的城市, 在填写差旅报销申请时, 粗心 的小明发现自己弄丢了出差过程中的票据。 为了弥补小明的损失, 公司同意小明用别的票据进行报销, 但是公司财务 要求小明提交的票据中任意两张的日期差不小于 $K$ 天, 且总金额不得超过实际 差旅费用 $M$ 。 比如财务要求 $K=7$ 时, 若小明提交了一张 1 月 8 日的票据, 小明就不能 提交 1 月 2 日至 1 月 14 日之间的其他票据, 1 月 1 日及之前和 1 月 15 日及之 后的票据则可以提交。 公司的同事们一起给小明凑了 $N$ 张票据, 小明现在想要请你帮他整理一 下, 从中选取出符合财务要求的票据, 并使总金额尽可能接近 $M$ 。 需要注意, 由于这些票据都是同一年的, 因此 12 月底的票据不会影响到 1 月初票据的提交。这一年不是闰年。 ### 输入格式 第 1 行： 3 个整数, $N, M, K$ 第 $2 \ldots N+1$ 行: 每行 3 个整数 $m_{i}, d_{i}, v_{i}$, 第 $i+1$ 行表示第 $i$ 张票据时间 的月份 $m_{i}$ 和日期 $d_{i}, v_{i}$ 表示该票据的面值 ### 输出格式 第 1 行: 1 个整数, 表示小明能够凑出的最大报销金额 ### 样例输入 ```text 4 16 3 1 1 1 1 3 2 1 4 4 1 6 8 ``` ### 样例输出 ```text 10 ``` ### 样例说明 选择 1 月 3 日和 1 月 6 日的票据 ### 评测用例规模与约定 对于 $100 \\%$ 的评测用例, $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$ 日期保证合法。