{"problem":{"name":"pay","description":{"content":"今天是 L 公司发工资的一天。 $n$ 名员工排成一排准备领工资，编号为 $1\\sim n$，第 $i$ 名员工有一个期望快乐值 $a_i$。 老板非常扣，在这 $n$ 名员工中只选择了 $m$ 名员工 $b_1,b_2,\\cdots,b_m$ 发 $k$ 元工资。 员工们都非常具有同理心，不仅自己获得工资时会增加快乐值，当周围的员工获得工资时自己也会增加快乐值。 具体地，当与一名员工 A","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9519"},"statements":[{"statement_type":"Markdown","content":"今天是 L 公司发工资的一天。\n\n$n$ 名员工排成一排准备领工资，编号为 $1\\sim n$，第 $i$ 名员工有一个期望快乐值 $a_i$。\n\n老板非常扣，在这 $n$ 名员工中只选择了 $m$ 名员工 $b_1,b_2,\\cdots,b_m$ 发 $k$ 元工资。\n\n员工们都非常具有同理心，不仅自己获得工资时会增加快乐值，当周围的员工获得工资时自己也会增加快乐值。\n\n具体地，当与一名员工 A 距离为 $d$ 的员工获得了工资，A 的快乐值会增加 $\\max(0, k - d)$。特别地，如果 A 本身就获得了工资，A 的快乐值会增加 $k$。\n\n老板希望，你能找到最小的整数 $k$，使得所有员工的快乐值不低于他的期望。\n\n## Input\n\n第一行两个整数 $n,m$。\n\n第二行 $n$ 个整数 $a_1,a_2,\\cdots,a_n$。\n\n第三行 $m$ 个整数 $b_1,b_2,\\cdots,b_m$。\n\n## Output\n\n一个整数，表示你求出的最小的 $k$。\n\n[samples]\n\n## Note\n\n**【样例说明】**\n\n样例 $1$ 中，$k=2$ 时，每个人的快乐值分别为 $3,4,4,4,3$，满足要求。\n\n样例 $2$ 中，$k=5$ 时，每个人的快乐值分别为 $5,7,7,7,7$，满足要求。\n\n**【数据范围】**\n\n对于 $10\\%$ 的数据，满足 $n=1$。\n\n对于 $30\\%$ 的数据，满足 $n\\le 300$。\n\n对于 $60\\%$ 的数据，满足 $n\\le 5000$。\n\n对于另外 $10\\%$ 的数据，满足 $m=1$。\n\n对于 $100\\%$ 的数据，满足 $1\\le m\\le n\\le 10^6$，$0\\le a_i\\le 10^9$，$1\\le b_i\\le n$ 且 $b_i$ 互不相同。\n\n**本题输入量较大，请注意使用合理的输入方式。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9519","tags":["二分","洛谷原创","O2优化"],"sample_group":[["5 5\n3 3 3 3 3\n1 2 3 4 5","2"],["5 2\n5 2 6 3 1\n2 5","5"]],"created_at":"2026-03-03 11:09:25"}}