한국에서는 청개구리들의 말썽이 가히 믿기 어려울 정도이다.

그도 그럴 것이, 청개구리들은 여러분이 돌보고 있는 논 위를 밤사이에 마구 뛰어 다니면서 벼들을 쓰러뜨리기 때문이다

(이로 인해 농부 창호의 논도 많은 피해를 입었다고 한다).

아침이 되어, 쓰러진 벼들을 파악한 당신은 가장 큰 해를 끼친 청개구리가 남긴 발자취를 파악하고 싶어 한다.

청개구리는 논을 언제나 일직선으로 쭉 뛰어가며, 한 번에 뛰는 간격도 언제나 같다.

논은, 그림 1처럼 모눈의 교점들에 벼가 심어져 있는 구조를 하고 있다.

그리고 문제의 청개구리들은 논 밖에서 논으로 들어와, 일직선으로 팔짝팔짝 뛰어 정확하게 벼만 짓밟고 반대편 논 밖으로 나간다.

그림 2를 참고하라.

그림 3처럼, 여러 청개구리들이 제각기 다른 방향에서부터 논으로 들어와 서로 다른 방향으로 뛰어갈 수 있다.

그리고 개구리에게 밟힌 벼는 쓰러진다. 여러 개구리에게 여러 번 밟히는 벼도 있다.

하지만, 개구리들이 지나간다고 자신의 경로가 그림 3처럼 직선으로 남는 것은 아니다.

우리가 아침이 되어 확인할 수 있는 것은 그림 4처럼, 쓰러진 벼들 뿐이다.

그림 4를 보면, 개구리들이 몇 마리가 와서 어느 방향으로 어느 간격으로 벼를 밟고 갔는지 그 경로를 재현할 수 있다.

단, 벼를 세 포기 이상 밟은 개구리의 경로만 생각하기로 한다.

그리고 이것을 개구리 경로라고 편의상 일컫겠다.

그렇다면, 그림 4의 상황이라면 그림 3과 같은 세 개의 개구리 경로가 있다고 말할 수 있다. (물론 다른 가짓수도 있을 수 있다.)

한편, 첫째 칸에서 수직으로 내려가는 경로는 간격이 4인 개구리 경로일 수도 있지만,

이 경로의 영향을 받은 벼는 두 포기밖에 없기 때문에 고려하지 않는다.

그리고 둘째 줄 셋째 칸(2, 3), 셋째 줄 넷째 칸(3, 4), 여섯째 줄 일곱째(6, 7) 칸을 지나는 경로는 일직선이고 벼가 세 포기가 속해 있지만,

간격이 일정하지 않기 때문에 개구리 경로로 인정하지 않는다.

어떤 개구리 경로에 속하는 선에는, 다른 개구리 경로에 속하는 벼가 있을 수 있다.

예를 들어 위 그림에서 (2, 1), (2, 3), (2, 5), (2, 7)은 개구리 경로인데, 이 선 안에는 (2, 6)처럼 다른 개구리에게 밟힌 벼가 또 있다.

그리고 사실은, 쓰러진 벼 중에는 어느 개구리 경로에도 속하지 않은 벼도 있을 수 있다. 개구리에게 밟힌 벼라고 해서,

모두 다 조건을 만족하는 '개구리 경로'에 속하는 것이 아니기 때문이다.

이번 문제는, 가능한 개구리 경로를 모두 조사하여, 벼를 가장 많이 밟았다고 결론지을 수 있는 개구리 경로를 찾아,

그 경로가 지나게 되는 벼 포기의 수를 출력하는 것이다. 그림 4의 경우, 정답은 7이다.

여섯째 줄부터 가로로 벼 일곱 포기를 모두 밟는 경로가 있기 때문이다.

청개구리 timer 1s memory 128MB

청개구리 1s 128MB