小明在出差結(jié)束后返回了公司所在的城市，在填寫差旅報(bào)銷申請(qǐng)時(shí)，粗心的小明發(fā)現(xiàn)自己弄丟了出差過程中的票據(jù)。

為了彌補(bǔ)小明的損失，公司同意小明用別的票據(jù)進(jìn)行報(bào)銷，但是公司財(cái)務(wù)要求小明提交的票據(jù)中任意兩張的日期差不小于 K 天，且總金額不得超過實(shí)際差旅費(fèi)用 M。

比如財(cái)務(wù)要求 K = 7 時(shí)，若小明提交了一張 1 月 8 日的票據(jù)，小明就不能提交 1 月 2 日至 1 月 14 日之間的其他票據(jù)，1 月 1 日及之前和 1 月 15 日及之后的票據(jù)則可以提交。

公司的同事們一起給小明湊了 N 張票據(jù)，小明現(xiàn)在想要請(qǐng)你幫他整理一下，從中選取出符合財(cái)務(wù)要求的票據(jù)，并使總金額盡可能接近 M。

需要注意，由于這些票據(jù)都是同一年的，因此 12 月底的票據(jù)不會(huì)影響到 1 月初票據(jù)的提交。這一年不是閏年。 

第 1 行：3 個(gè)整數(shù)，N, M, K

第 2 . . . N + 1 行：每行 3 個(gè)整數(shù) m_i , d_i , v_i，第 i + 1 行表示第 i 張票據(jù)時(shí)間的月份 m_i 和日期 d_i，v_i 表示該票據(jù)的面值 

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

10

選擇 1 月 3 日和 1 月 6 日的票據(jù)

對(duì)于 100% 的評(píng)測(cè)用例，1 ≤ N ≤ 1000, 1 ≤ M ≤ 5000, 1 ≤ K ≤ 50, 1 ≤ m_i ≤ 12, 1 ≤ d_i ≤ 31, 1 ≤ v_i ≤ 400

日期保證合法。