题目描述

塔子哥喜欢魔术，现在有 $n$ 个魔术道具，这些道具由不同的物品组成。其中第$i$个道具包含$a_i$个特殊元素，包含$b_i$个普通元素。

塔子哥想最大化他的魔术表演，但他的魔术需要特殊元素所占的比例不能低于一半。

塔子哥需要选择一些道具，将它们的特殊元素混合在一起，问塔子哥最多可以得到多少特殊元素用作魔术表演？

输入描述

一行一个整数$n$，表示道具的数量。

接下来一行，$n$个整数$a_1,a_2,...，a_n$，表示第i个道具包含$a_i$个特殊元素。

接下来一行，$n$个整数$b_1,b_2,....,b_n$，表示第i个道具包含$b_i$个普通元素。

$1 \leq n \leq 10^5$

$0 \leq a_i, b_i \leq 100$

$a_i + b_i = 100$

输出描述

一行一个整数，表示塔子哥最多可以得到的特殊元素数量。

样例

输入

3
50 60 30
50 40 70

输出

110

说明

选择第一和第二个道具，可以得到110个特殊元素。