Little I is playing the final boss battle of a turn-based RPG. In this battle, the protagonist and their $(n-1)$ teammates (a total of $n$ people) act in a fixed order, aiming to deal the highest possible total damage to the boss.

The game features $x$ types of attack modes, where the $i$-th ($1 \le i \le x$) attack mode deals a base damage of $d_i$ to the boss.

During the battle, status effects can be applied to the boss. There are $y$ types of status effects, and the boss cannot be under the influence of two status effects at the same time. When the boss is under a specific status effect, using a specific attack mode triggers a critical hit, dealing additional damage. The critical hit rules are given by $m$ triples $(p_j, q_j, c_j)$, meaning that using the $q_j$-th ($1 \le q_j \le x$) attack mode while the boss is under the $p_j$-th ($1 \le p_j \le y$) status effect deals an additional $c_j$ damage.

At the start of the battle, the boss is not under any status effect. Following the action order, the $i$-th ($1 \le i \le n$) person can perform one of the following three actions:

• Use a spell to put the boss under the $a_i$-th status effect. If the boss was already under a different status effect, the previous status effect is removed.
• Use the $b_i$-th attack mode to attack the boss. Regardless of whether a critical hit is triggered, the boss's status effect is removed after dealing damage.
• Slack off, i.e., do nothing, in which case the boss's status effect is preserved.

As a fan of the story, Little I does not want to calculate the optimal strategy themselves, so they have handed the problem to you. You need to find the maximum total damage that can be dealt within $n$ actions.

Input

The input is read from standard input.

The first line contains four integers $n, m, x, y$ ($1 \le n, m, x, y \le 2 \times 10^5$), representing the number of actions, the number of critical hit rules, the number of attack modes, and the number of status effect types, respectively.

The second line contains $x$ integers $d_1, d_2, \dots, d_x$ ($1 \le d_i \le 10^9$), describing the base damage of each attack mode.

The next $n$ lines each contain two integers $a_i, b_i$ ($1 \le a_i \le y, 1 \le b_i \le x$), describing the $i$-th person's available actions.

The next $m$ lines each contain three integers $p_j, q_j, c_j$ ($1 \le p_j \le y, 1 \le q_j \le x, 1 \le c_j \le 10^9$), describing the $j$-th critical hit rule. It is guaranteed that all $(p_j, q_j)$ pairs are distinct.

Output

Output to standard output.

Output a single integer representing the maximum total damage that can be dealt to the boss over $n$ actions.

Examples

Input 1

4 1 2 2
10 1
2 1
1 1
1 2
2 2
2 2 1000000000

Output 1

1000000002

Note 1

In the example, there are two attack modes and two status effects. The first attack mode deals $10$ base damage, and the second attack mode deals $1$ base damage. There is only one critical hit rule: using the second attack mode while the boss is under the second status effect deals an additional $10^9$ damage.

The optimal strategy is as follows:

• The first person uses a spell to put the boss under the second status effect;
• The second person slacks off, and the boss remains under the second status effect;
• The third person uses the second attack mode, dealing $1$ base damage and $10^9$ critical damage, and the boss's status effect is cleared;
• The fourth person uses the second attack mode, dealing $1$ base damage.

The total damage is $1 + 10^9 + 1 = 10^9 + 2$.