#2039. pay

pay

题目描述

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

nn 名员工排成一排准备领工资,编号为 1∼n1\sim n,第 ii 名员工有一个期望快乐值 aia_i。

老板非常扣,在这 nn 名员工中只选择了 mm 名员工 b1,b2,⋯ ,bmb_1,b_2,\cdots,b_m 发 kk 元工资。

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

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

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

输入格式

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

第二行 nn 个整数 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n。

第三行 mm 个整数 b1,b2,⋯ ,bmb_1,b_2,\cdots,b_m。

输出格式

一个整数,表示你求出的最小的 kk。

样例

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

题目来源:洛谷 P9519