长假即将来临！Andi 和 Budi 两兄弟从叔叔那里收到了一套漫画书作为礼物。由于假期没有其他计划，他们决定待在家里看漫画。

共有 $N$ 本漫画书，编号从 $1$ 到 $N$。Andi 读完第 $i$ 本书需要 $A_i$ 小时，而 Budi 需要 $B_i$ 小时。Andi 和 Budi 都会按照书号从小到大的顺序，一次读一本书。

由于只有一套漫画书，他们决定遵循以下规则：

• 作为哥哥，Budi 在读完一本书后可以选择跳过下一本书。更准确地说，在 Budi 读完第 $i$ 本书后，他可以直接开始读第 $(i+2)$ 本书，而完全跳过第 $(i+1)$ 本书。
• 如果 Budi 没有跳过第 $i$ 本书，那么作为弟弟的 Andi 在 Budi 读完第 $i$ 本书之前，不得开始阅读第 $i$ 本书。如果 Budi 跳过了第 $i$ 本书，则对该书没有特殊限制。

Andi 和 Budi 必须阅读第 $1$ 本书和第 $N$ 本书以享受故事情节。此外，Andi 希望阅读所有书籍，而 Budi 可以根据上述规则跳过某些书籍。当且仅当 Andi 和 Budi 都读完了第 $N$ 本书时，才视为他们完成了所有漫画书的阅读。

你的任务是确定 Andi 和 Budi 完成阅读所需的最短时间（以小时为单位）。

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 1000$)，表示漫画书的数量。 第二行包含 $N$ 个整数 $A_i$ ($1 \le A_i \le 1000$)，表示 Andi 阅读每本书所需的时间。 第三行包含 $N$ 个整数 $B_i$ ($1 \le B_i \le 10$)，表示 Budi 阅读每本书所需的时间。

输出格式

输出一行一个整数，表示 Andi 和 Budi 完成阅读所需的最短时间。

样例

输入格式 1

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

输出格式 1

13

说明

如果 Budi 只阅读第 $1, 3, 4, 6$ 本书，可以达到 $13$ 小时的最短时间。

输入格式 2

2
2 1
1 1

输出格式 2

4

说明

Andi 和 Budi 都必须阅读第 $1$ 本书和第 $N=2$ 本书。他们完成所有书籍阅读的最短时间为 $4$ 小时。