4725: 刷野 II(广东省重点中学信息学邀请赛普及组)
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
（广东省重点中学信息学邀请赛 (GDKOI 2024 day1普及组 第一试)
Zayin是一个与怪物战斗的巫师，这次他将面临n个站成一排的怪物，其中第i个怪物的生命值是ai。
Zayin知道许多被压制的咒语，在这场战斗中，他决定使用一个名为” 闪电连击” 的咒语来一口气击败所有的怪物。让我们看看这个咒语是如何工作的。
• 首先，Zayin选择一个怪物i(1≤i≤n) 以及咒语的初始力量x。
• 然后这个咒语会首先击中怪物i，随后对于除第一个目标怪物外，Zayin可以选择一个没有被该咒语击中过，并且与其中一个已经被击中的怪物相邻的怪物。
• 第一个被击中的目标怪物会受到 x 的伤害，第二个目标怪物会受到x−1的伤害，第三个受到x−2的伤害，以此类推。不难看出，每个怪物都会被击中恰好一次。
如果一个怪物受到的伤害不低于其生命值，则视为死亡。
Zayin想展示他作为一个高级巫师的能力，所以他希望在只使用一次咒语就能杀死所有怪物的前提下，使用最少的初始力量x。
现在你需要求出所需的最少的初始力量，并给出一个方案。如果有多个不同的方案，只需要给出任意一个就可以了。
Zayin是一个与怪物战斗的巫师，这次他将面临n个站成一排的怪物，其中第i个怪物的生命值是ai。
Zayin知道许多被压制的咒语，在这场战斗中，他决定使用一个名为” 闪电连击” 的咒语来一口气击败所有的怪物。让我们看看这个咒语是如何工作的。
• 首先，Zayin选择一个怪物i(1≤i≤n) 以及咒语的初始力量x。
• 然后这个咒语会首先击中怪物i，随后对于除第一个目标怪物外，Zayin可以选择一个没有被该咒语击中过，并且与其中一个已经被击中的怪物相邻的怪物。
• 第一个被击中的目标怪物会受到 x 的伤害，第二个目标怪物会受到x−1的伤害，第三个受到x−2的伤害，以此类推。不难看出，每个怪物都会被击中恰好一次。
如果一个怪物受到的伤害不低于其生命值，则视为死亡。
Zayin想展示他作为一个高级巫师的能力，所以他希望在只使用一次咒语就能杀死所有怪物的前提下，使用最少的初始力量x。
现在你需要求出所需的最少的初始力量，并给出一个方案。如果有多个不同的方案，只需要给出任意一个就可以了。
输入
第一行包含两个整数d, n，表示测试点编号和怪物数。
接下来一行n个整数，第i个整数ai表示第i个怪物的血量。
接下来一行n个整数，第i个整数ai表示第i个怪物的血量。
输出
第一行输出一个整数 x，表示最少的初始力量。
接下来第二行输出 n 个用空格分割的下标 monsteri (1 ≤ i ≤ n)，其中 monsteri 表示第 i 个击中的目标怪物。
接下来第二行输出 n 个用空格分割的下标 monsteri (1 ≤ i ≤ n)，其中 monsteri 表示第 i 个击中的目标怪物。
样例输入 复制
1 10
19 9 12 5 10 7 16 15 17 12样例输出 复制
25
1 2 3 4 5 6 7 8 9 10提示
数据范围:
对于所有测试数据，保证 1 ≤ n ≤ 5 × 106, 1 ≤ a ≤ 109。
对于所有测试数据，保证 1 ≤ n ≤ 5 × 106, 1 ≤ a ≤ 109。