P4754 True Vegetable

小 A 现在有 $N$ 道题，编号为 $1,2,\cdots,N$。每道题的起始毒瘤程度为 $0$ 或 $1$。在每回合，小 A 可以将编号连续的 $K$ 道题的毒瘤程度 +1。但小B因为本身比较菜，不是很愿意小 A 出毒瘤题，所以在 $w_i$ 回合开始时可以向第 $x_i$ 题传播 $v_i$ 点的菜气，使得第 $x_i$ 的毒瘤程度减少 $v_i$ 点（减后可以为负）。这里我们假定菜是有限的，在释放了 $v_i$ 点的菜气后，小 B 需要至少 $r_{v_i}$ 个回合不能释放菜气。现在小 A 知道了小 B 释放菜气的计划，他想知道他至少需要多少个回合可以使得每道题的毒瘤程度至少为 $1$。

第一行输入四个整数，$N,M,K,L$，分别为题目的数量，小B的操作数量，每次连续增加毒瘤程度题目的数量和释放菜气的最大值。 第二行输入 $N$ 个整数 $a_1,a_2,\cdots,a_N$，分别为$N$个题目的毒瘤程度。 第三行输入 $L$ 个整数 $r_1,r_2,\cdots,r_L$，分别为释放 $1$ 到 $L$ 点菜气的冷却回合数。 接下来有 $M$ 行，每行输入三个整数 $w_i,x_i,v_i$，表示小B在第 $w_i$ 回合开始时向第 $x_i$ 题释放了 $v_i$ 点的菜气。保证 $\{w_i\}$ 为递增序列。

请输出小 A 将每道题的毒瘤程度加到至少为 $1$ 最少需要的回合数。

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