Go - Državno

Perica and Jovica have recently found out about the ancient chinese game Go and decided to play a game of it themselves. They liked it so much that they didn't even study all the rules in detail. Instead they're playing on their own, slightly altered, rules.

Perica and Jovica are playing on a board of size N x N. Perica is the white player and his stones are coloured in white, while Jovica has black coloured stones. The players play in turns, and in each turn the player sets one of his stones on an unoccupied field.

Each field is neighbouring no more than four fields - up, down, left and right to it. The fields on the table's edges have three, and the corners have only two neighbouring fields. An unoccupied field which is neighboured to a stone represents one "freedom" of that stone. Two neighbouring stones of the same colour are connected, and all stones that are connected to each other form a single group. Also, the number of empty neighbouring fields of all the stones in a single group represents the freedom of the group. If, after a move is made, some opponent's groups lose all their freedoms, all the stones belonging to that group are being removed. If the stone that got set leads to loss of all freedom for both the opponent's and the player's groups, only the opponent's groups are being removed. However, a move can also lead to removal of one's own stones, if by that move only the freedoms of the player's own groups are lost.

The game got heated up and it's Perica's turn - he is the white player. Perica wants to play such a move that after a white stone is set (and all groups that need to get removed), the difference between the white and black stone amount is as big as possible, i.e. if we mark the amount of white stones with b, and the amount of black stones with [], Perica wants to maximize the value of b - c. Your task is to determine how big will this difference be if Perica plays the most optimal move possible.