You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

今天是 L 公司发工资的一天。

$n$ 名员工排成一排准备领工资，编号为 $1\sim n$，第 $i$ 名员工有一个期望快乐值 $a_i$。

老板非常扣，在这 $n$ 名员工中只选择了 $m$ 名员工 $b_1,b_2,\cdots,b_m$ 发 $k$ 元工资。

员工们都非常具有同理心，不仅自己获得工资时会增加快乐值，当周围的员工获得工资时自己也会增加快乐值。

具体地，当与一名员工 A 距离为 $d$ 的员工获得了工资，A 的快乐值会增加 $\max(0, k - d)$。特别地，如果 A 本身就获得了工资，A 的快乐值会增加 $k$。

老板希望，你能找到最小的整数 $k$，使得所有员工的快乐值不低于他的期望。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

第三行 $m$ 个整数 $b_1,b_2,\cdots,b_m$。

输出格式

一个整数，表示你求出的最小的 $k$。

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

2

5 2
5 2 6 3 1
2 5

5

提示

【样例说明】

样例 $1$ 中，$k=2$ 时，每个人的快乐值分别为 $3,4,4,4,3$，满足要求。

样例 $2$ 中，$k=5$ 时，每个人的快乐值分别为 $5,7,7,7,7$，满足要求。

【数据范围】

对于 $10\%$ 的数据，满足 $n=1$。

对于 $30\%$ 的数据，满足 $n\le 300$。

对于 $60\%$ 的数据，满足 $n\le 5000$。

对于另外 $10\%$ 的数据，满足 $m=1$。

对于 $100\%$ 的数据，满足 $1\le m\le n\le 10^6$，$0\le a_i\le 10^9$，$1\le b_i\le n$ 且 $b_i$ 互不相同。

本题输入量较大，请注意使用合理的输入方式。