Bombillas P43214

En el piso del autor de este problema no se gana para sustos. Por ejemplo, la última factura de luz llegó en papel extra-grande para que cupiera el precio. Por eso se ha decidido invertir en n bombillas de bajo consumo, que se han instalado todas en la cocina.

Una bombilla está definida por dos parámetros: el consumo inicial i, que es la cantidad de julios que gasta para encenderse, y el consumo temporal t, que es la cantidad de julios que gasta por cada minuto que esté encendida. Así, si queremos iluminar la cocina durante poco tiempo, quizá convenga más encender una bombilla que tenga un consumo inicial bajo, aunque su consumo temporal sea más alto, mientras que si queremos iluminarla durante más tiempo tal vez convenga encender una bombilla cuyo consumo temporal sea menor, a pesar de que el inicial sea más alto. De hecho, puede que hasta nos interese dejar encendida una bombilla aunque durante un rato nadie esté usando la cocina, para ahorrarnos el coste de volver a encenderla más tarde. ¡Cada julio cuenta!

Aquí es donde necesitamos vuestra ayuda. Tenemos la información de las n bombillas, y una lista con los m intervalos en los que la cocina está ocupada a lo largo del día. Las horas empiezan a las 00:00 y acaban a las 23:59. Al principio del día todas las luces están apagadas. Siempre que haya alguien en la cocina tiene que haber al menos una luz encendida. ¿Cuál es la mínima energía necesaria para iluminar todos los intervalos?

Entrada

La entrada consiste en diversos casos. Cada caso empieza con n y m, seguidas de n pares de enteros i y t describiendo las bombillas, seguidos de m pares de horas en el formato hh:mm, indicando el momento inicial y final de cada intervalo. Las 2m horas de cada caso aparecen en orden estrictamente creciente. Podéis suponer 1 ≤ n ≤ 2000, m ≥ 1, 1 ≤ i ≤ 2 · 10⁵, 1 ≤ t ≤ 2000, 00 ≤ hh ≤ 23, y 00 ≤ mm ≤ 59.

Salida

Para cada caso, escribid el mínimo consumo de energía necesario.

Puntuación

• Test1:   Resolver entradas donde n = 1.  20 Puntos 

• Test2:   Resolver entradas donde n ≤ 2.  20 Puntos 

• Test3:   Resolver entradas donde n ≤ 100.  30 Puntos 

• Test4:   Resolver entradas de todo tipo.  30 Puntos