Cow Roller Coaster

The cows are building a roller coaster, and they want it to be as fun as possible while staying within their budget.

The track is a straight line of length $L$. There are $N$ interchangeable components. Component $i$ has a fixed length $W_i$ and, because of the terrain, can only be placed starting at position $X_i$, so it covers the interval $[X_i, X_i + W_i]$. The cows connect components so that the coaster starts at position $0$ and ends at position $L$, with the end of each component (except the last) being exactly the start of the next one. In other words, the chosen components must tile the whole segment $[0, L]$ with no gaps and no overlaps.

Each component $i$ has a fun rating $F_i$ and a cost $C_i$. The coaster's total fun is the sum of the fun ratings of the components used, and its total cost is the sum of their costs. The total budget is $B$. Determine the maximum total fun of a coaster that spans $[0, L]$ and costs at most $B$.

Constraints

• $1 \le L \le 1000$
• $1 \le N \le 10000$
• $1 \le W_i \le L$
• $0 \le X_i \le L - W_i$
• $1 \le F_i \le 1000000$
• $1 \le C_i \le 1000$
• $1 \le B \le 1000$

• Line 1: three space-separated integers $L$, $N$, and $B$.
• Lines $2 \dots N+1$: line $i+1$ contains four space-separated integers $X_i$, $W_i$, $F_i$, and $C_i$.

• A single integer: the maximum total fun of a coaster that covers the entire track $[0, L]$ while staying within the budget. If no such coaster can be built, output $-1$.

For the first test case, one optimal choice is to take the components on input rows 3, 5, and 6: they form a connected coaster covering $[0, 5]$ with total fun $17$ and total cost $7$, which is within the budget of $10$. Taking the first two components would give more fun ($25$), but their combined cost is $12$, which exceeds the budget.