P11780 [COTS 2012] 卡车通行 / AUTOCESTA

有一条长为 $L$ 公里的高速公路，开始的时候你有这里面 $0$ 公里的高速公路，公路按照 $1$ 公里进行划分，第 $i$ 公里购买的代价为 $X_i$。 你有 $n$ 辆卡车，每个卡车都有一条路线，用三个参数 $A,B,C$ 表示，即车从距离起点 $A$ 公里进入，然后从距离起点 $B$ 公里的位置离开，如果路上只要经过了未购买的高速公路，你就要花费 $C$ 的代价。 如果某公里的高速公路没有购买，那么这公里只能允许正方向和反方向不超过 $K$ 辆卡车通行。 你希望购买公路的代价和为车子缴纳的代价和最小，求出这个值。

在第一行中，有一个整数 $L$，以公里为单位的高速公路长度。 在下一行中，有 $L$ 个整数 $X_i$ 表高速公路每公里的购买价格。 接下来的一行一个整数 $n$，表卡车数量。 接下来 $n$ 行，每行三个整数 $a_i,b_i,c_i$，表示卡车的三个参数。 接下来一行一个整数 $K$，表示限制卡车的通过数的数量。

一行一个整数，表示最小代价。

【样例解释】 关于第一个样例的解释： - 如果不购买任何公里的高速公路，代价为 $800$ （两条路线每条代价 $400$ ）。 - 如果该买下整条高速公路，代价为 $900$。 - 如果以 $300$ 代价从位置 $1$ 到位置 $2$ 购买了一公里的高速公路，那么它将只支付第一条路线的通行费，因此总代价为 $700$。 【数据范围与约定】 对于全部数据，有 $1\le L,n \le 10^5,0\le X_i \le 10^9,1\le K \le100,0 \le a_i,b_i\le L,a_i \neq b_i,0\le c_i \le 10^6 $。 - 对于 $50 \%$ 的数据中，满足 $K = 1$ 。 - 对于 $34 \%$ 的数据中，满足 $n \le 10$ 。 - 对于 $68 \%$ 的数据中，上述两个条件中的至少一个将适用。 - 对于 $50 \%$ 的数据中，满足 $L \le 1000$。 - 对于 $66 \%$ 的数据中，满足 $n \le 1000$。 - 对于其他的数据，无特殊限制。