Estantería
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 libros , y quiere construir un nuevo conjunto de estantes para tenerlos a todos.
Cada libro tiene ancho y alto . Los libros deben ser añadidos a un conjunto de estantes en orden; por ejemplo, el primer estante debe contener a los libros para algún , el segundo debería comenzar con el libro , y así sucesivamente. Cada estante debe tener un ancho de lo más . 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: y .
• Líneas 2…1+N: La línea contiene dos enteros separados por espacio: y . .
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 estantes, el primero contiene únicamente al libro (altura , ancho ), el segundo contiene los libros (altura , ancho ) y el tercero contiene al libro (altura , ancho ).
Comments