注意

書籍の版によっては、書籍内の入力例が正しくない場合があります。正誤表を参照してください。

問題文

あるダンジョンには N 個の部屋があり、1 から N までの番号が付けられています。このダンジョンは一方通行であり、通路を介して 1 つ先または 2 つ先の部屋に移動することができます。各通路における移動時間は以下の通りです。

• 部屋 i - 1 から部屋 i に向かう通路を通るのに A_i 分 (2 ≤ i ≤ N) かかる。
• 部屋 i - 2 から部屋 i に向かう通路を通るのに B_i 分 (3 ≤ i ≤ N) かかる。

太郎君が部屋 1 から部屋 N に移動するのに、最短何分かかりますか。答えを求めるプログラムを作成してください。

制約

• 3 ≤ N ≤ 100\,000
• 1 ≤ A_i ≤ 100 (2 ≤ i ≤ N)
• 1 ≤ B_i ≤ 100 (3 ≤ i ≤ N)
• 入力される値はすべて整数である。

入力例 1

5
2 4 1 3
5 3 7

出力例 1

8

入力例 2

10
1 19 75 37 17 16 33 18 22
41 28 89 74 98 43 42 31

出力例 2

157