Montaña Rusa Vacuna
¡Las vacas están construyendo una montaña rusa! Ellas quieren que usted las ayude para diseñar una montaña rusa tan divertida como sea posible, manteniéndose dentro del presupuesto.
La montaña rusa será construida en la tira estrecha de terreno de longitud . La montaña rusa tiene una colección de algunas de componentes intercambiables. Cada componente tiene una longitud fija . Debido a variaciones de terreno, cada componente puede solo ser construida comenzando en la ubicación . Las vacas quieren poner juntas varias componentes de montaña rusa comenzando en y terminando en de tal manera que al final de cada componente (excepto la última) esté el inicio de la siguiente.
Cada componente tiene una calificación de diversión y un costo de . La diversión total de la montaña rusa es la suma de las diversiones de cada componente usada. El presupuesto total de las vacas es . Ayude a las vacas a determinar la montaña rusa más divertida que ellas pueden construir con su presupuesto.
Entrada
• Línea 1: Tres enteros separados por espacios: , y .
• Líneas 2...N+1: La línea contiene cuatro enteros separados por espacios, respectivamente: , , y .
Salida
• Línea 1: Un solo entero que es el máximo valor de diversión que puede tener una montaña rusa manteniéndose dentro del presupuesto cumpliendo todas las otras restricciones. Si no es posible construir una montaña rusa dentro del presupuesto, dé como salida \(–1\).
Ejemplo de Entrada
5 6 10
0 2 20 6
2 3 5 6
0 1 2 1
1 1 1 3
1 2 5 4
3 2 10 2
Ejemplo de Salida
17
Explicación
Tomando las componentes , y se tiene una montaña rusa conectada con valor de diversión y costo . Tomando las dos primeras componentes daría una montaña rusa con mayor diversión , pero estaría fuera del presupuesto.
Comments