题目描述

奶牛们正打算造一条过山车轨道．她们希望你帮忙，找出最有趣，但又符合预算的方案．

过山车的轨道由若干钢轨首尾相连，由$\red{x=0}$处一直延伸到$\red{X=L(1≤}$$\red{L≤}$$\red{1000)}$处．现有$\red{N(1≤}$$\red{N≤}$$\red{10000)}$根钢轨，每根钢轨的起点$\red{X_i(0≤}$$\red{X_i≤}$$\red{L- W_i)，}$长度$\red{W_i(l≤}$$\red{W_i≤}$$\red{L)，}$有趣指数$\red{F_i(1≤}$$\red{F_i≤}$$\red{1000000)，}$成本$\red{C_i(l≤}$$\red{C_i≤}$$\red{1000)}$均己知．

请确定一种最优方案，使得选用的钢轨的有趣指数之和最大，同时成本之和不超过$\red{B(1≤}$$\red{B≤}$$\red{1000)}$．

输入格式

第$\red{1}$行输入$\red{L，}$$\red{N，}$$\red{B}$

接下来$\red{N}$行，每行四个整数$\red{X_i，}$$\red{W_i，}$$\red{F_i，}$$\red{C_i}$．

输出格式

第$\red{1}$行： 一个整数，它是过山车在预算内并满足所有其他约束条件时可以拥有的最大乐趣值。

如果不可能在预算内建造过山车，产出为$\red{-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

提示

选用第$\red{3}$条，第$\red{5}$条和第$\red{6}$条钢轨