12月将举办首届西电ACM新生赛,敬请期待~~~~

问题 1100. -- 无聊的xry111

1100: 无聊的xry111

时间限制: 2 Sec  内存限制: 128 MB
提交: 108  解决: 26
[提交][状态][讨论版]

题目描述

xry111有一天很无聊,于是他开始玩一个无聊的游戏 。他在纸上画一根有n个点的线段(点的标号从左往右依次增加,第1个点和第n个点为线段的两个端点)。
xry111需要在其中选择以其中两个点为端点的子线段
选择的得分为子线段的总长度与子线段中包含的所有点中点权值的最小值的乘积
现在xry111已经画好了线段,xry111想知道他能得到的最大得分为多少

输入

多组输入(最多30组),请处理到EOF
第一行一个整数n,表示线段中点的个数 2<=n<=10^5
第二行 n个整数ai 代表第i个点的权值 0<=a[i]<=10^9
接下来n-1行,每行一个整数x,表示第i个点到第i+1个点之间的长度,保证每条线段长度不超过10^5。
保证答案不超过有符号64位整数的表示范围。

输出

输出一个整数代表得分的最大值

样例输入

2
1 2
1
4
1 2 2 2
1 1 1

样例输出

1
4

提示

第一组样例只能取1,2两个点之间的子线段,总长度为1。其中包含1,2两个点,权值最小为1。得分为1

第一组样例可以取2,4两个点之间的子线段,总长度为2。其中包含2,3,4三个点,权值最小为2。得分为4


来源

[提交][状态][讨论版]