← 返回比赛
已结束 GESP排位赛 #3
← 上一题 下一题 →

A1549 | 日行一善

来源官方 / 2023
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

Yuilice有一天扶老奶奶过马路，老奶奶为了报答Yuilice，给了他一条数轴和$n$条金条奖励。

但是这$n$条金条黏在了一块积木板上，Yuilice一旦把它们拿去换钱，他们就会飞回积木板上。

Yuilice愁昏了头，但是他细心的发现，每根金条上写着四个数字和数字的解释，并且在数轴上刻画着几行字。

这四个数字分别是:

- $S_i$:该金条在数轴上的起点
- $W_i$:该金条的长度
- $V_i$:该金条所能获得的价钱
- $C_i$:把该金条放到数轴对应位置所需支付的价钱。

数轴上的文字是:

- 假若你将一根金条放到数轴对应位置上，你可获得该金条对应的价钱，但是你必须刚好铺满$[0,L]$的这块区域。
- 铺上去的金条必须首尾相连，不可以重叠，也不可以空缺，否则你将一无所获。

Yuilice抠抠搜搜一共就只有$B$元钱，他想请你帮帮他，怎样安排他才能拿到最多的金钱？

注意:你必须要刚好铺满0~L这块区域才可以获得价值

输入格式

第一行输入三个整数$L,n,B(1 \leq L \leq 10^3 , 1 \leq n \leq 10^4 , 0 \leq B \leq 10^3)$

随后$n$行，每行输入四个整数$S_i(0 \leq S_i \leq L - W_i),W_i(1 \leq W_i \leq L),V_i(1 \leq V_i \leq 10^6),C_i(1 \leq C_i \leq 10^3)$，代表每根金条的信息。

输出格式

输出一个数字，代表Yuilice能够获得最大的价值，如果一无所获，那么请输出-1。

输入输出样例

输入 #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
输出 #1
17
C++ 编辑器
输入
输出