序列

题目描述

Y 同学正在维护一个长度为 $N$ 的整数序列 $A = \{a_1, a_2, \dots, a_N\}$。初始时，序列中的每个元素 $a_i \in \{0, 1\}$。

为了保持系统的稳定性，序列中的每个元素都需要保持在至少 $1$ 的水平。然而，系统会受到外部干扰，导致某些位置的数值下降。同时，Y 同学每回合可以进行维护操作来提升数值。

具体的过程如下： 系统的时间从第 $1$ 回合开始流动。

1. 外部干扰：已知有 $M$ 次预定的干扰事件。第 $i$ 次干扰发生在第 $w_i$ 回合开始时，它会使位置 $x_i$ 处的数值减少 $v_i$（即 $a_{x_i} \leftarrow a_{x_i} - v_i$）。数值减少后可能变为负数。
2. 维护操作：在每一个回合（包括第 1 回合），Y 同学都可以执行一次操作：选择一个长度为 $K$ 的连续子区间 $[p, p+K-1]$（其中 $1 \le p \le N-K+1$），将该区间内所有元素的值增加 $1$。

Y 同学想知道，最少经过多少个回合（记为 $T$），他可以通过合理安排这 $T$ 个回合内的维护操作（共计 $T$ 次区间加 $1$），使得在第 $T$ 回合结束时（即所有的第 $1 \dots T$ 回合的干扰生效，且 $T$ 次维护操作完成后），序列中所有的元素都满足 $a_i \ge 1$。

注意：虽然干扰是按回合发生的，但在计算第 $T$ 回合的状态时，我们可以认为前 $T$ 个回合的所有干扰和维护操作是累积结算的。

输入格式

第一行输入四个整数 $N, M, K, L$。分别表示序列长度、干扰事件数量、维护操作的区间长度、以及单次干扰的最大值。

第二行输入 $N$ 个整数 $a_1, a_2, \dots, a_N$，表示序列的初始状态（$0$ 或 $1$）。

第三行输入 $L$ 个整数 $r_1, r_2, \dots, r_L$，其中 $r_v$ 表示产生一次数值减少 $v$ 的干扰后，下一次干扰至少需要间隔的回合数（此信息主要用于解释数据的生成约束）。

接下来 $M$ 行，每行输入三个整数 $w_i, x_i, v_i$，表示在第 $w_i$ 回合开始时，位置 $x_i$ 的数值减少 $v_i$。

输出格式

输出一个整数，表示使所有元素最终至少为 $1$ 所需的最少回合数。

样例

样例输入 #1

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

样例输出 #1

3

样例输入 #2

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

样例输出 #2

2

样例输入 #3

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

样例输出 #3

1

数据范围与约定

对于 $100\%$ 的数据，保证：

• $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 < \dots < r_L \le 2 \times L$
• $1 \le w_1 < w_2 < \dots < w_M \le N + L$
• 输入的干扰事件满足时间约束：$w_i + r_{v_i} \le w_{i+1}$
• $1 \le x_i \le N$
• $1 \le v_i \le L$