P9519 pay

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.

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$.

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

**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