P0949

[Usaco2006 Dec]Cow Roller Coaster

[Usaco2006 Dec]Cow Roller Coaster

奶牛们打算修建一条过山车轨道。她们希望在预算范围内，让过山车尽可能有趣。

轨道位于一段长度为 LL 的直线上，需要从位置 00 开始，连续延伸到位置 LL。现有 NN 个不同的轨道组件，每个组件 ii 的起点为 XiX_i，长度为 WiW_i，因此其终点为 Xi+WiX_i+W_i。受地形限制，每个组件只能安装在指定的位置。

所选组件必须首尾相接：第一个组件从位置 00 开始，每个组件的终点都必须是下一个组件的起点，最后一个组件的终点必须为位置 LL。

组件 ii 的有趣指数为 FiF_i，成本为 CiC_i。整条轨道的有趣指数是所有所选组件的有趣指数之和，总成本也是所有所选组件的成本之和。

奶牛们的预算为 BB。请在总成本不超过 BB 的前提下，求能够修建的轨道的最大有趣指数。

输入格式

第一行包含三个整数 LL、NN 和 BB，分别表示轨道总长度、可选组件数量和预算。

接下来 NN 行，第 ii 行包含四个整数 XiX_i、WiW_i、FiF_i 和 CiC_i，分别表示组件 ii 的起点、长度、有趣指数和成本。

输出格式

输出一个整数，表示在满足所有条件且总成本不超过预算时，轨道能够获得的最大有趣指数。

如果无法在预算范围内修建一条从位置 00 延伸到位置 LL 的完整轨道，输出 −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

样例输出

17

数据范围

  • 1≤L≤1031\le L\le 10^3；
  • 1≤N≤1041\le N\le 10^4；
  • 1≤B≤1031\le B\le 10^3；
  • 0≤Xi≤L−Wi0\le X_i\le L-W_i；
  • 1≤Wi≤L1\le W_i\le L；
  • 1≤Fi≤1061\le F_i\le 10^6；
  • 1≤Ci≤1031\le C_i\le 10^3。

来源与许可

本题为 USACO 2006 December 试题「Cow Roller Coaster」，题面与测试数据整理自 BZOJ。

样例 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

输出

17