Minimum Knights to Checkmate the King

In this problem, you are given an n × m chessboard with a single black king whose position remains fixed. You have an unlimited supply of knights at your disposal. Your task is to place as few knights as possible on the board so that the king is in checkmate. The checkmate condition is defined as follows: For every cell that the king can move to in exactly one move (and which is inside the board), there must exist at least one knight that can reach that cell in exactly one knight move.

Both the king and the knight move according to the standard chess rules. Specifically:

• King: In one move, the king can move one step in any of the eight directions (up, down, left, right, and the four diagonals).
• Knight: A knight moves in an "L" shape. Formally, a knight move can be described by a translation of
  \[ (\pm2,\pm1) \quad \text{or} \quad (\pm1,\pm2), \] where there is no restriction similar to the "knight's leg" rule (i.e. as long as the move stays within the board and follows the L-shaped pattern, it is valid).

The king itself is not under attack; rather, the knights are placed such that every cell the king may move into is attacked by at least one knight in one move.

Input Format: The input consists of four integers n, m, kx, and ky on a single line, where the board has size n × m and the king is located at cell (kx, ky). The board is 1-indexed.

Note: If the king has no valid moves (i.e. no adjacent cell inside the board), the answer is 0. If it is impossible to cover all the king's available moves with legal knight moves, output -1.

inputFormat

The input consists of a single line with four space‐separated integers: n m kx ky.

• n, m (1 ≤ n, m ≤ 10⁹) represent the dimensions of the chessboard.
• kx, ky (1 ≤ kx ≤ n, 1 ≤ ky ≤ m) denote the position of the black king.

outputFormat

Output a single integer representing the minimum number of knights needed to ensure that every cell the king can move to (in one step) is under attack by at least one knight. If it is impossible to cover all such cells, output -1.

sample

1 1 1 1

0