sland Hopping with Treasure

$/$ Problem Statement

You're a pirate captain with a treasure map. The map shows islands connected by bridges, and each island has treasure.

You need to plan a treasure hunting trip with the following rules:

$1.$ You can only visit one island at a time.

$2.$ You can only travel between islands using the bridges.

$3.$ Once you leave an island, you can't go back to it$.$

$4.$ Some islands might have more than one bridge connecting them.

Your task is to start at a specific island and end at another specific island, visiting other islands along the way. The gr to collect as much treasure as possible in the shortest amount of time.

Note: There are no cycles in the graph $($the graph is a DAG$).$

$|$ Input Format

The first line of input contains three space$-$separated integers N$,$ M$,$ and K representing the number of islands, t number of bridges, and the number of starting$-$ending island pairs respectively.

The second line contains N space$-$separated integers $1,2,...,71,72,..,$ TN representing the amount of treasure island.

The next M lines each contain three space$-$separated integers U$,$ V$,$ and W representing a bridge between isli V with travel time W$.$

The next K lines each contain two space$-$separated integers S and E representing a starting island S and ar island E$.$

Output Format

Constraints

$25$N$510^9$

$15$M$<=10^9$

$15$ T$<10^$g

$1<=$U$,$V$,$S$,$ ESN

$15$W$<=10^9$

$1<=$K$$10^9$

Sample Testcase $1$

Testcase Input

$561$

$1020304050$

$125$

$1310$

$2410$

$345$

$451$

$252$

$15$

Sample Testcase $2$

Testcase Input

$441$

$10203040$

$1210$

$2310$

$3410$

$1450$

$14$

Testcase Output

$10030$

Explanation

One possible path is $1->2->3->4.$ The treasures collected are $10+20+30+40=100$ and th