下头论文
题目背景
莲子一直在苦恼关于论文的灵感。她为此花了太多时间,以至于没有时间理会她的伙伴梅莉。
题目描述
一天,莲子发现了一个绝妙的点子,并希望通过实验等过程将其完善。具体来说,**她需要依次完成 $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$ 为单调递增序列。