¡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 ~L~ ~(1 \leq L \leq 1000)~. La montaña rusa tiene una colección de algunas de ~N~ ~(1 \leq N \leq 10 000)~ componentes intercambiables. Cada componente ~i~ tiene una longitud fija ~W_i~ ~(1 \leq W_i \leq L)~. Debido a variaciones de terreno, cada componente ~i~ puede solo ser construida comenzando en la ubicación ~X_i~ ~(0 \leq X_i \leq L-W_i)~. Las vacas quieren poner juntas varias componentes de montaña rusa comenzando en ~0~ y terminando en ~L~ de tal manera que al final de cada componente (excepto la última) esté el inicio de la siguiente.

Cada componente ~i~ tiene una calificación de diversión ~F_i~ ~(1 \leq F_i \leq 1 000 000)~ y un costo de ~C_i~ ~(1 \leq C_i \leq 1000)~. 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 ~B~ ~(1 \leq B \leq 1000)~. 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: ~L~, ~N~ y ~B~.

• Líneas 2...N+1: La línea ~i+1~ contiene cuatro enteros separados por espacios, respectivamente: ~X_i~, ~W_i~, ~F_i~ y ~C_i~.

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 ~3~, ~5~ y ~6~ se tiene una montaña rusa conectada con valor de diversión ~17~ y costo ~7~. Tomando las dos primeras componentes daría una montaña rusa con mayor diversión ~(25)~, pero estaría fuera del presupuesto.