题目描述 

Description

PP 特别喜欢玩即时战略类游戏，但他觉得那些游戏都有美中不足的地方。灾害总不降临道路，而只降临城市，而且道路不能被占领，没有保护粮草的真实性。于是他就研发了《新三国争霸》。

在这款游戏中，加入灾害对道路的影响（也就是一旦道路W[i，j]受到了灾害的影响，那么在一定时间内，这条路将不能通过）和道路的占领权（对于一条道路W[i，j]，至少需要K[i，j]个士兵才能守住）。

PP可真是高手，不一会，就攻下了N-1座城市，加上原来的就有N座城市了，但他忽略了一点……那就是防守同样重要，不过现在还来的及。因为才打完仗所以很多城市都需要建设，PP估算了一下，大概需要T天。他现在无暇分身进攻了，只好在这T天内好好的搞建设了。所以他秒要派士兵占领一些道路，以确保任何两个城市之间都有路（不然敌人就要分而攻之了，是很危险的）。士兵可不是白干活的，每个士兵每天都要吃掉V的军粮。因为有灾害，所以方案可能有变化（每改变一次就需要K的军粮，初始方案也需要K的军粮）。

因为游戏是PP编的，所以他知道什么时候有灾害。PP可是一个很节约的人，他希望这T天在道路的防守上花最少的军粮。

N<=300，M<=5000 ，T<=50；

输入描述 

Input Description

第一行有5个整数N，M，T，V，K。N表示有城市数，M表示道路数，T表示需要修养的天数，V表示每个士兵每天吃掉的军粮数，K表示修改一次花掉的军粮数。

以下M行，每行3个数A，B，C。表示A与B有一条路（路是双向的）需要C个士兵才能守住。

第M+2行是一个数P，表示有P个灾害。

以下P行，每行4个数，X，Y，T1，T2。表示X到Y的这条路，在T1到T2这几天都会受灾害。

输出描述 

Output Description

T天在道路的防守上花费最少的军粮。

样例输入 

Sample Input

3 3 5 10 30

1 2 1

2 3 2

1 3 4

1

1 3 2 5

样例输出 

Sample Output

180

数据范围及提示 

Data Size & Hint

各个测试点1s

 

最小生成树+DP

先处理出第i天到第j天之间通用的最小生成树，记作sol[i][j]

然后dp，决策某连续的一段时间内用同一个方案：

f[i]=min(f[i],f[j]+sol[j+1][i]*(每人耗粮数)*(天数i-j)+k)

 

1 /*by SilverN*/ 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 using namespace std; 9 const int mxn=320;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}14 return x*f;15 }16 //17 struct edge{18 int x,y,dis;19 }e[6010];20 int cmp(edge a,edge b){ return a.dis