奶牛们正在建造过山车！他们希望你的帮助，在保持预算的同时，设计出尽可能有趣的过山车。

过山车将建在长度为L（$1≤L≤1000$）的长线性陆地上。过山车由N个（$1≤N≤10000$）不同可互换部件的集合组成。每个分量i具有固定长度$W_i$（$1≤W_i≤L$）。由于地形变化，每个部件i只能从$X_i$位置开始建造（$0≤X_i≤L - W_i$）。奶牛想把从0开始到L结束的各种过山车组件串在一起，这样每个组件的结束（除了最后一个）就是下一个组件的开始。

每个组件i都有一个“乐趣评级”$F_i$（$1≤F_i≤1000000$）和一个成本$C_i$（$1≤C_i≤1000$）。压路机的总乐趣是所使用的每个组件的乐趣之和；总成本同样是所使用的每个组件的成本之和。奶牛的总预算为$B$（$1≤B≤1000$）。

帮助奶牛确定他们可以用预算建造的最有趣的过山车。

第1行：三个空格分隔的整数：L、N和B。

第2.N+1行：第i+1行包含四个空分整数，分别为：$X_i$、$W_i$、$F_i$和$C_i$。

一个整数，是过山车在预算范围内并满足所有其他限制的情况下可以获得的最大乐趣值。如果不可能在预算范围内建造过山车，则输出-1。

Taking the 3rd, 5th and 6th components gives a connected roller-coaster with fun value 17 and cost 7. Taking the first two components would give a more fun roller-coaster (25) but would be over budget.

USACO