U147003 草

$$\large{一切都是野蛮的}$$ $$\large{要反对这种野蛮}$$ $$\large{我们必须也学会野蛮}$$ $$\large{\ \ \ \ \ \ \ \ \ \ ——fcc}$$

$FCC$ 有 $N$ 片草地，第 $i$ 片草地上长有 $a_i$ 株野蛮草 $FCC$ 打算进行 $M$ 次采摘，每次可选择若干片长有至少一株野蛮草的草地（可以不选），并从每片选中的草地中采摘 $1$ 株野蛮草，第 $j$ 次采摘时在第 $i$ 片草地采摘将获得 $b_{ij}$ 野蛮值 为了保护草地的生态环境，每次采摘后，需要保证 $\forall \ i \in [1,N)$，$a_i \leq a_{i+1}$ 另外，$FCC$ 有 $K$ 个计划，每个计划形如 $(c_i,d_i,e_i)$，表示对于第 $c_i$ 片草地，第 $d_i$ 次采摘时，$e_i = 1$ 则必须采摘，否则不能采摘 为了学会野蛮，你需要求出 $FCC$ 能获得的最大野蛮值

第一行，三个整数 $N,M,K$ 第二行，$N$ 个整数，第 $i$ 个整数表示 $a_i$ 接下来 $N$ 行，每行 $M$ 个整数，第 $i+2$ 行第 $j$ 个整数表示 $b_{ij}$ 接下来 $K$ 行，第 $i+N+2$ 行三个整数 $c_i,d_i,e_i$

一个整数，表示答案

对于 $\ \ 8\%\ \ $ 的数据，$1 \leqslant N,M \leqslant 4$ 对于 $\ 16\%\ $ 的数据，$1 \leqslant N,M \leqslant 6$ 对于 $\ 24\%\ $ 的数据，$1 \leqslant N,M \leqslant 8$ 对于 $\ 32\%\ $ 的数据，$1 \leqslant N,M \leqslant 10$ 对于 $\ 48\%\ $ 的数据，$1 \leqslant N,M \leqslant 13$ 对于 $\ 60\%\ $ 的数据，$1 \leqslant N,M \leqslant 16$ 另有 $\ 20\%\ $ 的数据，$a_i = M$ 对于 $100\%$ 的数据，$1 \leqslant c_i \leqslant N \leqslant 19$，$1 \leqslant a_i,d_i \leqslant M \leqslant 19$，$0 \leqslant K \leqslant N×M$，$|b_{ij}| \leqslant 10^6$，$e_i \in \{ 0,1 \}$，保证 $a_i$ 单调不降，且至少存在一种合法的采摘方案 时空限制：$2000ms \ \ 1000MB$