Hojas y abejas P27309

¡Ya es primavera! El huerto de nuestro amigo Pau Gargallo está a rebosar de flores. Sin embargo, y por motivos difíciles de explicar (y que no vienen a cuento) nosotros estamos más interesados en las hojas. Pau sólo nos deja cortar plantas con flor, y nos cobra F céntimos de euros por cada planta florecida que cortemos; por otra parte, sabemos que podemos conseguir L céntimos de euro por cada hoja que vendamos en el mercado negro de coleccionistas de hojas. ¿Sabrías decirnos cuál es el máximo beneficio que podemos obtener, y cuántas plantas deberíamos cortar para conseguirlo? En caso de que hubiera varios modos distintos de conseguir el mismo beneficio, nuestra naturaleza perezosa nos impulsa a aceptar únicamente como respuesta válida aquella que requiera cortar el mínimo número de plantas.

Un pequeño detalle: ¡algunas flores tienen abejas! Bajo ningún concepto nos atreveremos a cortar plantas cuya flor tenga al menos una abeja.

Entrada

Una entrada contiene un único jardín. La primera línea del jardín contiene los números 0≤ F≤ 1000, 0≤ L≤ 1000 i 3≤ m≤ 1000, que son, respectivamente, el coste de cortar una planta, el beneficio que obtenemos por hoja, y la longitud del jardín. La descripción de un jardín de longitud m ocupa m líneas (mirad los ejemplos de entrada para entender mejor la explicación).

• Cada fila del jardín puede contener una planta.
• El carácter - indica el tallo de la planta.
• El carácter b indica una hoja que pertenece al tallo situado inmediatamente por debajo.
• El carácter P indica una hoja que pertenece al tallo situado inmediatamente por arriba.
• Un cuadrado 3 por 3 formado por caracteres x o B, y situado al final de un tallo (el tallo finaliza en el medio de la pared izquierda del cuadrado), indica que la planta está florecida. Los caracteres B representan trozos de flor ocupados por abejas.

  Ninguna planta tiene un tallo de longitud superior a 80.

Las plantas situadas en la primera y la última posición del jardín nunca tendrán flores. Los carácteres de dos plantas distintas nunca se superpondrán unos a otros.

Salida

Escribe dos líneas, cada una de ellas acabada en un retorno de línea. En la primera línea debes escribir el máximo beneficio que se puede obtener del jardín en céntimos de euro, y en la segunda línea el mínimo número de cortes necesarios para conseguirlo.

Puntuación

• TestA:  35 Puntos 

  Juegos de prueba donde entre cada par de tallos hay, al menos, un espacio sin planta, como en el ejemplo 1 o el ejemplo 2.

• TestA:  65 Puntos 

  Juegos de prueba donde no existe la limitación anterior.