T53629 管道储液系统

题目背景

**BY 1704 CHY** A市有一个管道储液系统,每次可以用来存储很多A市生产出的一些有特殊性质的液体。

题目描述

管道系统一共有$M$条海拔水平一致的管道,每个管道都有一个容积$V_i$,管道由$N$个控制阀门(编号为$1$至$N$)相互连接。 由于一些原因,要使这些控制阀门在用管道互相连接后形成**一棵或多棵树**的结构。为了防止内部溶液流出,每条管道一定在两端各连接着控制阀门。 对于每条管道,都有一个允许的内部液体的相对压强范围$[B_i,E_i] (B_i \ge 0,E_i \ge 0)$表示该管道对可以装入的液体的要求。相对压强最小为0。 由于这些液体的特殊性质,你可以加固一些管道,加固后的管道在可容纳的液体相对压强范围会变为$[B_i - K, E_i + K]$。但是它的容积会比原来减少$W$。管道的体积减少为0的时候将不再连通。加固的操作可以重复多次。 在加入液体时从$1$号控制阀门加入且控制阀门不会允许一个管道流入不符合压强的范围的液体。

输入格式

第一行$5$个整数$N,M,K,W,D$,其中$N,M,K,W$表示描述中的值,$D$表示液体种类数量。 第$2$行到第$M + 1$行,每行$5$个整数$P_i,Q_i,V_i,B_i,E_i$,分别表示该管道连接的两个控制阀门,该管道的容积和该管道允许的相对压强范围$[B_i,E_i]$(保证$B_i \le E_i$)。 第$M + 2$行到第$M + D + 1$行每行一个整数$R$,表示每种液体的压强。

输出格式

共$D$行,表示每种液体装在该管道系统中的最大容积。

说明/提示

对于前20%的数据,保证$D = 1, N \le 100, M \le 1000, B_i = E_i, K = 0,W = 0$且第一个测试点$R = 7$, 第二个测试点$R = 13$ 对于前40%的数据,保证$D = 1, N \le 100, M \le 1000, B_i = E_i, K = 0,W = 0$ 对于前60%的数据,保证$D \le 10, K = 0, W = 0, N \le 500, M \le 10000$ 对于前100%的数据,保证$ D \le 10, N \le 5000, M \le 200000, V_i \le 10^9$