说明

你将和 $m$ 个朋友一起去开车兜风。为了享受驾驶过程，你有一个包含 $n$ 首歌曲的播放列表，歌曲编号为 $1$ 到 $n$。

在时刻 $0$，你选择其中一首歌曲并从其开头开始播放。之后，播放列表会无限循环。对于每首歌曲 $k$（$1 \leq k \leq n$），一旦歌曲 $k$ 开始播放，它会持续 $l_k$ 个单位时间，然后歌曲 $k+1$（如果 $k=n$ 则为歌曲 $1$）会立即接续播放。

第 $i$ 个朋友喜欢歌曲 $f_i$，他会在时刻 $t_i - 0.5$ 加入你。此后，每当歌曲 $f_i$ 开始播放时，他都会感到兴奋。请注意，即使在他加入时歌曲 $f_i$ 已经在播放中，他也不会感到兴奋，因为每个人都希望从开头欣赏他们最喜欢的歌曲。

如果你能最优地选择播放列表的第一首歌曲，那么所有 $m$ 个朋友都至少兴奋一次的最早时间是什么？注意，你不能从歌曲的中间开始播放。

输入格式

输入包含一个测试用例，格式如下。

$$\begin{aligned} & n \ m \\ & l_1 \ l_2 \ \cdots \ l_n \\ & t_1 \ t_2 \ \cdots \ t_m \\ & f_1 \ f_2 \ \cdots \ f_m \end{aligned}$$

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 200\,000$，$1 \leq m \leq 200\,000$）。$n$ 是播放列表中歌曲的数量，$m$ 是加入你兜风的朋友数量。

第二行包含 $n$ 个正整数 $l_1, l_2, \ldots, l_n$。每个 $l_i$ 表示歌曲 $i$ 的长度。它们的总和不超过 $10^{15}$。

第三行包含 $m$ 个整数 $t_1, t_2, \ldots, t_m$（$1 \leq t_i \leq 10^{15}$）。每个 $t_i$ 表示第 $i$ 个朋友在时刻 $t_i - 0.5$ 加入你。

第四行包含 $m$ 个整数 $f_1, f_2, \ldots, f_m$（$1 \leq f_i \leq n$）。每个 $f_i$ 是第 $i$ 个朋友最喜欢的歌曲编号。

输出格式

输出一个整数，表示所有 $m$ 个朋友都至少兴奋一次的最早时间。

3 4
3 1 4
10 7 3 7
1 3 2 1

12

5 7
20 25 9 14 20
25 9 14 75 38 100 38
3 1 1 5 2 4 4

136

提示

在第一个样例中，如果你从歌曲 $3$ 开始播放列表，四位朋友首次感到兴奋的时刻分别是 $12$、$8$、$7$ 和 $12$。

翻译由 DeepSeek V3.2 完成