题目描述

奶牛们正在建造过山车！它们希望在预算范围内设计出尽可能有趣的过山车，需要你的帮助。

过山车将建在一段长度为$L$（$1 \leq L \leq 1000$）的直线型土地上，由$N$（$1 \leq N \leq 10000$）种不同的可互换组件中挑选若干组成。每个组件$i$有固定长度$W_i$（$1 \leq W_i \leq L$），由于地形差异，组件$i$只能从位置$X_i$（$0 \leq X_i \leq L - W_i$）开始建造。奶牛们希望过山车从位置$0$开始，到位置$L$结束，且除最后一个组件外，每个组件的终点必须是下一个组件的起点。

每个组件$i$有“趣味值”$F_i$（$1 \leq F_i \leq 1000000$）和成本$C_i$（$1 \leq C_i \leq 1000$）。过山车的总趣味值为所有使用组件的趣味值之和，总成本为所有使用组件的成本之和。奶牛的总预算为$B$（$1 \leq B \leq 1000$）。请帮助奶牛确定在预算内且满足所有约束条件下，能建造的过山车的最大趣味值。若无法在预算内建造过山车，输出$-1$。

输入格式

• 第1行：三个空格分隔的整数$L$、$N$和$B$。
• 第2到$N+1$行：第$i+1$行包含四个空格分隔的整数$X_i$、$W_i$、$F_i$和$C_i$，分别表示组件$i$的起始位置、长度、趣味值和成本。

输出格式

• 第1行：一个整数，表示预算内可建造的过山车的最大趣味值。若无法建造，输出$-1$。

输入样例 1

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

输出样例 1

17

样例解释

选择第3、5、6个组件时，过山车路径连续（从0开始，依次经过位置0→1→2→3→5），总趣味值为$2+5+10=17$，总成本为$1+4+2=7$，未超过预算。若选择前两个组件，总趣味值为$20+5=25$，但总成本$6+6=12$超过预算$10$，因此不可行。

来源

USACO 2006 十二月银牌赛