Description

Little A now has $N$ problems, numbered $1,2,\cdots,N$. The initial “toxicity level” of each problem is $0$ or $1$. In each round, Little A can increase the toxicity level of $K$ problems with consecutive indices by $1$.

However, Little B is not very strong and does not really want Little A to create toxic problems. At the start of round $w_i$, Little B can spread $v_i$ points of “noob gas” to problem $x_i$, which decreases the toxicity level of problem $x_i$ by $v_i$ points (it may become negative after decreasing). We assume the amount of “noob gas” is limited: after releasing $v_i$ points of noob gas, Little B must wait at least $r_{v_i}$ rounds before being able to release noob gas again.

Now Little A knows Little B’s plan for releasing noob gas, and he wants to know the minimum number of rounds needed to make the toxicity level of every problem at least $1$.

Input Format

The first line contains four integers $N,M,K,L$, representing the number of problems, the number of Little B’s operations, the number of consecutive problems increased each time, and the maximum value of noob gas that can be released.

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

The third line contains $L$ integers $r_1,r_2,\cdots,r_L$, representing the cooldown rounds for releasing $1$ to $L$ points of noob gas.

The next $M$ lines each contain three integers $w_i,x_i,v_i$, meaning that at the start of round $w_i$, Little B releases $v_i$ points of noob gas to problem $x_i$. It is guaranteed that $\{w_i\}$ is a strictly increasing sequence.

Output Format

Output the minimum number of rounds Little A needs to make the toxicity level of every problem at least $1$.

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

3

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

2

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

1

Hint

Constraints

$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$.

Translated by ChatGPT 5