下头论文

题目背景

莲子一直在苦恼关于论文的灵感。她为此花了太多时间,以至于没有时间理会她的伙伴梅莉。

题目描述

一天,莲子发现了一个绝妙的点子,并希望通过实验等过程将其完善。具体来说,**她需要依次完成 $n$ 项任务**,其中第 $i$ 项任务需要连续的 $a_i$ 天来完成。也就是说,假设她在第 $x$ 天开始该任务,那么她会在第 $x+a_i-1$ 天结束后完成该任务,她需要保证这些天里她都是空闲的。 不幸的是,她有 $m$ 天有各种事要去做,这些非空闲的日子会以一个单调递增序列 $b$ 的形式给出。即,对于任意的 $i(1\leq i<m)$,满足 $b_i<b_{i+1}$。 莲子希望完成任务的时间越短越好。例如:不妨假设,莲子要完成 $2$ 项任务,第一项耗时 $2$ 天,第二项耗时 $3$ 天,而第 $4$ 天莲子有事情要去做。则下图呈现了一种方案,使得莲子完成任务的时间尽可能短,为 $7$ 天: ![](https://cdn.luogu.com.cn/upload/image_hosting/bdiupoc1.png) 她想要知道,在最好情况下,她能在第几天结束后完成所有任务。

输入输出格式

输入格式


第一行两个整数 $n,m$。 第二行 $n$ 个正整数描述序列 $a$。 第三行 $m$ 个正整数描述序列 $b$。保证 $b$ 为单调递增序列。

输出格式


一行一个整数,表示莲子最快能在第几天结束后完成所有任务。

输入输出样例

输入样例 #1

2 1
2 3
4

输出样例 #1

7

输入样例 #2

3 3
1 1 1
1 5 6

输出样例 #2

4

说明

### 样例解释 #### 样例 \#1 即在题面中提及的情况。莲子在第 $1$ 天开始第一项任务,在第 $2$ 天结束后完成第一项任务。由于第 $4$ 天有事,她不能从第 $3$ 天开始第二项任务,于是她只好从第 $5$ 天开始该任务,在第 $7$ 天结束时完成全部任务。 注意到该样例符合 $\textbf{Subtask 2}$ 的特殊性质。 #### 样例 \#2 莲子在第 $2$ 至第 $4$ 天**依次**完成了所有任务。 ### 数据范围 **本题采用捆绑测试。每一个 Subtask 内的测试点均需通过才能获得该 Subtask 的分数。** 简记:$\sum a_i$ 为所有 $a_i$ 的和,即 $a_1+a_2+\dots+a_n$。其他试题中若无特殊说明也以此解释为准。 $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n,m\le } & \bm{\sum a_i\le} & \bm{b_i\le} & \textbf{\textsf{特殊性质}}&\textbf{Subtask \textsf{依赖}}\cr\hline 1 & 20 & 10 & 100 & 100 & - &-\cr\hline 2 & 20 & 10^5 & 10^8 & 10^8 & m=1&- \cr\hline 3 & 20 & 10^3 & 10^8 & 10^8 & \mathbf{-}&- \cr\hline 4 & 40 & 10^5 & 10^8 & 10^8& -&1,2,3 \cr\hline \end{array} $$ 对于所有数据满足:$1\le n,m\le 10^5$,$1\le a_i \le \sum a_i\le 10^8$, $1\le b_i\le 10^8$,$b$ 为单调递增序列。