Problem Background

Lian Zi has been struggling with finding inspiration for her thesis. She has spent so much time on it that she has no time to attend to her companion, Mayuri.

Problem Description

One day, Lian Zi came up with a brilliant idea and hoped to refine it through experiments and other processes. Specifically, she needs to complete \( n \) tasks in sequence, where the \( i \)-th task requires \( a_i \) consecutive days to complete. That is, if she starts the task on day \( x \), she will finish it on day \( x + a_i - 1 \). She needs to ensure that she is free during these days.

Unfortunately, she has \( m \) days when she has other things to do, and these non-idle days are given in the form of a monotonically increasing sequence \( b \). That is, for any \( i \) ( \( 1 \leq i < m \) ), \( b_i < b_{i+1} \).

Lian Zi hopes to complete the tasks as soon as possible. For example, suppose Lian Zi needs to complete 2 tasks, the first one taking 2 days and the second one taking 3 days, and she has something to do on day 4. The following diagram shows a plan that allows Lian Zi to complete the tasks as soon as possible, which is 7 days:

She wants to know, in the best case, on which day she can finish all the tasks.

Input Format

The first line contains two integers \( n \) and \( m \).

The second line contains \( n \) positive integers describing the sequence \( a \).

The third line contains \( m \) positive integers describing the sequence \( b \). It is guaranteed that \( b \) is a monotonically increasing sequence.

Output Format

A single integer on one line, indicating the earliest day on which Lian Zi can finish all the tasks.

Sample Input and Output

Sample Input #1

2 1
2 3
4

Sample Output #1

7

Sample Input #2

3 3
1 1 1
1 5 6

Sample Output #2

4

Notes

Sample Explanation

Sample #1

This is the scenario mentioned in the problem statement. Lian Zi starts the first task on day 1 and finishes it on day 2. Since she has something to do on day 4, she cannot start the second task on day 3, so she starts it on day 5 and finishes all tasks on day 7.

Note that this example meets the special properties of Subtask 2.

Sample #2

Lian Zi completes all tasks sequentially from day 2 to day 4.

Data Range

This problem is group testing. You must pass all test cases within a Subtask to earn points for that Subtask.

Let \( \sum a_i \) be the sum of all \( a_i \), i.e., \( a_1 + a_2 + \dots + a_n \). This interpretation applies to other problems unless specified otherwise.

$$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{Points} & \bm{n,m\le } & \bm{\sum a_i\le} & \bm{b_i\le} & \textbf{Special Properties} & \textbf{Subtask Dependencies} \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 & - & - \cr\hline 4 & 40 & 10^5 & 10^8 & 10^8 & - & 1,2,3 \cr\hline \end{array} $$

For all data, \( 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 \), and \( b \) is a monotonically increasing sequence.

见题面 Input 部分

见题面 Output 部分