33OJ
登录 注册

#P4754. True Vegetable

True Vegetable

题目描述

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

输入格式

第一行输入四个整数,N,M,K,LN,M,K,L,分别为题目的数量,小B的操作数量,每次连续增加毒瘤程度题目的数量和释放菜气的最大值。

第二行输入 NN 个整数 a1,a2,⋯ ,aNa_1,a_2,\cdots,a_N,分别为NN个题目的毒瘤程度。

第三行输入 LL 个整数 r1,r2,⋯ ,rLr_1,r_2,\cdots,r_L,分别为释放 11 到 LL 点菜气的冷却回合数。

接下来有 MM 行,每行输入三个整数 wi,xi,viw_i,x_i,v_i,表示小B在第 wiw_i 回合开始时向第 xix_i 题释放了 viv_i 点的菜气。保证 {wi}\{w_i\} 为递增序列。

输出格式

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

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×1051 \le N,M \le 5 \times 10^5

1≤K≤N1 \le K \le N

1≤L≤1001 \le L \le 100

a[i]∈{0,1}a[i] \in \{0,1\}

1=r1<r2<⋯<rL≤2×L1 = r_1 < r_2 < \cdots < r_L \le 2 \times L

1≤wi≤N+L1 \le w_i \le N+L

wi+rvi≤wi+1w_i+r_{v_i} \le w_{i+1}

1≤xi≤N1 \le x_i \le N

1≤vi≤L1 \le v_i \le L