小明在出差結(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ù) mi , di , vi,第 i + 1 行表示第 i 張票據(jù)時(shí)間的月份 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ù)
對(duì)于 100% 的評(píng)測(cè)用例,1 ≤ N ≤ 1000, 1 ≤ M ≤ 5000, 1 ≤ K ≤ 50, 1 ≤ mi ≤ 12, 1 ≤ di ≤ 31, 1 ≤ vi ≤ 400
日期保證合法。
1. 對(duì)于編程題目,要求選手給出的解答完全符合 GNU C/C++ 標(biāo)準(zhǔn),不能使用諸如繪圖、Win32API、中斷調(diào)用、硬件操作或與操作系統(tǒng)相關(guān)的 API。
2. 代碼中允許使用 STL 類庫。
3. main 函數(shù)結(jié)束必須返回 0。
4. 所有依賴的函數(shù)必須明確地在源文件中 #include
5. 提交時(shí),注意選擇使用C或C++語言。