题目详情题解（0）讨论（0）提交记录（0）

A7443.日行一善

普及+/提高

官方

通过率：0%

时间限制：1.00s

内存限制：128MB

题目描述

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

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

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

这四个数字分别是:

  • SiS_i:该金条在数轴上的起点
  • WiW_i:该金条的长度
  • ViV_i:该金条所能获得的价钱
  • CiC_i:把该金条放到数轴对应位置所需支付的价钱。

数轴上的文字是:

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

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

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

输入格式

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

随后nn行，每行输入四个整数Si(0≤Si≤L−Wi),Wi(1≤Wi≤L),Vi(1≤Vi≤106),Ci(1≤Ci≤103)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
首页