旅馆订单
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
你经营着一家旅馆,这家旅馆有 个房间,每个房间有维护费用和容量。其中第 个房间的维护费用为 ,容量为 人。注意:对于 ,若 ,则 。
现在有 个订单,每个订单有两个参数: ,其中 表示这个订单支付的租金, 表示人数。
你现在得要合理选择一些订单,并放弃其他订单,使得每个选择的订单被安排在同一间房间内,且人数不超过这个房间的容量限制。当然,两个不同的订单也不能被安排在同一间房间内。
现在你想要知道,在最多选出 个订单时的最大收益。一个方案的收益的定义为,选出的订单的租金和,减去选出的房间的维护费用和。
输入格式
第一行三个空格隔开的整数 。
接下来 行,每行两个空格隔开的整数 。
接下来 行,每行两个空格隔开的整数 。
输出格式
一行一个整数表示最大收益。注意答案可能很大。
样例 #1
样例输入 #1
3 2 2
150 2
400 3
100 2
200 1
700 3
样例输出 #1
400
提示
样例 解释
可以将第一个订单安排至第三个房间,将第二个订单安排至第二个房间。
数据范围
对于 的数据,有 $1 ≤ n,m ≤ 500\ 000;1 ≤ o ≤ \min(n,m);1 ≤ c_i,p_i,v_i,d_i ≤ 10^9$。输入数据保证对于 ,若 ,则 。