问题描述

有n条线段，每条线段只能放在数轴上的一个特定位置，并且第i根线段有如下几个属性：Xi（该线段放在数轴上的起点），Wi（该线段长度），Fi（你若使用该线段你能获得的价值），Ci（你若使用该线段你所需要的费用）。现在让你从中选出一些线段，使得这些线段能够铺满数轴上的区间[0,L]，并且所花费用和不超过B，同时要使你收获的价值尽量大，请你找到这个方案。

输入

第一行三个整数 L（1 ≤L≤1,000），n（1≤N≤10,000），B（1 ≤B≤1,000）。

接下来n行，每行四个整数 Xi，Wi，Fi，Ci，表示第i根线段的四个属性。

输出

一个整数，表示你能获得的最大价值和。若无法满足上述要求，则输出−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