Burgers

문제

Kai the lobster is starting a burger chain selling burgers. He has $nn$ ingredients to work with, which are labelled from $11$ to $nn$. For each ingredient $ii$, he has $x[i]x[i]$ portions of ingredient $ii$.

He has two recipes for burgers. For each ingredient $ii$, the first recipe requires $a[i]a[i]$ portions of ingredient $ii$ and the second recipe requires $b[i]b[i]$ portions of ingredients $ii$.

Can you help Kai compute the maximum total number of burgers he can make?

입력

The first line of input consists of one integer $nn$, the number of different ingredients.

The second line consists of $nn$ spaced integers $x[1],x[2],\dots ,x[n-1],x[n]x[1],\; x[2],\; \backslash dots\; ,\; x[n\; -\; 1],\; x[n]$, the total number of portions Kai has of each ingredient.

The third line consists of $nn$ spaced integers $a[1],a[2],\dots ,a[n-1],a[n]a[1],\; a[2],\; \backslash dots\; ,\; a[n\; -\; 1],\; a[n]$, the number of portions of each ingredient for the first recipe.

The fourth line consists of $nn$ spaced integers $b[1],b[2],\dots ,b[n-1],b[n]b[1],\; b[2],\; \backslash dots\; ,\; b[n\; -\; 1],\; b[n]$, the number of portions of each ingredient for the second recipe.

출력

The output should contain a single integer on a single line, the largest number of burgers Kai can make.

3
14 10 100
3 1 1
2 3 1

5

2
83 72
1 3
1 3

24