Description

有 $n$ 条线段，每条线段只能放在数轴上的一个特定位置，并且第 $i$ 根线段有如下几个属性：$X_i$（该线段放在数轴上的起点），$W_i$（该线段长度），$F_i$（你若使用该线段你能获得的价值），$C_i$（你若使用该线段你所需要的费用）。现在让你从中选出一些线段，使得这些线段能够铺满数轴上的区间 $[0,L]$ 且线段必须首尾相接（也就是不能重叠，也不能空缺），并且所花费用和不超过 $B$，同时要使你收获的价值尽量大，请你找到这个方案。

Input Format

第一行三个整数 $L, n, B$。

接下来 $n$ 行，每行四个整数 $X_i, W_i, F_i, C_i$ 表示第 $i$ 根线段的四个属性。

Output Format

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

Hint

对于 $100\%$ 的数据，保证 $1\le W_i\le L\le 1000,1\le N\le 10000,1\le F_i\le 10^6,1\le B,C_i\le 1000,0\le X_i\le L-W_i$