Time

11:03:14
11 Feb 2012

ACM-ICPC Thailand Southern Region Programming Contest 2011
Left: 3 hours 57 minutes
End: 11.02.2012 15:00
Leader: Informatimukas

Five for week 22
Left: 10 hours 57 minutes
End: 11.02.2012 22:00
Leader: NuM

Condition

Problem Statistic

Discuss

New-year presents

prb26 Santa Claus and Snow-maiden must deliver n presents for children. You know packing time t₁ every present by Snow-maiden and delivering time 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.

Specifications

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₁,t₂ ≤ 1000.

Output

Print the smallest possible delivering time of all presents.

Problem information

Time Limit: 1 seconds
Memory Limit: 64 MB
Balls for the passed test: 9.09091
Complexity: 49% 69/135
Classes: Greedy algorithm

Example

Example input

5
4   4   30    6    2
5   1    4    30   3

Example output

← Paint3D

Problems

Cycle shifts →