蓝桥杯 2022 国 B 费用报销 类背包问题 思路类似于

[蓝桥杯 2022 国 B] 费用报销

题目描述

小明从出差结束回到公司所在地后，在准备提交差旅费用报销单据时,马虎的他不小心遗失了相关文件

为补偿小明的损失, 公司同意让小明使用其他票据来报销, 但须确保其任何两张票据间的日期间隔不得少于 K 天, 且总金额不能超过实际出差费用 M.

比如财务规定 K=7 的情况下，在小明呈交了某张日期为\texttt{1}月\texttt{8}日的票据之后，则无法再呈交日期在\texttt{1}月\texttt{2}日至\texttt{1}月\texttt{14}日之间的其他票据；而对于日期在\texttt{1}月\texttt{1}日及之前以及\texttt{1}月\texttt{15}日及之后的票据，则允许呈交。

公司在内部制作了$N$张票据分发给小明，请你希望他能将这些票据进行分类处理，并从这些票据中筛选出符合财务标准的文件，并尽量让总金额接近目标值 $M$。

需要特别留意的是：因为这些票据均属于同一年度的信息，在提交时即便到了12月底也无需担心其对未来月份的影响；而这一年也不是闰年

输入格式

第 1 行：3 个整数, N, M, K。

从第二行到第N+1行为止的数据段落中包含若干条记录信息

输出格式

第 1 行：1 个整数, 表示小明能够凑出的最大