Problem Description

Little A has \( N \) problems, numbered from \( 1 \) to \( N \). Each problem starts with a toxicity level of either \( 0 \) or \( 1 \). In each round, Little A can increase the toxicity level of \( K \) consecutive problems by \( 1 \). However, Little B, being less skilled, does not want Little A to create toxic problems. Therefore, at the beginning of the \( w_i \)-th round, Little B can spread \( v_i \) units of inexperience to the \( x_i \)-th problem, reducing its toxicity level by \( v_i \) points (which can result in negative values). We assume that inexperience is limited, and after releasing \( v_i \) units of inexperience, Little B needs at least \( r_{v_i} \) rounds before he can release inexperience again. Now, Little A knows Little B's plan for releasing inexperience, and he wants to find out the minimum number of rounds needed to ensure that the toxicity level of each problem is at least \( 1 \).

Input Format

The first line contains four integers: \( N \), \( M \), \( K \), and \( L \), representing the number of problems, the number of operations by Little B, the number of consecutive problems whose toxicity level is increased each time, and the maximum value of inexperience released, respectively.

The second line contains \( N \) integers \( a_1, a_2, \cdots, a_N \), representing the initial toxicity levels of the \( N \) problems.

The third line contains \( L \) integers \( r_1, r_2, \cdots, r_L \), representing the cooldown rounds required for releasing \( 1 \) to \( L \) units of inexperience.

The next \( M \) lines each contain three integers \( w_i, x_i, v_i \), indicating that Little B releases \( v_i \) units of inexperience to the \( x_i \)-th problem at the beginning of the \( w_i \)-th round. The sequence \( \{w_i\} \) is guaranteed to be increasing.

Output Format

Output the minimum number of rounds required for Little A to increase the toxicity level of each problem to at least \( 1 \).

Sample Input and Output

Sample Input #1

6 1 3 2
0 0 0 0 0 0
1 2
2 1 1

Sample Output #1

3

Sample Input #2

6 1 3 2
1 0 0 0 0 0
1 2
2 1 1

Sample Output #2

2

Sample Input #3

6 1 6 2
0 0 0 0 0 0
1 2
2 1 1

Sample Output #3

1

Notes

• \( 1 \le N, M \le 5 \times 10^5 \)
• \( 1 \le K \le N \)
• \( 1 \le L \le 100 \)
• \( a[i] \in \{0, 1\} \)
• \( 1 = r_1 < r_2 < \cdots < r_L \le 2 \times L \)
• \( 1 \le w_i \le N + L \)
• \( w_i + r_{v_i} \le w_{i+1} \)
• \( 1 \le x_i \le N \)
• \( 1 \le v_i \le L \)

见题面 Input 部分

见题面 Output 部分