2231. [HDOJ 4864]Task

【题目描述】

今天公司有 $m$ 项任务要完成。第 $i$ 项任务需要 $x_i$ 分钟来完成。同时，这个任务有一个困难级别 $y_i$。级别低于该任务级别 $y_i$ 的机器无法完成这项任务。如果公司完成了这项任务，他们将获得 $(500\times x_i+2\times y_i)$ 美元。

公司有 $n$ 台机器。每台机器都有最大工作时间和一个级别。如果任务的时间超过机器的最大工作时间，则该机器无法完成这个任务。每台机器一天只能完成一项任务。每项任务只能由一台机器完成。

公司希望最大化今天他们可以完成的任务数量。如果存在多个解决方案，他们希望使收益最大化。

【输入格式】

第一行包含两个整数 $N$ 和 $M$。$N$ 是机器的数量。$M$ 是任务的数量 $(1 \leq N \leq 100000, 1\leq M\leq 100000)$。

接下来的 $N$ 行每行包含两个整数 $x_i(0<x_i<1440),y_i(0\leq y_i\leq 100)$。$x_i$ 是机器可以工作的最长时间。$y_i$ 是机器的级别。

接下来的 $M$ 行每行包含两个整数 $x_i(0<x_i<1440),y_i(0\leq y_i\leq 100)$。$x_i$ 是完成任务所需的时间。$y_i$ 是任务的级别。

【输出格式】

对于每个测试用例，输出两个整数，代表公司今天可以完成的最大任务数以及他们将获得的收入。

【样例输入】

1 2
100 3
100 2
100 1

【样例输出】

1 50004