고속도로 구매

시간 제한1초메모리 제한128 MB

요약
구간별 매입 비용과 트럭별 경로 및 통행료, 그리고 방향별 최대 K대 제한이 있을 때 도로 매입비와 통행료 합의 최소값을 구하는 문제입니다.
난이도

어려움10점 중 8점

유형
그래프, 최단 경로, 동적 계획법
정답자
아직 제출이 없습니다

문제

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

고속도로는 길이가 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)

출력

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

예제2

  1. 예제 1

    입력
    3
300 300 300
2
0 3 400
2 1 400
99
    예상 출력
    700

  2. 예제 2

    입력
    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