Description

There are $n$ small islands on this ocean, connected by $m$ stone bridges. Some islands have rewards buried by wzt; they are very tempting. Their temptation is described by an integer $k_i$. Some islands have lsq’s mercenaries, each with a price described by an integer $b_i$. lsq must pay money for his mercenaries to help him search for rewards.

A mercenary’s base price does not change. During the search, for each mercenary, as he crosses bridges, his total cost will increase by the sum of the lengths of all bridges he passes. Unfortunately, there are not only bridges blocking the way; each island has many beasts. Although the mercenaries are brave, driving away beasts is unpleasant. Therefore, for each mercenary, his total cost will also increase by the sum of the numbers of beasts on all islands he passes through (including the starting island).

lsq knows everything about the situation and must decide which reward each of his mercenaries should go for. The goal is to find all rewards and achieve maximum profit. Each mercenary can be hired at most once.

Profit is defined as: the sum of the temptation values of all rewards minus all the money lsq spends.

lsq’s decision is extremely difficult, so he asks you for help.

Input Format

The first line contains four integers: $n$ (total number of islands), $m$ (total number of bridges), $a$ (total number of lsq’s mercenaries), $b$ (total number of rewards).

The next line contains $n$ integers, the number of beasts on each island.

The next $m$ lines, each with three integers $u, v, w$, indicate that there is a bridge of length $w$ connecting island $u$ and island $v$.

The next $a$ lines, each with two integers $q_i, p_i$, indicate that the $i$-th mercenary has base price $q_i$ and initial position at island $p_i$.

The next $b$ lines, each with two integers $k_i, q_i$, indicate that the $i$-th reward has temptation $k_i$ and is located at island $q_i$.

Output Format

If all rewards can be found, output "Yes", and on the next line output the maximum profit.

If not all rewards can be found, output "No", and on the next line output the maximum number of rewards that can be found.

4 6 3 2
16 37 22 24 
1 4 25
1 1 23
4 1 20
3 1 47
1 1 18
3 3 24
213 1
174 2
62 4
1493 3
2632 4

Yes
3741

4 2 3 2
16 37 22 24
1 4 25
1 3 12
213 1
174 3
62 4
1493 2
2632 4

No
1

Hint

Constraints:

• For 30% of the testdata, $n \le 200$, $m \le 200$, $b \le a \le 30$.
• For 50% of the testdata, $n \le 500$, $m \le 800$, $b \le a \le 100$.
• For 100% of the testdata, $n \le 1000$, $m \le 15000$, $b \le a \le 300$. The rest of the testdata guarantees no 32-bit signed int overflow (Pascal: longint).

By Ebola.

Translated by ChatGPT 5