Task Scheduling with Busy Days

One day, Lianzi came up with a brilliant idea and decided to refine it through a series of experiments. Specifically, she must complete \(n\) tasks sequentially. The \(i\)-th task requires \(a_i\) consecutive free days. In other words, if she starts the \(i\)-th task on day \(x\), she will finish it on day \(x+a_i-1\) (i.e. the task occupies days \(x, x+1, \ldots, x+a_i-1\)).

However, unfortunately, there are \(m\) days on which she is busy, given as a strictly increasing sequence \(b_1, b_2, \ldots, b_m\). That is, for every \(1 \le i < m\), \(b_i < b_{i+1}\). On these days, she cannot work on her tasks.

Lianzi wants to finish her tasks as soon as possible. Your task is to determine the earliest day on which she can finish all tasks if she schedules them optimally.

Note: All formulas are in \(\LaTeX\) format. This problem guarantees that there is always a valid schedule.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1\le n\le 10^5,\ 0\le m\le 10^5)\), the number of tasks and the number of busy days respectively.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) \((1\le a_i\le 10^9)\), where \(a_i\) represents the number of consecutive days needed to complete the \(i\)-th task.

If \(m > 0\), the third line contains \(m\) integers \(b_1, b_2, \ldots, b_m\) \((1\le b_1 < b_2 < \cdots < b_m\le 10^{18})\), representing the days on which Lianzi is busy. If \(m=0\), the third line is omitted.

outputFormat

Output a single integer, the earliest day on which Lianzi can finish all tasks.

sample

2 1
2 3
4

7