Problem Description

In a distant ocean, a game of世纪大战级别 is unfolding.

Special thanks to lsq for participating in the problem verification.

Problem Description

In this ocean, there are n islands connected by m stone bridges. Some islands have rewards planted by wzt, which are very tempting and described by an integer ki. Some islands have mercenaries hired by lsq, each with a price described by an integer bi. lsq must pay money for his mercenaries to search for the rewards.

The price of the mercenaries does not change. During the search, each mercenary will cross bridges, and their price will increase by the length of all bridges they cross.

Unfortunately, not only are there bridges, but each island also has many ferocious beasts. Although the mercenaries are brave, the process of driving away the beasts is very unpleasant. Therefore, for each mercenary, the price will increase by the total number of beasts on all islands (including the starting island) they pass through.

lsq knows everything about this place and needs to make a decision on which reward each mercenary should search for. lsq's goal is to find all rewards and achieve the maximum profit. Each mercenary can only be hired once.

Profit is defined as: the total attractiveness of all rewards minus all the money lsq spends.

lsq's decision is extremely difficult, so he has to ask you, who has AKed NOI, for help.

Input Format

The first line contains four numbers: 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 numbers, representing the number of beasts on each island.

The next m lines contain three numbers each: u, v, w, indicating that there is a bridge of length w connecting island u and island v.

The next a lines contain two numbers each: qi, pi, indicating that the i-th mercenary's price is qi and their initial position is island pi.

The next b lines contain two numbers each: ki, qi, indicating that the i-th reward's attractiveness is ki and its position is island qi.

Output Format

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

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

Sample Input and Output

Input Sample #1

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

Output Sample #1

Yes
3741

Input Sample #2

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

Output Sample #2

No
1

Notes/Hints

For 30% of the data, n <= 200, m <= 200, b <= a <= 30.

For 50% of the data, n <= 500, m <= 800, b <= a <= 100.

For 100% of the data, n <= 1000, m <= 15000, b <= a <= 300, and other data guarantees that it will not overflow int (longint in Pascal).

By Ebola

见题面 Input 部分

见题面 Output 部分