题目描述
小 A 现在有 N 道题,编号为 1,2,⋯,N。每道题的起始毒瘤程度为 0 或 1。在每回合,小 A 可以将编号连续的 K 道题的毒瘤程度 +1。但小B因为本身比较菜,不是很愿意小 A 出毒瘤题,所以在 wi 回合开始时可以向第 xi 题传播 vi 点的菜气,使得第 xi 的毒瘤程度减少 vi 点(减后可以为负)。这里我们假定菜是有限的,在释放了 vi 点的菜气后,小 B 需要至少 rvi 个回合不能释放菜气。现在小 A 知道了小 B 释放菜气的计划,他想知道他至少需要多少个回合可以使得每道题的毒瘤程度至少为 1。
输入格式
第一行输入四个整数,N,M,K,L,分别为题目的数量,小B的操作数量,每次连续增加毒瘤程度题目的数量和释放菜气的最大值。
第二行输入 N 个整数 a1,a2,⋯,aN,分别为N个题目的毒瘤程度。
第三行输入 L 个整数 r1,r2,⋯,rL,分别为释放 1 到 L 点菜气的冷却回合数。
接下来有 M 行,每行输入三个整数 wi,xi,vi,表示小B在第 wi 回合开始时向第 xi 题释放了 vi 点的菜气。保证 {wi} 为递增序列。
输出格式
请输出小 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≤N,M≤5×105
1≤K≤N
1≤L≤100
a[i]∈{0,1}
1=r1<r2<⋯<rL≤2×L
1≤wi≤N+L
wi+rvi≤wi+1
1≤xi≤N
1≤vi≤L