Background

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

Description

为了弥补小明的损失，公司同意小明用别的票据进行报销，但是公司财务要求小明提交的票据中任意两张的日期差不小于$K$天，且总金额不得超过实际差旅费用$M$。

比如财务要求$K$ =7时，若小明提交了一张1月8日的票据，小明就不能提交1月2日至1月14日之间的其他票据，1月1日及之前和1月15日及之后的票据则可以提交。

公司的同事们一起给小明凑了$N$张票据，小明现在想要请你帮他整理一下，从中选取出符合财务要求的票据，并使总金额尽可能接近$M$。

需要注意，由于这些票据都是同一年的，因此12月底的票据不会影响到1月初票据的提交。这一年不是闰年。

Format

Input

第1行:3个整数$N,M,K$

第2...N＋1行:每行3个整数$m_i,d_i,v_i$

第i＋1行表示第i张票据时间的月份$m_i$和日期$d_i$,$v_i$表示该票据的面值

Output

第1行:1个整数，表示小明能够凑出的最大报销金额

Samples

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

10

样例说明

选择1月3日和1月6日的票据

Limitation

对于100%的评测用例，$1≤N ≤1000,1 ≤ M ≤5000,1 ≤ K≤50,1 ≤m_i ≤12,1 ≤d_i ≤ 31,1 ≤v_i≤400$

日期保证合法。