龙虾 Kai 正在开一家汉堡连锁店。他有 $n$ 种配料，编号从 $1$ 到 $n$。对于每种配料 $i$，他拥有 $x[i]$ 份。

他有两种汉堡配方。对于每种配料 $i$，第一种配方需要 $a[i]$ 份配料 $i$，第二种配方需要 $b[i]$ 份配料 $i$。

你能帮 Kai 计算他最多能制作的汉堡总数吗？

输入格式

你的程序必须从标准输入读取数据。

第一行包含一个整数 $n$，表示不同配料的数量。

第二行包含 $n$ 个空格分隔的整数 $x[1], x[2], \dots, x[n-1], x[n]$，表示 Kai 拥有的每种配料的总份数。

第三行包含 $n$ 个空格分隔的整数 $a[1], a[2], \dots, a[n-1], a[n]$，表示第一种配方所需的每种配料的份数。

第四行包含 $n$ 个空格分隔的整数 $b[1], b[2], \dots, b[n-1], b[n]$，表示第二种配方所需的每种配料的份数。

输出格式

你的程序必须输出到标准输出。

输出应包含一个整数，表示 Kai 最多能制作的汉堡数量。

子任务

对于所有测试用例，输入满足以下限制：

• $1 \le n \le 100\,000$
• $1 \le x[i], a[i], b[i] \le 10^9$

你的程序将在满足以下限制的输入实例上进行测试：

样例

样例输入 1

3
14 10 100
3 1 1
2 3 1

样例输出 1

5

说明 1

他可以使用第一种配方制作 3 个汉堡，使用第二种配方制作 2 个汉堡，总共 5 个汉堡。

样例输入 2

2
83 72
1 3
1 3

样例输出 2

24

说明 2

他可以制作 24 个任意类型的汉堡，因为两种配方是相同的。