Description

One day, Renko discovered an excellent idea and wanted to refine it through experiments. Specifically, she needs to complete $n$ tasks sequentially, where the $i$-th task requires $a_i$ consecutive days to complete. This means if she starts the task on day $x$, she will finish it after day $x + a_i - 1$. She must ensure she is free on all those days.

Unfortunately, she has $m$ days with prior commitments, given as a monotonically increasing sequence $b$. That is, for any $i$ ($1 \leq i < m$), $b_i < b_{i+1}$.

Renko wants to minimize the total time taken to complete all tasks. For example: suppose she needs to complete 2 tasks, where the first takes 2 days and the second 3 days, and she has a commitment on day 4. The figure below shows a scenario where Renko finishes all tasks in the shortest possible time of 7 days:

• Green: be in progress
• Red: be busy
• Blank: spare time

She wants to determine the earliest day she can complete all tasks under optimal conditions.

Input Format

• The first line contains two integers $n$ and $m$.
• The second line contains $n$ positive integers describing sequence $a$.
• The third line contains $m$ positive integers describing sequence $b$, which is guaranteed to be monotonically increasing.

Output Format

Output one integer: the earliest day Renko can finish all tasks.

2 1
2 3
4

7

3 3
1 1 1
1 5 6

4

Hint

Sample #1

This matches the scenario described in the problem. Renko starts the first task on day 1 and finishes it after day 2. Due to her commitment on day 4, she cannot start the second task on day 3. Instead, she starts it on day 5 and completes it after day 7.

This sample satisfies the special property of Subtask 2.

Sample #2

Renko completes all tasks consecutively from day 2 to day 4.

Constraints

Bundled testing is used. All test cases in a Subtask must be passed to receive its points.

Note: $\sum a_i$ denotes the sum of all $a_i$ (i.e., $a_1 + a_2 + \dots + a_n$). The same applies to other problems unless stated otherwise.

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

For all data: $1 \leq n, m \leq 10^5$, $1 \leq a_i \leq \sum a_i \leq 10^8$, $1 \leq b_i \leq 10^8$, and $b$ is monotonically increasing.

---

Translated by DeepSeek R1