고속도로 구매

트럭 회사를 운영하는 상근이는 내년 통행료를 줄이기 위해 고속도로의 일부 구간을 직접 사려고 한다.

고속도로는 길이가 1km인 구간 L개로 나뉘어 있으며, 각 구간을 사는 비용은 서로 다를 수 있다. 상근이가 소유한 구간만 지나가는 트럭은 통행료를 내지 않는다. 반대로, 경로에 상근이가 소유하지 않은 구간이 하나라도 있으면 그 트럭은 정해진 통행료 C를 한 번 낸다. 통행료는 지나간 구간 수와 관계없다.

상근이는 내년에 운행할 각 트럭의 경로를 알고 있다. 한 경로는 세 정수 A, B, C로 주어진다. 트럭은 고속도로 시작점에서 A km 떨어진 지점으로 들어와 B km 떨어진 지점으로 나가며, 총 |B-A|개의 1km 구간을 지난다.

이 나라에는 같은 방향으로 한 구간을 지나는 차량 수가 최대 K대여야 한다는 법이 있다. 반대 방향도 독립적으로 최대 K대까지 허용된다. 단, 상근이가 소유한 구간에는 이 제한이 적용되지 않는다.

고속도로 구간을 사는 비용과 트럭들이 내는 통행료의 합이 최소가 되도록 할 때, 그 최소 비용을 구하라.

첫째 줄에 고속도로의 총 길이 L이 주어진다. (1 <= L <= 100,000)

둘째 줄에 L개의 정수 X_i가 주어진다. X_i는 i번 1km 구간을 사는 비용이다. (0 <= X_i <= 1,000,000,000)

셋째 줄에 트럭의 수 N이 주어진다. (1 <= N <= 100,000)

다음 N개 줄에는 i번 트럭의 운행 정보 A_i, B_i, C_i가 주어진다. 트럭은 A_i km 지점에서 들어와 B_i km 지점에서 나간다. (0 <= A_i, B_i <= L, A_i != B_i, 0 <= C_i <= 1,000,000,000)

마지막 줄에 K가 주어진다. (1 <= K <= 100)

다음 해에 회사를 운영하는 데 드는 최소 비용을 출력한다.