2587. [HZOI 2016]你猜是不是DP

【题目描述】

小P得到了一个长为$n$的序列。小P想给这个序列染上黑色和白色，于是他就随便制定了一个染色方案。正当小P要染色时，小A批判道：“Naive！这个染色方案太难看了，你应该仔细分析染色的效果之后再动手。”

小A和小P一起分析序列的性质之后，得出两个结论：

1.序列中的第i个位置染成黑色会产生$b_i$的美感，染成白色会产生$w_i$的美感(必须染上黑白两种颜色之一，不能不染色)。

2.有些区间比较特殊，如果区间内的所有数都染成黑色会额外得到$c_i$的美感；另一些区间则恰好相反，如果区间内的所有数都染成白色会额外得到$c_i$的美感。

小A和小P想找到一种染色方案使得美感的总和最大，但是他俩实在太菜了，只会打20分暴力。因此，他们找到了精通DP的你，请求你帮帮他们。

小A和小P只关心美感总和的最大值，你可以认为他们有足够的智商根据这个数值去构造方案。

【输入格式】

第一行两个整数$n,m$，分别表示序列的长度和特殊区间的数量。

第二行n个整数$b_i$，表示每个位置染成黑色会得到的美感。

第三行n个整数$w_i$，表示每个位置染成白色会得到的美感。

以下$m$行，每行四个整数$t_i,l_i,r_i,c_i$，如果$t_i=1$则表示如果区间$[l_i,r_i]$都被染成黑色会额外得到$c_i$的美感，如果$t_i=2$则表示如果区间$[l_i,r_i]$都被染成白色会额外得到$c_i$的美感。

【输出格式】

单独一行输出一个整数，表示美感总和的最大值。

【样例输入】

5 3
1 2 2 4 3
0 -2 7 1 5
2 1 2 7
1 2 3 5
1 5 5 1

【样例输出】

21

【样例解释】

把第4个位置染成黑色，其余位置染成白色，得到美感总和为0+(-2)+7+4+5+7=21。

【数据范围与约定】

对于20%的数据，$n,m \le 20$。

对于50%的数据，$n,m \le 1000$。

对于100%的数据，$1 \le n,m \le 10000$，所有$c_i$均$>0$，保证$1 \le l_i \le r_i \le n$，保证所有$b_i,w_i,c_i$的绝对值均$\le 10000$。

由于出题人很懒，所有数据均为随机数据。

【来源】

似乎是经典问题