# 短板翻盘

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：512 MB

## 背景故事

创意集市的一排展台各有两项评分，允许出现负分。评委决定选一段连续展台，把其中最低的第一项评分，乘以第二项评分的总和，作为这一段的最终得分。

评委觉得这样能让大家重视短板。摊主们听完规则，默默翻开了数学课本里“负负得正”的那一页。

你要选出得分最高的一段，至少包含一个展台。

(本故事由GPT-6 Astra重写)

## 形式化问题描述

给定两个长度均为 $n$ 的整数序列 $a_1,\ldots,a_n$ 和 $b_1,\ldots,b_n$ ，分别表示各展台的第一项和第二项评分。求

$$\max_{1\le l\le r\le n}\left(\min_{l\le i\le r}a_i\right)\left(\sum_{i=l}^{r}b_i\right)$$

也就是在所有非空连续区间中，最大化“区间内第一项评分的最小值 × 区间内第二项评分的总和”。

区间必须非空。两序列都可以包含正数、零和负数，答案也可能为负数。

## 输入格式

第一行一个整数 $n$ .

第二行 $n$ 个整数 $a_1,\ldots,a_n$ .

第三行 $n$ 个整数 $b_1,\ldots,b_n$ .

## 输出格式

输出一个整数，表示最大值。

## 样例 1

### 输入

```text
3
1 -1 1
1 2 3
```

### 输出

```text
3
```

### 解释

选择区间 $[3,3]$ ，得到 $1\times3=3$ .

## 样例 2

### 输入

```text
3
-2 -1 -3
-2 -4 1
```

### 输出

```text
15
```

### 解释

选择整个区间，得到 $(-3)\times(-5)=15$ .

## 样例 3

### 输入

```text
1
2
-3
```

### 输出

```text
-6
```

### 解释

唯一的非空区间得分为 $-6$ ，不能改选空区间得到 $0$ .

## 数据范围与保证

- $1\le n\le1\,000\,000$ .
- $-1\,000\,000\le a_i,b_i\le1\,000\,000$ .

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 20% | $n\le300$ |
| 20% | $n\le2\,000$ |
| 20% | $n\le10\,000$ |
| 40% | 无额外条件 |