Task Assignment Profit Maximization

Today the company has \( m \) tasks to complete. The \( i\)-th task requires \( x_i \) minutes to complete and has a difficulty level \( y_i \). A machine whose level is below \( y_i \) cannot complete the task. If the company completes the task, they earn \(500\times x_i + 2\times y_i\) dollars.

The company also has \( n \) machines. Each machine is characterized by its maximum working time and its level. A machine can perform a task only if its maximum working time is at least the task's required time and its level is at least the task’s difficulty level. Each machine can complete at most one task per day and each task can be completed by at most one machine.

The goal is to maximize the number of tasks completed. If there are multiple ways to achieve the maximum number of tasks, choose the assignment that maximizes the total revenue.

Input: The first line contains two integers \( m \) and \( n \). The next \( m \) lines each contain two integers \( x_i \) and \( y_i \), describing the tasks. The following \( n \) lines each contain two integers representing a machine's maximum working time and its level.

Output: Print two integers: the maximum number of tasks that can be completed and the maximum total revenue earned.

inputFormat

The input begins with a line containing two integers \( m \) and \( n \) where \( m \) is the number of tasks and \( n \) is the number of machines. The following \( m \) lines each contain two integers \( x_i \) and \( y_i \), representing the time required and difficulty level of the \( i\)-th task. Then, there are \( n \) lines each containing two integers: the maximum working time and the level of a machine.

outputFormat

Output two integers separated by a space. The first integer is the maximum count of tasks that can be completed and the second integer is the maximum total revenue earned, where the revenue for completing the \( i\)-th task is \(500 \times x_i + 2 \times y_i\).

sample

3 2
10 5
4 20
6 6
10 6
6 20

2 8022