Maximum Non-Crossing Bridges

You are given two sets of houses located along two parallel river banks. The houses on the north bank and the houses on the south bank are positioned along the x-axis. Your task is to build as many bridges as possible connecting a house from the north bank to a house on the south bank. However, no two bridges should cross each other.

Formally, you are given two lists of integers: north_coords and south_coords, which represent the x-coordinates of houses on the north bank and the south bank respectively. A bridge connecting north_coords[i] and south_coords[j] is valid if you can arrange these pairs so that they are non-decreasing in both lists. The goal is to compute the maximum number of bridges that can be built under these conditions.

The problem can be mathematically expressed as finding the maximum number of pairs \((i, j)\) such that if the pairs are sorted by the north bank coordinates then their corresponding south bank coordinates are also in non-decreasing order. Use the following latex formulas for clarity:

Let \(N\) be the number of houses on the north bank and \(M\) be the number on the south bank. If the houses are sorted by x-coordinate, we need to find a subsequence of pairs \((north[i], south[j])\) such that:

[ north[i_1] \leq north[i_2] \leq \cdots \leq north[i_k] \quad \text{and} \quad south[j_1] \leq south[j_2] \leq \cdots \leq south[j_k] ]

The maximum length \(k\) is the number of bridges you can build.

inputFormat

The input is read from standard input and consists of two lines:

• The first line starts with an integer \(N\) followed by \(N\) integers representing the x-coordinates of houses on the north bank.
• The second line starts with an integer \(M\) followed by \(M\) integers representing the x-coordinates of houses on the south bank.

All numbers are separated by spaces.

outputFormat

Output a single integer to standard output representing the maximum number of bridges that can be built without any crosses.

## sample

4 1 3 5 7
5 2 4 6 8 10

4