Maximum Fun Roller Coaster

The cows are building a roller coaster on a linear stretch of land with length \(L\) and they have a limited budget \(B\). They have \(N\) interchangeable components available. Each component \(i\) has a fixed length \(W_i\), a fun rating \(F_i\), and a cost \(C_i\). However, due to terrain restrictions, component \(i\) can only be placed starting at location \(X_i\), and if used, it occupies the segment from \(X_i\) to \(X_i + W_i\).

The roller coaster must start at position 0 and end exactly at position \(L\). Consecutive components must exactly meet, meaning the end of one component is the start of the next. The total fun is the sum of the fun ratings of the components used, and the total cost is the sum of their costs. The cows want to maximize the total fun without exceeding the budget \(B\).

Given the map of available components, determine the maximum total fun that can be achieved while building a valid roller coaster within the budget.

inputFormat

The first line contains three integers \(L\), \(N\), and \(B\) \((1 \leq L \leq 1000,\ 1 \leq N \leq 10000,\ 1 \leq B \leq 1000)\), representing the length of the land, the number of available components, and the budget respectively.

Each of the following \(N\) lines contains four integers \(X_i\), \(W_i\), \(F_i\), and \(C_i\) \((0 \leq X_i \leq L - W_i,\ 1 \leq W_i \leq L,\ 1 \leq F_i \leq 10^6,\ 1 \leq C_i \leq 1000)\), describing a component's starting position, length, fun rating, and cost.

outputFormat

Output a single integer: the maximum total fun that can be obtained by constructing a roller coaster from position 0 to \(L\) without exceeding the budget \(B\). If no valid construction is possible, output an appropriate value (for example, 0).

sample

10 4 10
0 5 10 5
5 5 20 5
0 10 15 10
0 10 10 5

30