Studying Algorithms

Time limit1sMemory limit512 MB

Summary
Given per-algorithm study costs and reductions from learning other algorithms, pick at least M algorithms so total accumulated study is minimized.
Level

Medium7 of 10

Topics
Greedy, Graph, Sorting, Implementation
Solved
No attempts yet

Problem

Heejung, who never has enough money, decided to enter HCPC, get a good result, and win prize money. To that end, she first hacked the laptop of Jungho, the head of the problem-setting committee, and learned that the scope of the contest is N algorithms and that the problems come from that scope. Now that she knows the scope, all Heejung has left to do is study the algorithms. Studying algorithms actually hides a special rule, as follows.

Learning each algorithm for the first time requires an amount of algorithm study equal to Ki. Some algorithms are related to each other, so learning one algorithm reduces the amount of study needed to learn another specific algorithm. When the study needed to learn one algorithm is reduced by several other algorithms, all of the reductions are summed and applied. Also, algorithm study is not consumed; it accumulates. For example, to learn both an algorithm that needs 3 study the first time and an algorithm that needs 5 study, the required amount is not their sum 8 but their maximum 5.

However, when she actually tried to study the algorithms, midterms were already closing in, so there was not enough time to learn every algorithm. Heejung decided to invest as little time as possible and study at least M algorithms. Given the study needed to learn each algorithm for the first time and the relations between the algorithms, your task is to find the amount of algorithm study needed to learn at least M algorithms.

Input

The first line gives a positive integer N, the number of algorithms in the scope, and a positive integer M, the minimum number of algorithms to learn. ( 1 ≤ M ≤ N ≤ 100,000 )

The second line gives N positive integers Ki, the amount of algorithm study needed to learn each algorithm for the first time, separated by spaces. (1 ≤ Ki ≤ 108)

The third line gives a positive integer R, the number of relations between algorithms that are related to each other. ( 0 ≤ R ≤ 100,000 )

Over the next K lines, each line gives A, B, D, meaning that learning algorithm A reduces the study needed to learn algorithm B by D. (1 ≤ A, B ≤ N, 1 ≤ D ≤ 108)

The same pair A and B is not given more than once, and no relation has A = B. Also, the study is guaranteed never to drop to 0 or below no matter how much it is reduced.

Output

Print the minimum amount of algorithm study needed to learn at least M algorithms.

Examples1

  1. Example 1

    Input
    4 3
18 20 77 82
3
1 3 60
1 4 3
3 4 60
    Expected output
    19