Estantería


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Swift, VB

Cuando el Granjero Juan (GJ) no está ordeñando vacas, apilando fardos de heno, poniendo a sus vacas en filas o construyendo cercos, él disfruta sentando con un buen libro. A través de los años, él ha coleccionado N libros (1 \leq N \leq 2000), y quiere construir un nuevo conjunto de estantes para tenerlos a todos.

Cada libro tiene ancho W(i) y alto H(i). Los libros deben ser añadidos a un conjunto de estantes en orden; por ejemplo, el primer estante debe contener a los libros 1...k para algún k, el segundo debería comenzar con el libro k+1, y así sucesivamente. Cada estante debe tener un ancho de lo más L (1 \leq L \leq 1 000 000 000). La altura del estante es igual a la altura del libro más alto en ese estante, y la altura de todo el conjunto de estantes es la suma de las alturas de los estantes individuales, pues todos son apilados verticalmente.

Por favor, ayude a GJ a calcular la altura mínima de todo el conjunto de estantes.

Entrada

• Línea 1: Dos enteros separados por espacio: N y L.

• Líneas 2…1+N: La línea i+1 contiene dos enteros separados por espacio: H(i) y W(i). (1 \leq H(i) \leq 1000000; 1 \leq W(i) \leq L).

Ejemplo de Entrada

5 10
5 7
9 2
8 5
13 2
3 8

Detalles de la Entrada

Hay 5 libros. Cada estante puede tener un ancho a lo más de 10.

Salida

• Línea 1: La altura total mínima posible para el conjunto de estantes.

Ejemplo de Salida

21

Detalles de la Salida

Hay 3 estantes, el primero contiene únicamente al libro 1 (altura 5, ancho 7), el segundo contiene los libros 2...4 (altura 13, ancho 9) y el tercero contiene al libro 5 (altura 3, ancho 8).


Comments

There are no comments at the moment.