问题 1305. -- 富裕的ar老师

1305: 富裕的ar老师

时间限制: 1 Sec  内存限制: 128 MB
提交: 66  解决: 30
[提交][状态][讨论版]

题目描述

ar老师是XDU第二壕的ACMer,jlz也想像他一样富有。对于优秀的jlz来说,打工是不可能打工的,这辈子都不可能打工的,因为jlz要自己开一家电瓶车公司。
jlz有n辆电瓶车,每辆电瓶车都有它的外观评分xi和实用性评分yi。同时,jlz接到了m个订单,每个订单都有要求的最低的外观评分xi和实用性评分yi。
只有当电瓶车的两种评分均不低于订单要求时jlz才可以成交该订单,每完成一个订单,jlz将获得500*xi+2*yi元的纯利润(这里的xi与yi指该订单的最低要求的外观评分xi和实用性评分yi,
每个订单仅购买一辆电动车,每辆电动车只能被卖一次。jlz想知道,在成交订单数量最多的情况下他能获得的最大纯利润是多少元?

输入

第一行输入测试组数T。对于每组数据,第一行输入n,m,1<=n,m<=100000,紧接着输入n行,
第i+1行的xi与yi分别表示电动车外观评分xi和实用性评分yi,紧接着输入m行,第i+n+1行的xi与yi分别表示订单的最低外观评分xi和最低实用性评分yi。
其中1<=T<=10,1<=xi<= 1440,1<=yi<=1000

输出

每组数据输出一行结果,该行仅包含二个整数,表示jlz可卖出的最多电车数与最大纯利润

样例输入

1
1 2
100 3
100 2
100 1

样例输出

1 50004

提示

对于第一组数据,jlz可以通过卖掉第一辆电动车给第一个订单获得100*500+2*2=50004的利润。

来源

[提交][状态][讨论版]