Reminder: in case of any technical issues, you can use the lightweight website
m1.codeforces.com,
m2.codeforces.com,
m3.codeforces.com.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Matchmaker

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarpus has *n* markers and *m* marker caps. Each marker is described by two numbers: *x*_{i} is the color and *y*_{i} is the diameter. Correspondingly, each cap is described by two numbers: *a*_{j} is the color and *b*_{j} is the diameter. Cap (*a*_{j}, *b*_{j}) can close marker (*x*_{i}, *y*_{i}) only if their diameters match, that is, *b*_{j} = *y*_{i}. Besides, a marker is considered to be beautifully closed, if the cap color and the marker color match, that is, *a*_{j} = *x*_{i}.

Find the way to close the maximum number of markers. If there are several such ways, then choose the one that has the maximum number of beautifully closed markers.

Input

The first input line contains two space-separated integers *n* and *m* (1 ≤ *n*, *m* ≤ 10^{5}) — the number of markers and the number of caps, correspondingly.

Next *n* lines describe the markers. The *i*-th line contains two space-separated integers *x*_{i}, *y*_{i} (1 ≤ *x*_{i}, *y*_{i} ≤ 1000) — the *i*-th marker's color and diameter, correspondingly.

Next *m* lines describe the caps. The *j*-th line contains two space-separated integers *a*_{j}, *b*_{j} (1 ≤ *a*_{j}, *b*_{j} ≤ 1000) — the color and diameter of the *j*-th cap, correspondingly.

Output

Print two space-separated integers *u*, *v*, where *u* is the number of closed markers and *v* is the number of beautifully closed markers in the sought optimal way. Remember that you have to find the way to close the maximum number of markers, and if there are several such ways, you should choose the one where the number of beautifully closed markers is maximum.

Examples

Input

3 4

1 2

3 4

2 4

5 4

2 4

1 1

1 2

Output

3 2

Input

2 2

1 2

2 1

3 4

5 1

Output

1 0

Note

In the first test sample the first marker should be closed by the fourth cap, the second marker should be closed by the first cap and the third marker should be closed by the second cap. Thus, three markers will be closed, and two of them will be beautifully closed — the first and the third markers.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/17/2019 02:12:40 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|