题目描述

Today the company has $m$ tasks to complete. The $i-$th task need $x_i$ minutes to complete. Meanwhile, this task has a difficulty level $y_i$. The machine whose level below this task’s level $y_i$ cannot complete this task. If the company completes this task, they will get $(500\times x_i+2\times y_i)$ dollars.

The company has $n$ machines. Each machine has a maximum working time and a level. If the time for the task is more than the maximum working time of the machine, the machine can not complete this task. Each machine can only complete a task one day. Each task can only be completed by one machine.

The company hopes to maximize the number of the tasks which they can complete today. If there are multiple solutions, they hopes to make the money maximum.

输入格式

The input contains several test cases.

The first line contains two integers $N$ and $M$. $N$ is the number of the machines.M is the number of tasks $(1 \leq N \leq 100000, 1\leq M\leq 100000)$.

The following $N$ lines each contains two integers $x_i(0<x_i<1440),y_i(0\leq yi\leq 100)$. $x_i$ is the maximum time the machine can work. $y_i$ is the level of the machine.

The following $M$ lines each contains two integers $x_i(0<x_i<1440),y_i(0\leq y_i\leq 100)$. $x_i$ is the time we need to complete the task. $y_i$ is the level of the task.

输出格式

For each test case, output two integers, the maximum number of the tasks which the company can complete today and the money they will get.

题目大意

【题目描述】

今天公司有 $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$ 是任务的级别。

【输出格式】

对于每个测试用例，输出两个整数，分别是公司今天可以完成的最大任务数量和他们将获得的收益。

翻译来自于：ChatGPT。

1 2 
100 3 
100 2 
100 1

1 50004