Rasta and Kheshtak
Practice
2.5 (72 votes)
Binary search
Hash maps
Medium
Open
Sorting
Problem
83% Success 2020 Attempts 30 Points 2s Time Limit 256MB Memory 1024 KB Max Code

See Russian translation

Rasta is a big fan of Kheshtaks. A Kheshtak is a rectangle that in each of it cells there is an integer.

Today rasta came up with an interesting problem, Biggest Common Subsquare (BCS). A Kheshtak is called a Square if the number of its columns is equal to the number of its rows. A Square S is called a subsqaue of a Kheshtak A if and only if we can turn A to S by deleting some of its rows and some of its columns (maybe none).

He gives you two Kheshtaks, A and B (A one is n × m and B is x × y).

Input format

The first line of input contains n and m.

Then you are given A (n lines, in each line there are m space separated integers).

After that you are given x and y.

Then you are given B (x lines, in each line there are y space separated integers).

1 ≤ n, m, x, y ≤ 700 and all numbers in A and B are integers in the interval [1, 1000].

Output format

Print the size of BCS of A and B in a single line (size of a Square is number of its rows).

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
17 votes
Tags:
ApprovedBinary SearchImplementationMediumOpenSorting
Points:30
8 votes
Tags:
Binary SearchAlgorithmsGreedy Algorithms
Points:30
53 votes
Tags:
Matrix ExponentiationMedium