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

输入格式

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

接下来 $n$ 行，每行四个整数 $X_i, W_i, F_i, C_i$ 表示第 $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

6 11 100
0 6 876 18
0 4 169 1
0 2 496 9
1 3 697 10
1 1 739 5
2 2 358 11
3 1 891 18
4 1 271 12
5 1 771 27
5 1 754 2
5 1 950 26

2075

17 35 6
0 12 334 5
0 16 679 27
1 6 172 27
2 3 205 21
2 12 785 27
2 4 243 18
3 2 747 15
3 5 141 15
4 1 12 10
5 3 708 29
6 10 443 11
6 9 548 2
6 8 620 11
7 5 617 2
7 7 179 10
8 7 848 5
9 5 993 17
9 6 702 30
10 1 295 3
10 3 640 26
11 1 950 27
11 3 514 15
11 6 239 10
12 2 805 20
12 2 19 29
12 2 968 1
13 2 453 28
13 1 118 19
13 2 100 19
14 1 127 28
14 1 369 4
15 2 589 17
15 2 599 10
15 1 426 15
16 1 746 1

-1

说明/提示

对于 $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$