Ultimate Boss Battle Optimization

You are given a turn‐based RPG scenario where the protagonist and his \(n-1\) teammates (in total \(n\) persons) will perform actions sequentially. The goal is to maximize the total damage on the boss over the \(n\) actions.

The game has \(x\) attack modes. For the \(i\)-th attack mode \((1 \le i \le x)\), its base damage is \(d_i\).

There are \(y\) abnormal statuses. The boss can only have at most one abnormal status at a time. When the boss is affected by a certain abnormal status, using a specific attack mode may trigger a critical hit that deals extra damage. The bonus rules are given by \(m\) triples \((p_j, q_j, c_j)\). This means that if the boss is under abnormal status \(p_j\) \((1 \le p_j \le y)\) and an attack of mode \(q_j\) \((1 \le q_j \le x)\) is used, an additional damage of \(c_j\) is dealt.

At the start of the battle, the boss has no abnormal status. Actions occur in turn from \(i=1\) to \(n\). For the \(i\)-th action, you are given two integers \(a_i\) and \(b_i\). The acting person can choose one of the following actions:

1. Cast Spell: Apply abnormal status \(a_i\) to the boss. If the boss previously has another abnormal status, it is removed. (No damage is dealt.)
2. Attack: Attack the boss using attack mode \(b_i\). This attack always deals the base damage \(d_{b_i}\). Moreover, if at this moment the boss is under some abnormal status \(s\) (i.e. \(s \neq 0\)) and there is a bonus rule such that \(s = p_j\) and \(b_i = q_j\), then an extra \(c_j\) damage is added. After the attack, the boss's abnormal status is removed.
3. Do Nothing: The player does nothing. The boss's abnormal status, if any, remains unchanged. (No damage is dealt.)

Your task is to choose one action for each of the \(n\) turns such that the total damage dealt is maximized. Print the maximum total damage possible.

inputFormat

The input is given as follows:

 n x y m
 d1 d2 ... dx
 p1 q1 c1
 p2 q2 c2
 ...
 pm qm cm
 a1 b1
 a2 b2
 ...
 an bn

Where:

• \(n\): the number of actions (turns).
• \(x\): the number of attack modes.
• \(y\): the number of abnormal statuses.
• \(m\): the number of bonus rules.
• \(d_i\): base damage for the \(i\)-th attack mode.
• Each bonus rule is given as three integers \(p_j\), \(q_j\), and \(c_j\); meaning that if the boss is under abnormal status \(p_j\) and an attack of mode \(q_j\) is used, an extra damage of \(c_j\) is added.
• Each of the next \(n\) lines contains two integers \(a_i\) and \(b_i\) representing the abnormal status to be applied (if casting a spell) and the attack mode used (if attacking) in the \(i\)-th turn respectively.

outputFormat

Output a single integer: the maximum total damage that can be dealt in \(n\) actions.

sample

3 2 2 2
10 20
1 1 5
2 2 15
1 1
2 2
1 2

50