In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Byteasar would fancy a game of checkers, however his chessboard got lost somewhere. He only managed to find a wooden board, sized , divided into equal in size, square fields. Each field is painted either white or black, however the arrangement of the colours on this board not necessarily matches the proper chessboard pattern. In such a case Byteasar has decided to utilise his carpentry experience and with the help of a saw he plans to cut out a chessboard, which is a square consisting of certain number of fields, where two fields sharing sides have alternate colours.
It is not clear whether Byteasar manages to find out a properly sized square on the board. So, he decided to cut out two triangular pieces from the board in order to glue them together in such a way that a chessboard would be created. (The pieces must be separable, however they may be turned around in any way after cutting out). Help Byteasar and calculate the largest chessboard size that he is able to obtain by using this method. The figure below presents the board sized and the two triangles, which could be glued together in order to form chessboard sized :
The first input line contains two integers and (): the board size. The following lines contains integers each: -th number from -th line (, ) describes the colour positioned on the intersection of -th column and -th row of the board. Digit 0 describes white field and digit 1 - black field.
The first and only output line should contain one integer, representing the largest chessboard size, which is obtainable by cutting two triangular pieces from the board and pasting them together.
For the input data:
4 5 1 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0the correct result is:
whereas for the input data:
3 3 1 1 1 1 1 0 0 1 0the correct answer is:
Task author: Tomasz Idziaszek