가로 줄과 세로 줄의 개수가 각각 N 인 바둑판 모양이 있다. 여기에서 인접한 두 가로줄 또는 두 세로줄 사이의 거리는 1이다.
또한, 가로줄과 세로줄이 만나서 생기는 교차점은 왼쪽에서 x번째 세로줄과 아래쪽에서 y번째 가로줄의 교차점일 때, (x,y)로 나타낸다.
그러면, 제일 왼쪽, 제일 아래쪽 교차점을 S라 하고, (1,1)로 나타낸다.
예를 들어, N=5인 경우에 바둑판 모양은 위와 같고, 교차점 A와 B는 각각 (2,3)와 (4,2)로 나타낸다.
이제 하나의 철사를 다음 규칙에 따라서 바둑판 모양에 놓는다.
(1) 철사는 바둑판 모양의 가로줄과 세로줄 위에만 놓인다.
(2) 철사는 바둑판 모양의 가로줄과 세로줄의 교차점에서만 직각으로 꺾일 수 있다.
(3) 철사는 겹쳐서 놓일 수 있다.
(4) 철사의 시작점과 끝점은 모두 이고 이들은 (용접하여) 붙여져 있다.
예를 들어, N=5인 위 그림 모양의 바둑판에서 철사를 S=(1,1)에서 시작해서 순서대로 교차점 (3,1),(3,4),(2,4),(2,3),(4,3),(4,5)(1,5)에서 꺾어서S=(1,1)에 연결 할 수 있다.
철사가 놓여 지면 세로줄과 평행한 직선으로 바둑판 모양을 자른다.
그러면 철사는 이 직선에 의해 여러 조각들로 나누어질 수 있다. 이 직선은 인접한 두 세로줄 사이를 정확히 가운데로 지나고,
철사를 반드시 2개 이상의 조각으로 나눈다고 가정한다.
위 규칙들을 만족하게 놓여 진 철사와 자르는 직선이 주어지면,
이 직선에 의해 나누어진 철사 조각들 중에서 가장 긴 조각의 길이를 찾는 프로그램을 작성하시오.
예를 들어, 아래 그림과 같이 위의 예에서 놓여진 철사에 대해서 2번째 세로줄과 3번째 세로줄 사이를 지나는 직선으로 나누어진 철사 조각들 중에서 가장 긴 부분의 길이는 7이다.
