태현이는 1x1 크기의 칸으로 나눠진 WxH 정사각형 판을 가지고 있다. 편의상 판의 행들은 위에서 부터 아래로 0 번 부터 H-1 번으로 번호를 붙이고, 판의 열들은 왼쪽 부터 오른쪽으로 0부터 W-1번의 번호가 붙인다.

각 칸은 최대 한개의 돌을 놓을 수 있으며, 놓인 돌들 모든 돌의 쌍의 거리는 유클리디언 거리로 정확히 2가 되어선 안된다.

두개의 돌이 각각 (x1, y1), (x2, y2)에 놓여있을 경우의 유클리디언 거리는 sqrt( (x1-x2)²+ (y1-y2)² )이다. 여기서 sqrt는 양의 제곱근을 뜻한다.

위의 조건을 만족시킬 때 판에다가 놓을 수 있는 돌의 최대 개수를 출력하라.

돌 놓기 timer 1s memory 32MB

돌 놓기 1s 32MB