The squirrel nation is preparing for quarantine! There are $N$ hungry squirrels that need to be fed. The exact amount of acorns that each squirrel consumes varies, but it is known that the $i^{th}$ squirrel will eat between $a_i$ and $b_i$ acorns during quarantine.

Before the quarantine begins, there are $M$ magical trees that will produce acorns that the squirrels can collect. The exact amount of acorns produced is also unknown due to seasonal fluctuations, but it is known that the $j^{th}$ tree will produce between $e_j$ and $f_j$ acorns before the quarantine begins. They will never produce an amount of acorns outside of this range.

Each squirrel will visit some of the trees and bring some of the acorns back to their home. The $i^{th}$ squirrel will collect at least $c_{ij}$ and at most $d_{ij}$ acorns from the $j^{th}$ tree. They will never collect an amount of acorns outside of this range. Obviously the total number of acorns taken from a tree cannot exceed the number of acorns that tree produces. In addition, squirrels do not like to waste food, so no acorns can be left on the trees before the quarantine begins, and no squirrel will bring home more acorns than they eat.

After the quarantine ends, Carson has been tasked with the job of collecting all the shells of the eaten acorns. Carson does not like working so he wants to determine both the minimum and maximum number of acorn shells that he will need to collect, over all possibilities where all squirrels survive the quarantine without wasting any food. The $i^{th}$ squirrel will survive the quarantine only if they eat between $a_i$ and $b_i$ acorns, and collect between $c_{ij}$ and $d_{ij}$ acorns from the $j^{th}$ tree. Food is wasted if there are acorns left on the trees or if there are uneaten acorns in any squirrel's home.

Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

$1\le N,M\le 500$
$0\le a_i\le b_i\le {10}^9$ for all $1\le i\le N$
$0\le c_{ij}\le d_{ij}\le {10}^9$ for all $1\le i\le N$ and $1\le j\le M$
$0\le e_j\le f_j\le {10}^9$ for all $1\le j\le M$

Subtask 1 [39%]

$a_i=0$ for all $1\le i\le N$
$c_{ij}=0$ for all $1\le i\le N$ and $1\le j\le M$
$e_j=0$ for all $1\le j\le M$

Subtask 2 [61%]

Partial points can be earned based on the number of correct lines in your output. Please see the output specification section for more details.

No additional constraints.

Input Specification

The first line of input contains $2$ integers, $N$ and $M$, representing the number of squirrels in the squirrel nation, and the number of magical trees producing acorns.

The next $N$ lines describe the number of acorns each squirrel will eat. The $i^{th}$ line contains $2$ integers, $a_i$, $b_i$, indicating that the $i^{th}$ squirrel will eat between $a_i$ and $b_i$ acorns during the quarantine.

The next $N$ lines describe the minimum number of acorns each squirrel will collect from each tree. Each line contains $M$ integers. The $j^{th}$ integer on the $i^{th}$ line is $c_{ij}$ indicating that the $i^{th}$ squirrel will collect at least $c_{ij}$ acorns from the $j^{th}$ tree.

The next $N$ lines describe the maximum number of acorns each squirrel will collect from each tree. Each line contains $M$ integers. The $j^{th}$ integer on the $i^{th}$ line is $d_{ij}$ indicating that the $i^{th}$ squirrel will collect at most $d_{ij}$ acorns from the $j^{th}$ tree.

The next $M$ lines describe the number of acorns each tree produces before the quarantine. The $j^{th}$ line contains $2$ integers, $e_j$, $f_j$, indicating that the $j^{th}$ tree will produce between $e_j$ and $f_j$ acorns before the quarantine.

Output Specification

This problem is graded with a custom checker. As usual, ensure that every line of output is terminated with a \n character and that there are no trailing spaces. This problem will NOT notify you if you have a presentation error.

If there is no way for all squirrels to survive the quarantine without wasting any food, output -1 and only -1 on a single line.

Otherwise, output two integers each on their own line. The first integer should be the minimum number of acorn shells that Carson will have to collect after the quarantine. The second integer should be the maximum number of acorn shells that Carson will have to collect after the quarantine.

For the test cases in the first subtask, you will receive $39$ points if all lines of output match the expected output correctly. Otherwise, you will receive $0$ points.

For the test cases in the second subtask, you will earn points only if you received $39$ points on the first subtask. If all lines of output match the expected output, you will receive $61$ additional points. If none of the lines of output match the expected output or if the number of lines of output is incorrect, you will receive $0$ additional points. Otherwise, you will receive $30$ additional points.

Your score for a subtask is equal to the minimum number of points earned for any case in that subtask.

Sample Input 1

3 2
0 1
0 4
0 0
0 0
0 0
0 0
2 0
1 3
0 1
0 3
0 2

Sample Output 1

0
4

Sample Explanation 1

There are $3$ squirrels and $2$ trees.

In this example, Carson will not have to collect any acorns if no squirrels eat any acorns, no matter how many acorns are produced.

Carson could have to collect $4$ acorns if the following occurs:

• tree $1$ produces $2$ acorns
• tree $2$ produces $2$ acorns
• squirrel $1$ collects $1$ acorn from tree $1$, and eats $1$ acorn
• squirrel $2$ collects $1$ acorn from tree $1$, $2$ acorns from tree $2$, and eats $3$ acorns
• squirrel $3$ does not collect any acorns

Sample Input 2

2 2
3 4
0 1
0 0
0 0
1 1
1 1
1 2
1 2

Sample Output 2

-1

Sample Explanation 2

While squirrel $2$ can survive the quarantine without eating any acorns, there is no way for squirrel $1$ to eat at least $3$ acorns.

Sample Input 3

2 3
4 6
1 2
2 2 0
0 0 0
2 3 0
0 1 4
1 2
2 4
1 2

Sample Output 3

5
7

Sample Explanation 3

There are $2$ squirrels and $3$ trees.

Carson could only have to collect $5$ acorns if the following occurs:

• tree $1$ produces $2$ acorns, tree $2$ produces $2$ acorns, tree $3$ produces $1$ acorn
• squirrel $1$ collects $2$ acorns from tree $1$, $2$ acorns from tree $2$, and eats $4$ acorns
• squirrel $2$ collects $1$ acorn from tree $3$, and eats $1$ acorn

Carson could have to collect $7$ acorns if the following occurs:

• tree $1$ produces $2$ acorns, tree $2$ produces $3$ acorns, tree $3$ produces $2$ acorns
• squirrel $1$ collects $2$ acorns from tree $1$, $3$ acorns from tree $2$, and eats $5$ acorns
• squirrel $2$ collects $2$ acorns from tree $3$, and eats $2$ acorns

Sample Input 4

2 2
0 1
0 1
0 1
0 0
1 1
0 1
0 1
0 1

Sample Output 4

1
1

Sample Explanation 4

There are $2$ squirrels and $2$ trees.

Carson will always have to collect $1$ acorn over all possibilities where the squirrels survive the quarantine. Trees $2$ will always produce $1$ acorn, and squirrel $1$ will always eat that acorn. All other combinations lead to the squirrels not surviving the quarantine or food being wasted.