刷野

题号：NC210807
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

吉吉国王最近迷上了一款网络游戏，在这款游戏种，在地图上刷野怪是效率最高的升级方法。但是刷野怪的时候非常容易掉血，因此吉吉国王希望受到的总伤害值最低。
现在吉吉国王遇到了 $n$ 只野怪，每只野怪都有一个攻击力 $a_i$ 和一个增益值 $b_i$ 。如果吉吉国王攻击第 $i$ 个野怪，那么吉吉国王会受到一个基础伤害 $a_i$ ，如果左侧存在野怪，那么会额外受到一个增益伤害 $b_l$ ，同理如果右侧存在野怪，那么会再多受到一个增益伤害 $b_r$ 。当杀死第 $i$ 个野怪，这个野怪两边的野怪会变成相邻。因此击杀一个野怪后，会受到可能的伤害值为 $a_i + b_l + b_r$ ，如果左侧或者右侧不存在野怪就不会多受到增益伤害，并且会使左右两边的野怪相邻。
假如现在三只野怪的伤害分别是 $(2, 3, 4)$ ，增益值是 $(0, 1, 2)$ 。那么如果吉吉国王选择击杀中间的野怪，会受到 $5$ 点伤害，并且剩下的野怪的伤害变成 $(2, 4)$ ，增益值为 $(0,2)$ 。现在你需要告诉吉吉国王他受到的最小伤害是多少。

输入描述:

第一行一个整数表示野怪的个数。
第二行个数，第个数表示。
第三行个数，第个数表示。

输出描述:

输出一行一个整数表示最小的伤害。

示例1

输入

复制

3
2 3 4
0 1 2

输出

复制

题目描述

输入描述:

输出描述:

输入

输出

备注: