logo AlgoBeat OnlineJudge
登录 注册

#103461. [BZOJ 3461] Jry的时间表

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:无测试数据
上传者: 匿名

题目描述

吉丽 (JRY) 的电脑里有一份时间表,表上有 个时间段,每个时间段吉丽都要和一个妹子约会。每个妹子都有一个属性 ,表示吉丽和第 个妹子约会至少需要带的 。吉丽特意把 标在了第 行,以作备忘。

你听说了吉丽的这张时间表,决定篡改一下数据,让吉丽花更多的 。当然,你对这 个妹子也有不同的好感度,所以你准备把第 行的数改为

有一天你趁机接触到了吉丽的时间表,可是时间紧迫,你最多只能输入两个数据,其他只能通过复制得到了。

定义“一次操作”为:修改第i行的数据,将 改为 ,选中这个数向上或向下拖动到第 行,这样就使得第 至第 行的数都被覆盖成了

注意:为了提高效率,你不会修改或覆盖同一行两次以上(包括两次)。

你的时间只够你完成两次操作,你在这么短的时间内仍不忘让吉丽花的 越多越好。请你回答:在最多操作两次的情况下,吉丽最多要花多少

输入格式

第一行一个整数

第二行 个数,表示

第三行 个数,表示bi。

输出格式

一个数,表示吉丽最多要花的

样例

样例输入 #1

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

样例输出 #1

31

样例说明

第一次操作:修改第 行,向上拖动到第 行。

第二次操作:修改第 行,向下拖动到第 行。

修改后的数列: 和为 ,可以验证这是最大值。

数据范围与提示

数据已加强,By evil 佂菡 XXY杯省选模拟题