SP14864 SALES - Sales

Bosco 手中有 $ B $ 美元（$ 1 \leq B \leq 50 $）。作为《万智牌》的爱好者，他希望用部分预算购买新牌来提升牌组实力。 他发现了一家出售 $ N $ 张卡片的本地商店（$ 1 \leq N \leq 30,000 $）。第 $ i $ 张卡片标价 $ c_i $ 美元（$ 1 \leq c_i \leq 50 $），可以提升 Bosco 的牌组质量指数（DQI） $ v_i $ 点（$ 1 \leq v_i \leq 1000 $）。每种牌只有一张可以出售。 最近生意不景气，商店决定在不同日期搞促销。尽管称为“促销”，但实际是“价格调整”，因为价格可能会上涨。Bosco 计划在这些促销日挑选一天购物。他已经拿到了价格调整的清单。 在第 $ i $ 天，第 $ a_i $ 张卡片的价格调整为 $ b_i $ 美元（$ 1 \leq a_i \leq N $ 且 $ 1 \leq b_i \leq 50 $），其他卡片价格不变。从第一天开始，每天的价格变动会累积。 此外，每天实际上只有某些卡片可以购买。具体来说，第 $ i $ 天，只有编号从 $ x_i $ 到 $ y_i $ 的卡片（$ 1 \leq x_i \leq y_i \leq N $）可以买。 Bosco 不在乎花多少预算，但他一定要确保他的牌组最好。因此，对于每一天，他都需要评估能组合出最大 DQI 总和的卡片（可能是空集），其花费不能超过 $ B $ 美元。帮助 Bosco 计算出每一天最大的 DQI 总和，以便他在最佳时机抢购这些“特价”商品。

第一行为三个整数：$ B$，$ N $，$ D $ 接下来 $ N $ 行，每行两个整数，$ c_i $ 和 $ v_i $，表示每张卡片的初始价格和对应的 DQI 值 接下来 $ D $ 行，每行四个整数，$ a_i $，$ b_i $，$ x_i $，$ y_i $，表示第 $ i $ 天的价格调整信息及可购买卡片范围

对每一天，输出 Bosco 能在预算范围内购买的卡片，其 DQI 最大化后的总和。

- $ 1 \leq B \leq 50 $ - $ 1 \leq N \leq 30,000 $ - $ 1 \leq D \leq 3000 $ - $ 1 \leq c_i \leq 50 $ - $ 1 \leq v_i \leq 1000 $ - $ 1 \leq a_i \leq N $ - $ 1 \leq b_i \leq 50 $ - $ 1 \leq x_i \leq y_i \leq N $ **本翻译由 AI 自动生成**