Competitions

# жадібний алгоритм

# New-year presents

Santa Claus and Snow-maiden must deliver **n** presents for children. You know packing time `t`

every present by Snow-maiden and delivering time _{1}`t`

by Santa Claus. Find the least time for what they can do all orders. Santa Claus can put only one present in his sack._{2}

#### Input

In the first line we have the number of presents **n** (**1** ≤ **n** ≤ **300**). In the next two lines **n** numbers, separated with a space, are given: second line is packing time of every present by Snow-maiden, the third line is delivering time by Santa Claus. It is known that **0** < `t`

, _{1}`t`

≤ _{2}**1000**.

#### Output

Print the smallest possible delivering time of all presents.

Input example #1

5 4 4 30 6 2 5 1 4 30 3

Output example #1

47