说明

又是新的一天，要打训练赛的阿冬又睡过头了。由于他昨天晚上玩《光明记忆：无限》玩得太晚，他做梦的内容也是《光明记忆：无限》。

在梦中，阿冬遇到了一个解谜：

敌方设置了一排横向共$N$个机关以阻止阿冬的前进，固执的阿冬只有消除所有的机关才会心满意足地醒来。每消除一个机关都会消耗阿冬一定的精力，且该机关左右的机关会施加电磁干扰以进一步消耗阿冬的精力。每消除一个机关，它两边的机关(如果有)会并在一起，仍然保持一排(即左右两边机关向这个机关的位置收缩，等同于一个含有$N-1$个机关的不包含这个被消除机关的同类问题)。

消除一个机关$i$所需要的精力具体为这个机关的复杂度$a_i$加上它相邻机关的电磁干扰强度$b_{i-1}$和$b_{i+1}$(特殊地，如果$i$为$1$则对应的$b_{i-1}$为0，如果$i$为$N$，则对应的$b_{i+1}$为0)。

你需要帮助阿冬求出消除所有机关所需要消耗的最小精力。

输入格式

第一行一个正整数$N$ $(1 \le N \le 400)$，表示机关个数。

第二行$N$个非负整数$a_i$ $(0 \le a_i \le 10^5)$，表示每个机关的复杂度。

第三行$N$个非负整数$b_i$ $(0 \le b_i \le 10^5)$，表示每个机关的电磁干扰强度。

输出格式

输出一个整数，表示阿冬所需要消耗的最小精力。

样例

3
3 5 7
8 2 3

19

提示

对于样例1，一种可行的最佳消除策略是：

先消除第1个机关，耗费精力为机关的复杂度3和电磁干扰强度2；

再消除原来的第3个机关，耗费精力为机关的复杂度7和电磁干扰强度2；

最后消除原来的第2个机关，耗费精力为机关的复杂度5和电磁干扰强度0。