Problema número 409

Seleccionando castellers

Tiempo máximo: 1,000-2,000 sMemoria máxima: 4096 KiB
Integrantes de un castell

La colla castellera "Xiquets de Reus" ensaya duramente para mejorar sus castells, lo que le lleva a conseguir constantes récords en la elaboración de formaciones cada vez más complejas.

Un castell es una torre humana donde toda su estructura se mantiene en pie exclusivamente gracias a la fuerza de sus integrantes, llamados castellers.

Los castells se clasifican en función de dos factores. El primero es el número de personas que forman cada nivel (también llamados plantas o pisos); el segundo es su altura, es decir el número de plantas que alcanza. Se utiliza la notación cdn, donde c indica el número de castellers en cada nivel, y n el número de niveles. Cuando los pisos están compuestos por un único casteller, la construcción es conocida con el nombre de pilar, y en ese caso en lugar de poner un 1 en la c, se pone directamente una p (por ejemplo, pd8).

La figura de la derecha muestra un castell 4d8. Observa que en la parte superior aparecen 3 pisos que no están compuestos por 4 personas. Debido a su dificultad e importancia, los tres niveles superiores son especiales y reciben nombres particulares:

  • Enxaneta: es el casteller que se sitúa en el nivel más alto, y da validez a la estructura.
  • Acotxador: también llamado aixecador, es el casteller que se sitúa horizontalmente en el penúltimo nivel, dando el apoyo necesario al enxaneta.
  • Dosos: son los dos integrantes del antepenúltimo nivel, justo debajo del acotxador. En los pilares, este piso también consta de un único integrante.

Al margen de la estructura central, existen un conjunto de castellers que se posicionan en la base formando la piña, que respalda toda la estructura conforme va creciendo. Opcional y adicionalmente a ella, también se puede situar un pequeño grupo de castellers por encima de la piña, para afianzar el segundo nivel cuando la altura del castell y su complejidad así lo requieren. Esta estructura se llama folre.

Para que un castell alcance altura y estabilidad, son muchos los factores a tener en cuenta durante su construcción: la fuerza de sus integrantes, su altura, su peso, experiencia, valentía, soltura… Por ejemplo, para evitar desequilibrios, es importante que los castellers de un mismo piso tengan una diferencia de altura de, como máximo, 15 centímetros. Las comisiones técnicas de las collas castelleras deben decidir quién integrará cada piso en función de las alturas de los castellers de los que disponen debido a esta restricción.

Entrada

La primera línea de la entrada indicará el número de casos de prueba que deberá procesar el programa.

Para cada caso de prueba se indicará en una primera línea el número de castellers por nivel de la construcción que se quiere intentar en la próxima salida (entre 1 y 9), junto a la cantidad de integrantes de la colla entre los que elegirlos (entre 1 y 100).

La siguiente línea del caso de prueba contendrá las alturas de todos ellos, expresadas en centímetros, sin ningún orden particular. Las alturas fluctúan entre 100 y 220 centímetros.

Salida

Para cada caso de prueba, el programa escribirá el número máximo de niveles del tamaño indicado que se pueden formar con los castellers de la colla, manteniendo la restricción de que la máxima diferencia de alturas entre los integrantes de un piso no puede ser mayor de 15 centímetros.

Por su importancia, la comisión técnica ha elegido ya quienes serán el enxaneta, el actoxador y los dosos, por lo que sus alturas no se listan en la entrada, y no deben tenerse en cuenta para la salida. Tampoco hay que preocuparse de la piña ni el folre que, aunque tienen una importancia clave en la construcción, son más tolerantes con las diferencias de alturas.

Entrada de ejemplo

4
3 9
152 159 167 173 180 188 194 201 209
3 9
152 160 168 176 184 192 200 208 216
3 10
170 105 130 175 180 192 195 172 195 165
2 10
170 105 130 175 180 192 195 172 195 165

Salida de ejemplo

3
0
2
4