"Perket" es una comida ampliamente conocida y deliciosa. Para que el perket sea lo que es, los azucareros del centro deben elegir cuidadosamente los ingredientes para obtener el máximo sabor posible manteniendo la tradición de la comida.

Tienes ~N~ ingredientes a tu disposición. Para cada uno, conocemos su acidez S y amargor B. Al usar múltiples ingredientes, la acidez total es el producto de las cantidades de acidez de todos los ingredientes, mientras que el amargor total es la suma de las cantidades de amargor de todos los ingredientes.

Como todos saben, se supone que el perket no debe ser ni ácido ni amargo; queremos elegir los ingredientes de manera que la diferencia absoluta entre la acidez y el amargor sea la más pequeña.

Además, es necesario usar al menos un ingrediente; no puedes servir agua como plato principal.

Entrada

La primera línea contiene el número entero ~N~ (~1 \leq N \leq 10~), que representa el número de ingredientes a nuestra disposición.

Cada una de las siguientes ~N~ líneas contienen dos enteros separados por un espacio, la acidez y amargura de cada ingrediente.

Los datos de entrada serán tal que, si hacemos una comida con todos los ingredientes, tanto la acidez como la amargura serán menores que ~10^9~.

Salida

Un solo número, la diferencia más pequeña posible entre acidez y amargura.

Ejemplo #1 de Entrada

1
3 10

Ejemplo #1 de Salida

7

Ejemplo #2 de Entrada

2
3 8
5 8

Ejemplo #2 de Salida

1

Ejemplo #3 de Entrada

4
1 7
2 6
3 8
4 9

Ejemplo #3 de Salida

1

Nota

En el tercer ejemplo, elegimos los últimos tres ingredientes. La acidez total es entonces ~2 \cdot 3 \cdot 4 = 24~ y la amargura es ~6 + 8 + 9 = 23~. La diferencia es ~1~.