" 找啊找啊找GF,找到一個好GF,吃頓飯啊拉拉手,你是我的好GF.再見." " 誒,別再見啊..."

七夕...七夕...七夕這個日子,對于sqybi這種單身的菜鳥來說是多么的痛苦...雖然他聽著這首叫做" 找啊找啊找GF" 的歌,他還是很痛苦.為了避免這種痛苦,sqybi決定要給自己找點事情干.

他去找到了七夕模擬賽的負責人zmc  MM,讓她給自己一個出題的任務(wù).經(jīng)過幾天的死纏爛打,zmc  MM終于同意了. 但是,拿到這個任務(wù)的sqybi發(fā)現(xiàn),原來出題比單身更讓人感到無聊-_-....所以,他決定了,要在出題的同時去辦另一件能夠使自己不無聊的事情--給自己找GF. 

sqybi現(xiàn)在看中了n個MM,我們不妨把她們編號1到n.請MM吃飯是要花錢的,我們假設(shè)請i號MM吃飯要花rmb[i]塊大洋.

而希望騙MM當自己GF是要費人品的,我們假設(shè)請第i號MM吃飯試圖讓她當自己GF的行為(不妨稱作泡該MM)要耗費rp[i]的人品.而對于每一個MM來說,sqybi都有一個對應(yīng)的搞定她的時間,對于第i個MM來說叫做time[i]. 

sqybi保證自己有足夠的魅力用time[i]的時間搞定第i個MM^_^. sqybi希望搞到盡量多的MM當自己的GF,這點是毋庸置疑的.但他不希望為此花費太多的時間(畢竟七夕賽的題目還沒出),所以他希望在保證搞到MM數(shù)量最多的情況下花費的總時間最少. sqybi現(xiàn)在有m塊大洋,他也通過一段時間的努力攢到了r的人品(這次為模擬賽出題也攢rp哦~~).

他憑借這些大洋和人品可以泡到一些MM.他想知道,自己泡到最多的MM花費的最少時間是多少. 注意sqybi在一個時刻只能去泡一個MM--如果同時泡兩個或以上的MM的話,她們會打起來的...

輸入的第一行是n,表示sqybi看中的MM數(shù)量.接下來有n行,依次表示編號為1,  2,  3,  ...,  n的一個MM的信息.每行表示一個MM的信息,有三個整數(shù):rmb,  rp和time.最后一行有兩個整數(shù),分別為m和r.

你只需要輸出一行,其中有一個整數(shù),表示sqybi在保證MM數(shù)量的情況下花費的最少總時間是多少.

零基礎(chǔ)同學可以先學習視頻課程，包含C/C++、Python、百練、藍橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習題，還有老師答疑，點擊這里了解課程詳情

名校訓(xùn)練 動態(tài)規(guī)劃