C : so easy

Progress Bar

时间限制:1 Sec 内存限制:0 MiB
提交:2 答案正确:1

提交


题目描述

题目描述:


    这题是这次最简单的题目。


    如今某企鹅有一款非常火的即时对战手机游戏。当然没玩过也不影响做题。在这款游戏中,如果能够击败对方英雄或者野怪,你就会获得一些金币,金


币呢可以购买更强大的装备。于是,如果你每次能够击败对方英雄或者野怪,就能获得一些金币,也就能购买更强大的装备,购买更强大的装备也就更容易


击败对方英雄,如果擅长这样滚雪球的话,胜利就会变得非常简单。


    你需要完成这样一个程序:


    1:假如你现在控制某位英雄,初始状态对方有n位英雄(n<=250000),每位英雄有其对应的被击败获得的金币数money[i](n<=money<=150000000)。为


了简化题目,每次只能选择一位英雄去击败获得金币,没有团战或者打不过的情况。


    2:每位敌方英雄被击败后,他的击败后价值就会变化,击败后,他的价值会变为money[i]-i,为了简化题意,不用再更新原来的money[i],只需在money[]


的末尾添加新的价值即可。即对于击败x个英雄后,有n+x个money值。


    3:这是一位比较特殊的英雄,他的可攻击范围是很大的。这里给出一个数组dis,有n个数,代表某次可选择的攻击范围,对于选择dis[i],可选择对从


dis[i]到现有的money末尾的任意一个英雄进行攻击,击败后获得对应的金币。每个dis只能用一次。


    4:击败n次会有2n个money值,你要求的是如何进行击败使得新得到的n+1到n+n的金币和最大,以便于自己滚雪球。输出这后n个money的和。结果对1e9+7取模。



样例说明:


ans = 0


1:从dis中选择1(dis[2]),可选择击败英雄2-4,选择击败英雄2,money: 8 11 8 5 9(money[2]-2)  ans=0+9


2: 从dis中选择2(dis[4]),可选择击败英雄2-5,选择击败英雄2,money: 8 11 8 5 9 9(money[2]-2) ans=9+9=18


3: 从dis中选择3(dis[1]),可选择击败英雄3-6,选择击败英雄3,money: 8 11 8 5 9 9 5(money[3]-3) ans=18+5=23


4: 从dis中选择4(dis[3]),可选择击败英雄4-7,选择击败英雄5,money: 8 11 8 5 9 9 5 4(money[5]-5) ans=23+4=27

输入

第一行一个n,代表初始的敌方英雄人数(n<=250000)


第二行n个数,代表初始的n位英雄的金币价值(n<=money<=1500000)


第三行n个数,代表可选择的n次攻击范围(1<=dis<=n)

输出

最大后n项金币和

样例输入

复制
4
8 11 8 5
3 1 4 2

样例输出

复制
27

提示


			

来源