题目描述

小华在出差返回公司后，准备提交差旅报销申请。可惜粗心的她把出差期间的票据弄丢了，只好请同事们帮忙凑一些替代票据。

不过公司财务有严格规定：提交的票据中，任意两张的日期差必须不小于 $K$ 天，且所有票据的总面值不得超过实际差旅费用 $M$。

举个例子，假设 $K=7$，如果小华提交了一张 3 月 15 日的票据，那么 3 月 9 日至 3 月 21 日之间的其他票据都不能再提交，但 3 月 8 日及之前或 3 月 22 日及之后的票据则不受影响。

同事们一共凑出了 $N$ 张票据，每张票据记录了月份、日期和面值。请帮小华从中选出符合财务规定的票据子集，使得总面值尽可能接近但不超过 $M$。

注意：所有票据都在同一年内，因此 12 月底的票据不会影响到 1 月初票据的提交。这一年不是闰年。

输入格式

第 $1$ 行：$3$ 个整数 $N, M, K$，分别表示票据数量、最大报销金额和最小日期间隔天数。

第 $2 \sim N+1$ 行：每行 $3$ 个整数 $m_i, d_i, v_i$，分别表示第 $i$ 张票据的月份、日期和面值。

输出格式

第 $1$ 行：$1$ 个整数，表示小华能够报销的最大总面值。

样例

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

10

提示

【样例说明】

选择 1 月 3 日和 1 月 6 日的票据，总面值为 $2+8=10$。

【评测用例规模与约定】

对于 $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$。

日期保证合法。