小明在出差結(jié)束后返回了公司所在的城市,在填寫差旅報銷申請時,粗心的小明發(fā)現(xiàn)自己弄丟了出差過程中的票據(jù)。
為了彌補小明的損失,公司同意小明用別的票據(jù)進行報銷,但是公司財務要求小明提交的票據(jù)中任意兩張的日期差不小于 K 天,且總金額不得超過實際差旅費用 M。
比如財務要求 K = 7 時,若小明提交了一張 1 月 8 日的票據(jù),小明就不能提交 1 月 2 日至 1 月 14 日之間的其他票據(jù),1 月 1 日及之前和 1 月 15 日及之后的票據(jù)則可以提交。
公司的同事們一起給小明湊了 N 張票據(jù),小明現(xiàn)在想要請你幫他整理一下,從中選取出符合財務要求的票據(jù),并使總金額盡可能接近 M。
需要注意,由于這些票據(jù)都是同一年的,因此 12 月底的票據(jù)不會影響到 1 月初票據(jù)的提交。這一年不是閏年。
第 1 行:3 個整數(shù),N, M, K
第 2 . . . N + 1 行:每行 3 個整數(shù) mi , di , vi,第 i + 1 行表示第 i 張票據(jù)時間的月份 mi 和日期 di,vi 表示該票據(jù)的面值
4 16 3 1 1 1 1 3 2 1 4 4 1 6 8
10
選擇 1 月 3 日和 1 月 6 日的票據(jù)
對于 100% 的評測用例,1 ≤ N ≤ 1000, 1 ≤ M ≤ 5000, 1 ≤ K ≤ 50, 1 ≤ mi ≤ 12, 1 ≤ di ≤ 31, 1 ≤ vi ≤ 400
日期保證合法。
請對本次比賽進行一些描述,公告內(nèi)容應當包含:
比賽的創(chuàng)辦者或組織;
本次比賽的目的或意義;
本次比賽的考點、語言或類型;或其他注意事項及描述等。
至少保證30個漢字長度。