题目描述

小 D 现在在一个黑暗的房间里，身边有两个鞋盒，其中一个只有左脚的鞋另一个只有右脚的鞋。在两个盒子里的鞋，分别各有 $n$ 种不同的颜色，你现在知道了两个盒子 中每种颜色鞋子的数量，现在你希望从两个盒子中分别取出一些鞋子从而保证自己一定 能凑出一双颜色相同的鞋子，小 D 现在想知道需要从两个鞋盒中分别拿出多少只鞋子就一定能够保证凑出一对相同颜色的鞋子，从两个鞋盒中拿出鞋子的数量不要求相等，在所有可能情况中，找出鞋子总数量最少的方案。

输入格式

第一行一个整数 $n$ 表示鞋子颜色种数

第二行 $n$ 个整数表示左脚鞋盒中 $i$ 颜色的鞋有多少只

第三行 $n$ 个整数表示右脚鞋盒中 $i$ 颜色的鞋有多少只

数据范围

对于 30% 的数据，$1 \le n \le 5$，且每种颜色的鞋子数量均不为 $0$。

对于 50% 的数据，$1 \le n \le 10$

对于 100% 的数据, $1 \le n \le 16$, $0 \le a_i \le 10^8$

输出格式

一个整数，代表所有可能方案中鞋子总数量最少的方案中鞋子的总数量。

样例

4
0 6 1 6
1 5 0 6

10

样例解释

选 8 个左鞋, 2 个右鞋，一定能保证有一对颜色一样的鞋