Background

$\small\color{white}/10^{\text{th}}\text{Problem by AtC}.$

In this problem, the line connecting two points is considered to be the line segment with these two points as endpoints.

Problem Description

$\text{BiOI}$ has a grid with $n$ rows and $m$ columns. You need to choose as few lattice points as possible so that, for any two distinct lattice points, the line segment connecting them passes through at least one chosen point (here we consider that a segment passes through its two endpoints).

$\text{CmOI}$ thinks this problem is too easy, so he additionally gives $a, b, x$, meaning that the lattice point at row $a$, column $b$ must be chosen or must not be chosen:

• When $x = 0$, this lattice point cannot be chosen.
• When $x = 1$, this lattice point must be chosen.

You only need to output the minimum number of lattice points to choose. $\text{BiOI}$ and $\text{CmOI}$ will give the grid and your answer to $\text{ArCu}$ so that he can construct an actual selection.

Input Format

The first line contains two integers $n, m$.

The second line contains three integers $a, b, x$.

Output Format

Output one integer in one line, the minimum number of lattice points that need to be chosen.

3 3
2 2 1

5

2 5
1 3 0

7

4 5
3 2 0

16

Hint

$\text{Details about Subtasks}:$

All testdata satisfy $1 \le n, m < 2^{32}$, $1 \le a \le n$, $1 \le b \le m$, $0 \le x \le 1$.

• $\text{Subtask 1}: 1 \le n, m \le 10, \text{5 points.}$
• $\text{Subtask 2}: x = 0, \text{25 points}.$
• $\text{Subtask 3}: x = 1, \text{30 points.}$
• $\text{Subtask 4}: \text{40 points.}$

$\text{Sample Explanation}:$

• $\text{Sample 1}:$

The grid has $3$ rows and $3$ columns, and the lattice point at row $2$, column $2$ must be chosen.

An optimal solution is as follows (black points are chosen lattice points):

Note that the following solutions are not valid:

• The figure shows two ways where the segment between two distinct lattice points does not pass through any black point.
• The lattice point at row $2$, column $2$ is not chosen, but the input requires this point to be chosen.

Also, we consider that having an endpoint on a black point counts as passing through a black point. That is, the following segment passes through a black lattice point.

Translated by ChatGPT 5