问题 1304. -- 富裕的wang9897

1304: 富裕的wang9897

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

题目描述

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

输入

第一行输入测试组数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<=100

输出


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

样例输入

1
1 2
100 3
100 2
100 1

样例输出

1 50004

提示

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

来源

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