PP  特別喜歡玩即時(shí)戰(zhàn)略類(lèi)游戲，但他覺(jué)得那些游戲都有美中不足的地方。災(zāi)害總不降臨道路，而只降臨城市，而且道路不能被占領(lǐng)，沒(méi)有保護(hù)糧草的真實(shí)性。于是他就研發(fā)了《新三國(guó)爭(zhēng)霸》。 在這款游戲中，加入災(zāi)害對(duì)道路的影響（也就是一旦道路W[i，j]受到了災(zāi)害的影響，那么在一定時(shí)間內(nèi)，這條路將不能通過(guò)）和道路的占領(lǐng)權(quán)（對(duì)于一條道路W[i，j]，至少需要K[i，j]個(gè)士兵才能守住）。 PP可真是高手，不一會(huì)，就攻下了N-1座城市，加上原來(lái)的就有N座城市了，但他忽略了一點(diǎn)……那就是防守同樣重要，不過(guò)現(xiàn)在還來(lái)的及。因?yàn)椴糯蛲暾趟院芏喑鞘卸夹枰ㄔO(shè)，PP估算了一下，大概需要T天。他現(xiàn)在無(wú)暇分身進(jìn)攻了，只好在這T天內(nèi)好好的搞建設(shè)了。所以他秒要派士兵占領(lǐng)一些道路，以確保任何兩個(gè)城市之間都有路（不然敵人就要分而攻之了，是很危險(xiǎn)的）。士兵可不是白干活的，每個(gè)士兵每天都要吃掉V的軍糧。因?yàn)橛袨?zāi)害，所以方案可能有變化（每改變一次就需要K的軍糧，初始方案也需要K的軍糧）。 因?yàn)橛螒蚴荘P編的，所以他知道什么時(shí)候有災(zāi)害。PP可是一個(gè)很節(jié)約的人，他希望這T天在道路的防守上花最少的軍糧。 N< =300，M< =5000  ，T< =50；

第一行有5個(gè)整數(shù)N，M，T，V，K。N表示有城市數(shù)，M表示道路數(shù)，T表示需要修養(yǎng)的天數(shù)，V表示每個(gè)士兵每天吃掉的軍糧數(shù)，K表示修改一次花掉的軍糧數(shù)。 以下M行，每行3個(gè)數(shù)A，B，C。表示A與B有一條路（路是雙向的）需要C個(gè)士兵才能守住。 第M+2行是一個(gè)數(shù)P，表示有P個(gè)災(zāi)害。 以下P行，每行4個(gè)數(shù)，X，Y，T1，T2。表示X到Y(jié)的這條路，在T1到T2這幾天都會(huì)受災(zāi)害。

T天在道路的防守上花費(fèi)最少的軍糧。

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

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