New-year presents
Medium
Execution time limit is 1 second
Runtime memory usage limit is 128 megabytes
Santa Claus and Snow-maiden must deliver n presents for children. You know packing time t[1]
every present by Snow-maiden and delivering time t[2]
by Santa Claus. Find the least time for what they can do all orders. Santa Claus can put only one present in his sack.
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.
Examples
Input #1
Answer #1
Submissions 6K
Acceptance rate 36%