题目描述

小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$最少需要的回合数。

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

提示

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