Descripción

Los héroes de tu serie de acción favorita se preparan para el enfrentamiento final con los villanos. Fundamentalmente, hay dos rivales que lucharán entre sí: un héroe principal muy importante que quiere salvar el universo y un villano principal igual de importante que quiere destruirlo. Sin embargo, a través de innumerables escisiones recursivas, pueden tener compinches ligeramente menos importantes (un héroe y un villano que a su vez son rivales), que a su vez también pueden tener sus propios compinches (aún menos importantes), y así sucesivamente. Tenga en cuenta que hay el mismo número de héroes y de villanos, y cada pareja de rivales tiene como máximo una pareja de compañeros.

Inicialmente, cada personaje luchará contra su rival, y el ganador será determinado por quién tiene el Nivel de Poder más alto. Si un héroe y su correspondiente villano tienen el mismo Nivel de Poder, su batalla será determinada por la batalla de sus compinches, ya que el compinche ganador puede ayudar como una especie de desempate. (Si los rivales de igual Nivel de Poder no tienen compinches, el personaje héroe ganará con la ayuda de transeúntes al azar). Sin embargo, cuando una batalla es ganada por cualquiera de los dos bandos, los compinches no pueden hacer nada al respecto esto se debe a que la gente detrás del programa cree que algunos fans podrían enfadarse si un personaje fuera derrotado por un grupo de personajes menos importantes, por lo que perderían independientemente de los Niveles de Poder.

Una vez terminadas las batallas entre rivales (y los posibles desempates), el personaje más importante que quede derrotará al resto del bando contrario y determinará el destino del universo.

Afortunadamente, los héroes pueden asegurarse la victoria mediante un duro y riguroso entrenamiento. Por cada día que pasan entrenando, el Nivel de Poder de cada héroe aumenta en 1, mientras que los Niveles de Poder de los villanos permanecen constantes.

Pero todo esto ya lo sabías. La pregunta que te ronda por la cabeza es cuánto tiempo va a durar el entrenamiento.

Entrada

La entrada consiste en:

• una línea con un número entero ~n~ (~1 \le n \le 1000~), que da el número de parejas rivales.
• una línea con n enteros ~h1, ..., hn~ (~1 \le hi \le 1000~ para cada ~i~), cuyo \(i-ésimo\) valor da el Nivel de potencia del \(i-ésimo\) héroe más importante.
• una línea con n enteros ~v1, ..., vn~ (~1 \le vi \le 1000~ para cada ~i~), el \(i-ésimo\) valor que da el Nivel de Poder del \(i-ésimo\) villano más importante.

Salida

Da como salida un único número entero, el número mínimo de días que los héroes necesitan pasar entrenando para que su bando gane.

Subtarea

• 10 puntos. Para n ≤ 10
• 70 puntos. Sin restricciones

Ejemplos de Entrada y Saida

Ejemplo de Entrada #1

4
5 3 1 1
8 6 9 1

Ejemplo de Salida #1

4

Ejemplo de Entrada #2

1
2
1

Ejemplo de Salida #2

0

Ejemplo de Entrada #3

2
4 2
7 5

Ejemplo de Salida #3

3