Background

Special for beginners, ^_^

Description

有 N 个区间[Xi,Xi+Wi）,代价是 Ci,可供娱乐程度为 Fi。现在要用这些区间
完全覆盖[0,L），区间之间不能有重叠，并且区间代价和不超过 B。求最大的可
供娱乐程度。如果不能完全覆盖，则输出-1。
L(1 ≤ L ≤ 1,000).
N (1 ≤ N ≤ 10,000)
W i (1 ≤ W i ≤ L).
X i (0 ≤ X i ≤ L - W i ).
F i (1 ≤ F i ≤ 1,000,000)
C i (1 ≤ C i ≤ 1000).
B (1 ≤ B ≤ 1000).
输入文件：
第一行为 L，N 和 B；
以下 N 行，每行为
X i , W i , F i , 和 C i .
输出文件：
最大的可供娱乐程度。不能完全覆盖，则输出-1

Format

Samples

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

Limitation

选取的区间为第 3，5，6 区间，总代价为 7，娱乐程度为 17；如果选取 1，2， 娱乐程度为 25，但总代价超过 10。