Maximizing Intimacy Through Synchronized Task Sequences

Two individuals, A and B, each have a sequence of tasks to complete. Their tasks must be performed following a dependency order: task 1 must be done first, and for every other task e there is a prerequisite p_e such that task e can only be executed after p_e (the dependency relationships form a rooted out‐tree, so every task’s dependency chain is the unique path from it to task 1). In this problem, we assume that the input for each person is given as a chain (i.e. the unique path from the root to a chosen leaf) and each task has a positive execution time.

A and B decide to "synchronize" on some of these tasks. Specifically, each chooses a subsequence from his/her full task sequence (which must include the first and the last task) such that the chosen tasks occur in order. When A executes his chosen tasks a₁, a₂, …, a_k and B executes b₁, b₂, …, b_k concurrently (that is, a_i and b_i start at the same time for every 1 ≤ i ≤ k), they gain an intimacy score of C_{ai, bi} at the moment of synchronization.

However, between these synchronized tasks the two work alone on the remaining tasks in their full sequences. Suppose the full sequence for A is of length n with durations d₁, d₂, …, d_n (and similarly B’s full sequence of length m with durations); let S_A be the set of indices that A synchronizes on, and S_B for B. (By convention, indices 1 and n (or 1 and m) are forced to be in S_A (or S_B)). During the period in which A is executing tasks that are not synchronized he “loses” intimacy at a rate defined as follows: if he works continuously for T minutes without synchronization, then his intimacy decreases by 1 + 3 + 5 + … + (2T-1) = T². B’s penalty is defined analogously. (Note that the actual execution times matter – the tasks performed during the gaps directly contribute to a penalty of the square of the total gap time.)

The overall intimacy achieved is computed as:

Your task is: given the two full task sequences (each representing the unique dependency chain a person must follow), their execution times, and a set of scores C for some synchronized task pairs, determine the maximum intimacy achievable by appropriately choosing the synchronized subsequences for A and B. Note that the two synchronized subsequences must have the same length (and must include the first and the last tasks of each full sequence) and the gap penalty is computed using the sum of durations of the tasks that are not synchronized.

Important: When A and B synchronize on tasks, even though the execution times of the paired tasks may differ, the decision is made solely on the positions in their full sequences. Also, if a pair (i, j) is not provided in the input, assume that C_i,j is 0.

inputFormat

The first line contains three integers n m q representing the length of A's task sequence, the length of B's task sequence, and the number of pairs for which the synchronization reward is provided.

The second line contains n positive integers: the execution times of A's tasks in order.

The third line contains m positive integers: the execution times of B's tasks in order.

Each of the next q lines contains three integers i j s indicating that if A synchronizes on his i-th task and B on her j-th task concurrently, they gain a reward of s. (For pairs not given, assume a reward of 0.)

Note: It is guaranteed that tasks 1 and task n (for A) and tasks 1 and m (for B) must be included in the synchronized subsequence.

outputFormat

Output a single integer — the maximum intimacy that can be achieved.

sample

4 5 2
2 1 4 7
4 8 3 6 4
1 1 100
4 5 200

186