Problem Description

Today is payday at Company L.

There are $n$ employees standing in a line to receive their salaries, numbered from $1$ to $n$. The $i$-th employee has an expected happiness value $a_i$.

The boss is very stingy, and among these $n$ employees, he only chooses $m$ employees $b_1,b_2,\cdots,b_m$ to pay a salary of $k$ yuan.

The employees are very empathetic: not only does their happiness increase when they themselves get paid, but it also increases when nearby employees get paid.

Specifically, when an employee at distance $d$ from employee A gets paid, A's happiness increases by $\max(0, k - d)$. In particular, if A himself gets paid, A's happiness increases by $k$.

The boss hopes that you can find the smallest integer $k$ such that every employee's happiness is not less than their expectation.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$.

The third line contains $m$ integers $b_1,b_2,\cdots,b_m$.

Output Format

One integer, representing the smallest $k$ you found.

5 5
3 3 3 3 3
1 2 3 4 5

2

5 2
5 2 6 3 1
2 5

5

Hint

Sample Explanation

In sample $1$, when $k=2$, everyone's happiness values are $3,4,4,4,3$, which meets the requirements.

In sample $2$, when $k=5$, everyone's happiness values are $5,7,7,7,7$, which meets the requirements.

Constraints

For $10\%$ of the testdata, $n=1$.

For $30\%$ of the testdata, $n\le 300$.

For $60\%$ of the testdata, $n\le 5000$.

For another $10\%$ of the testdata, $m=1$.

For $100\%$ of the testdata, $1\le m\le n\le 10^6$, $0\le a_i\le 10^9$, $1\le b_i\le n$, and all $b_i$ are distinct.

The input size of this problem is large, so please use a proper input method.

Translated by ChatGPT 5