#P4698. [CEOI2011] Hotel

[CEOI2011] Hotel

题目描述

你经营着一家旅馆,这家旅馆有 nn 个房间,每个房间有维护费用和容量。其中第 ii 个房间的维护费用为 cic_i,容量为 pip_i 人。

现在有 mm 个订单,每个订单有两个参数:vi,div_i,d_i ,其中 viv_i 表示这个订单支付的租金,did_i​​ 表示人数。

你现在得要合理选择一些订单,并放弃其他订单,使得每个选择的订单被安排在同一间房间内,且人数不超过这个房间的容量限制。当然,两个不同的订单也不能被安排在同一间房间内。

现在你想要知道,在最多选出 oo 个订单时的最大收益。一个方案的收益的定义为,选出的订单的租金和,减去选出的房间的维护费用和。

输入格式

第一行三个空格隔开的整数 n,m,on,m,o

接下来 nn 行,每行两个空格隔开的整数 ci,pic_i,p_i

接下来 mm 行,每行两个空格隔开的整数 vi,div_i,d_i

输出格式

一行一个整数表示最大收益。注意答案可能很大。

3 2 2
150 2
400 3
100 2
200 1
700 3
400

提示

样例 11 解释

可以将第一个订单安排至第三个房间,将第二个订单安排至第二个房间。

数据范围

对于 100%100\% 的数据,有 $1\le n,m\le 500\ 000;1\le o\le \min(n,m);1\le c_i,p_i,v_i,d_i\le 10^9$,保证 1i,jn\forall 1\le i,j\le n,若 pi<pjp_i\lt p_j,则 cicjc_i\le c_j