具有连续时间段和变化收益的任务安排问题可描述如下。
- 给定 n 个任务的集合 A。
- 在上午完成的任务必须按照给定任务序列 x1,x2,⋯,xn 的顺序依次完成;在下午完成的任务必须按照给定任务序列 y1,y2,⋯,ym 的顺序依次完成。
- 完成任务所获得的收益在不同时间段有所不同。在上午完成的任务序列 xi 中的各项任务可获得相应收益 ai,而在下午完成的任务序列 yi 中的各项任务可获得相应收益 bi。
- 每个任务可以在上午完成,也可以在下午完成,但最多只能完成1次。
设 1≤la+1≤ra≤n,且 1≤lb+1≤rb≤n, 则 [la,ra] 和 [lb,rb] 分别是上午和下午完成的连续任务区间。当 {xla,xla+1,⋯,xra}∩{ylb,ylb+1,⋯,yrb}=∅ 时,称这两个连续任务区间不重叠,即这两个连续任务区间中的任务均不相同。此时,这两个连续任务区间所获得的总收益为:
ra∑i=laai+rb∑i=lbbi
最佳收益问题:对于给定的上午和下午完成的任务序列,在所有不重叠的连续任务区间对中,计算能获得的最大收益。上午和下午完成的连续任务区间均可为空,此时相应的任务区间中没有任务。
输入格式
第一行中有两个正整数 n 和 m,分别表示上午和下午完成的任务序列的长度。
第二行中有 n 个整数,表示上午完成的任务序列 x1,x2,⋯,xn。
第三行中有 n 个整数,表示上午完成的任务序列所相应的收益 a1,a2,⋯,an。
第四行中有 m 个整数,表示下午完成的任务序列 y1,y2,⋯,ym。
第五行中有 m 个整数,表示下午完成的任务序列所相应的收益 b1,b2,⋯,bm。
输出格式
输出一行一个整数,表示答案。
样例数据
样例输入
8 5
12 10 2 1 6 7 4 8
1 9 2 8 2 10 9 10
6 9 7 8 3
7 7 8 3 3
样例输出
58
子任务
测试数据中 40% 的数据满足 n,m≤10000
测试数据中 100% 的数据满足 1≤n,m≤500000,1≤ai,bi≤109,1≤xi,yi≤n+m。