题目描述

有一条长为 $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$，表示限制卡车的通过数的数量。

输出格式

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

3 
300 300 300 
2 
0 3 400 
2 1 400 
99

700

10 
1 3 3 1 1 1 2 2 2 3 
5 
0 10 2 
1 5 4 
1 4 4 
9 0 2 
10 9 4 
2 

15

提示

【样例解释】

关于第一个样例的解释：

• 如果不购买任何公里的高速公路，代价为 $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$。
• 对于其他的数据，无特殊限制。