TAXI

Time Limit:
1.000 Sec
Memory Limit:
128Mb
Enviados:
149
Resuelto:
120

Descripción

Después de las lecciones, N grupos de jóvenes salieron y decidieron visitar a Juanito para celebrar su cumpleaños. Sabemos que el i-ésimo grupo está formado por Ai amigos (1 ≤ Ai ≤ 4) y quieren ir juntos a donde Juanito. Decidieron llegar en taxi. Cada coche puede transportar como máximo cuatro pasajeros.

¿Qué número mínimo de coches necesitarán los jóvenes si todos los miembros de cada grupo viajan en el mismo taxi (pero un taxi puede llevar a más de un grupo)?

Entrada

La primera línea contiene el número entero N (1 ≤ N ≤ 10^5): el número de grupos de escolares. La segunda línea contiene una secuencia de números enteros A1, A2, ..., An (1 ≤ Ai ≤ 4). Los números enteros están separados por un espacio, Ai es el número de jóvenes en el i-ésimo grupo.

Salida

Imprima el número único: el número mínimo de taxis necesarios para llevar a todos los jóvenes a donde Juanito.

Ejemplo Entrada

Copy icon
5
1 2 4 3 3

Ejemplo Salida

Copy icon
4

Ayuda

En el caso de prueba podemos ordenar a los jóvenes en cuatro coches así:

- el tercer grupo (compuesto por cuatro jóvenes),
- el cuarto grupo (compuesto por tres jóvenes),
- el quinto grupo (compuesto por tres jóvenes),
- el primer y el segundo grupo (compuesto por uno y dos jóvenes, respectivamente).
Hay otras formas de clasificar los grupos en cuatro coches.