← 返回题目列表

Codeforces · 586/B

B. 劳伦蒂和商店

中文机器翻译题面 查看原题

小男孩劳伦蒂已经玩他最喜欢的游戏 Nota 有一段时间了,现在非常饿了。这个男孩想做香肠和奶酪三明治,但首先,他需要买一根香肠和一些奶酪。

劳伦蒂居住的小镇并不大。里面的房子排成两排,每排有n栋房子。劳伦蒂住在第二排的最后一间房子里。镇上唯一的商店位于第一排的第一间房子里。

第一排和第二排与城市主干道隔开。一排相邻的房屋被街道隔开。

街道或大道的每个人行横道都有一些交通灯。为了过马路,您需要按下交通灯上的按钮,等待一段时间绿灯然后过马路。不同的红绿灯可以有不同的等待时间。

从第 i 行第 j 户到同排第 (j + 1) 户的人行横道上的红绿灯等待时间等于 aij (1 ≤ i ≤ 2, 1 ≤ j ≤ n - 1)。对于从一排第 j 个房屋到另一排第 j 个房屋的十字路口上的交通灯,等待时间等于 bj (1 ≤ j ≤ n)。这座城市没有任何其他过境点。

男孩想去商店,购买产品然后回去。城市的主干道足够宽,所以男孩想在去商店的路上和回家的路上正好穿过一次。如果再走同样的路,男孩会感到无聊,所以他希望回家的路和去商店的路至少有一个路口不同。

图为第一个示例。

帮助劳伦蒂确定他需要在十字路口等待的最短总时间。

输入

输入的第一行包含整数 n (2 ≤ n ≤ 50) — 每行中的房屋数量。

接下来的两行包含 n - 1 个空格分隔的整数 — 值 aij (1 ≤ aij ≤ 100)。

最后一行包含 n 个空格分隔的整数 bj (1 ≤ bj ≤ 100)。

输出

打印一个整数 - 劳伦蒂在十字路口需要等待的最少总时间,因为他在去商店和回家的路上只穿过大街一次。

示例

输入 #1

4
1 2 3
3 2 1
3 2 2 3

输出 #1

12

输入 #2

3
1 2
3 3
2 1 3

输出 #2

11

输入 #3

2
1
1
1 1

输出 #3

4

注意

第一个示例如上图所示。

在第二个示例中,Laurenty 的路径如下所示:

- 劳伦蒂穿过大道,等待时间为3;
- 劳伦蒂使用第一排第二个路口,等待时间为2;
- Laurenty使用第一排第一个路口,等待时间为1;
- Laurenty使用第一排第一个路口,等待时间为1;
- 劳伦蒂穿过大道,等待时间为1;
- 劳伦蒂使用第二排的第二个十字路口,等待时间为3。

在最后一个示例中,Laurenty 访问了所有交叉点,因此答案是 4。