问题描述

小明在出差结束后返回了公司所在的城市, 在填写差旅报销申请时, 粗心的小明发现自己弄丢了出差过程中的票据。

为了弥补小明的损失, 公司同意小明用别的票据进行报销, 但是公司财务要求小明提交的票据中任意两张的日期差不小于 $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 个整数, 表示小明能够凑出的最大报销金额。

选择 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$。

日期保证合法。