中等题——伪流水线调度

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 0 总提交人数: 0

题目描述

江南最大的皮革厂即将倒闭,厂长不知去向,但是厂内的机器还在。本着人道主义精神,Nova君决定帮助这家工厂完成尚未完成的订单。Nova君清点了工厂的物资,发现在有n个机器可以工作,还有m个订单没有完成。由于是快要倒闭的工厂,设备破旧,每个机器至多能完成一个任务,完成后就报废了。对于机器 i ,有一个最大运行时间xi和等级yi,对于订单 j ,也有一个完成所需时间xj和等级要求yj。只有当xi>=xj且yi>=yj的时候,机器 i才能完成任务 j,并获得1000xj+10yj的利润。请问最多能完成几个任务?当出现多种情况时,输出获得利润最多的情况。

输入

多组测试数据(组数不超过100),对于每组数据,第一行为两个正整数N和M,N代表机器数,M代表订单数。接下来输入N行,每行两个正整数xi和yi,接下来M行,每行两个正整数xj和yj。

1<= N <=100000,1<= M <=100000,0<xi<1000,0=<yi<=100,0<xi<1000,0=<yi<=100

xi、yi、xj、yj 具体含义见题目描述

输出

对于每组数据,输出一行,包含两个正整数,第一个为可以完成的订单数的最大值,第二个是获得的利润。

输入样例

1 2
100 3
100 2
100 1

输出样例

1 100020

相关推荐