P17821 回層浮 / kaisou

这一曲，我们用余生共同谱写。

在悠扬的琴声中，SK 的思绪飘向了记忆的远方。 时间的道路上存在 $n$ 个结点，每一时间结点 $i$ 均有其独特的色彩 $x_i$。这一次追忆之旅中，SK 决定选择经历一些关键的结点 $p_{1\sim k+1}$。故事的起点与结局不容错过，需要保证 $p_1=1$ 且 $p_{k+1}=n$。时间静静流淌向前，不容违逆，需要保证 $p_i< p_{i+1}$。 SK 将她的情绪归为 $m$ 种，每种情绪都有对应的频率 $t_i$。关键的记忆结点将故事划为若干小节，对于每一段小节，SK 都会将她的每一种情绪与其进行比对。具体地，对于第 $i$ 段小节，她将会捕捉到 $\sum_{j=1}^m|x_{p_{i+1}}-x_{p_{i}}-t_j|$ 份思绪。 遗憾的是，记忆在时间的冲刷下逐渐崩塌，回想记忆结点 $x_i$ 需要耗费 SK $c_i$ 份思绪。 为了尽可能地体验思绪，她该如何进行这一次的追忆？ **形式化地**，你需要选出 $1\sim n$ 的一个非空子序列 $p_{1\sim k+1}$，满足 $p_1=1$，$p_{k+1}=n$ 且 $p_i< p_{i+1}$，最大化 $$\sum_{i=1}^k\sum_{j=1}^m|x_{p_{i+1}}-x_{p_{i}}-t_j|-\sum_{i=1}^{k+1}c_{p_i}.$$

第一行两个正整数 $n,m$。 第二行输入 $n$ 个非负整数 $x_{1\sim n}$。 第三行输入 $n$ 个非负整数 $c_{1\sim n}$。 第四行输入 $m$ 个整数 $t_{1\sim m}$。

输出一行一个整数，表示答案。

### 数据规模与约定 对于所有数据，保证 $1\le n,m\le 3\times 10^5$，$0\le x_i\le 6\times10^7$，$0\le |t_j|\le 10^7$，$0\le c_i\le 10^9$。 ::cute-table | 子任务编号 | $n\le$ | $m\le$ | 特殊性质 | 分值 | |:-:|:-:|:-:|:-:|:-:| | $1$ | $20$ | $20$ | 无 | $5$ | | $2$ | $1000$ | $500$ | ^ | $10$ | | $3$ | ^ | $3\times 10^5$ | ^ | $10$ | | $4$ | $3\times10^4$ | ^ | ^ | $20$ | | $5$ | $3\times 10^5$ | $1$ | ^ | $15$ | | $6$ | ^ | $3\times10^5$ | 有 | $20$ | | $7$ | ^ | ^ | 无 | $20$ | 特殊性质：保证 $x_i\le x_{i+1}$。