El tomate es uno de los recursos más valiosos del universo. Cuando PSN0 llegó a su casa, se les asignó la tarea de establecer la producción de tomate.

Inicialmente, PSN0 solo tenía una cosechadora disponible para la cosecha de tomate, por lo que era urgente fabricar nuevas cosechadoras para comenzar:

1. La componente I para la cosechadora se puede producir en ~t_1~ días a partir de chatarra, de la cual hay una cantidad ilimitada en el antiguo taller de su casa.
2. La componente II se produce a partir de una primera componente ya producida en ~t_2~ días.
3. Finalmente, la cosechadora se fabrica en ~t_3~ días a partir de una componente I y una componente II.

La primera parte de la producción es bastante rápida: se garantiza que ~1 \le t_1 \le 2~. Cada parte de fabricación es responsabilidad de una fábrica separada, y cada fábrica solo puede trabajar en una etapa correspondiente (es decir, una fábrica que produce la componente II no puede producir la componente I).

Los tres procesos pueden realizarse en paralelo, es decir, mientras, una componente I está en producción, otra producida anteriormente puede transformarse en la componente II. Sin embargo, cada una de las tres fábricas requeridas está disponible en un solo número y no puede trabajar en más de una componente o cosechadora en un momento dado.

Para establecer rápidamente la producción de tomate, es necesario producir ~n~ cosechadoras. ¿cuál es el tiempo mínimo en qué se puede hacer esto?

Subtareas

• Subtarea 1 (7 puntos): ~n=1~.
• Subtarea 2 (11 puntos): ~t_2 = t_1 = 1~, ~t_3 \ge 2~.
• Subtarea 3 (15 puntos): ~t_1 = 1~.
• Subtarea 4 (10 puntos): ~t_1 = t_2 \ge t_3~.
• Subtarea 5 (10 puntos): ~t_1 = t_2~.
• Subtarea 6 (15 puntos): ~n \le 6~, ~t_2, t_3 \le 3~.
• Subtarea 7 (19 puntos): ~n \le 100~, ~t_2, t_3 \le 100~
• Subtarea 8 (13 puntos): Sin restricciones adicionales.

Entrada

La primera línea de entrada contiene un único número entero ~n~: el número de cosechadoras que deben producirse (~1 \le n \le 1000~).

La segunda línea contiene tres números enteros separados por espacios ~t_1~, ~t_2~ y ~t_3~: el tiempo requerido en cada etapa de producción para obtener una unidad del producto correspondiente (~1 \le t_1 \le 2~; ~1 \le t_2, t_3 \le 10^5~).

Salida

Imprima un único número entero: el tiempo mínimo requerido para producir ~n~ cosechadoras.

Ejemplos

Entrada 1

1
1 5 6

Salida 1

12

1. Es posible producir la primera componente de tipo I en el momento ~1~, después del cual la segunda fábrica puede comenzar inmediatamente a producir la componente II a partir de él.
2. En el momento ~1 + 5 = 6~ estará listo, y para entonces la primera fábrica producirá otras ~5~ componentes tipo I.
3. Uno de ellos, junto con el componente tipo II recién producido, se puede transferir inmediatamente a la tercera fábrica, y en el momento ~6 + 6 = 12~ se puede producir una cosechadora.

Entrada 2

2
2 1 4

Salida 2

12

Entrada 3

10
1 7 20

Salida 3

208