405351: GYM101911 H Theater Square

The Theater Square can be represented as a rectangle having height $$$n$$$ and length $$$m$$$, divided into square $$$1 \times 1$$$ cells. Let's denote the cell located at the intersection of $$$i$$$-th row and $$$j$$$-th column as $$$(i, j)$$$. The rows are numbered from top to bottom, the columns — from left to right.

There is a rectangular fountain inside the Teather Square. The cell in its left upper corner is $$$(x_1, y_1)$$$, the cell in its right lower corner is $$$(x_2, y_2)$$$.

The Theater Square soon will be paved with tiles having height $$$1$$$ and length $$$2$$$. Every cell (except cells inside the fountain) should be paved, and no cell should be covered by more than one tile. All tiles will be laid out horizontally, so the cells covered by each tile are in the same row. To pave the whole Theater Square it might be necessary to break some tiles. After breaking a tile, two new tiles of size $$$1 \times 1$$$ are formed (which cannot be broken further). You may consider that the mayor, who ordered the paving of the Theater Square, has infinite number of tiles $$$1 \times 2$$$.

Since broken tiles are not beautiful, among all possible ways to pave the Theater Square the mayor wants to choose a way such that the number of tiles to be broken into two lesser tiles is minimum possible. Pay attention that tiles should be laid horizontally, no tile can cover cells in different rows.

Help the mayor! Tell him the minimum possible number of tiles to be broken.

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 2 \cdot 10^5)$$$ — the height and the length of the Theater Square, respectively.

The second line contains four numbers $$$x_1, y_1, x_2, y_2 ~ (1 \le x_1 \le x_2 \le n, 1 \le y_1 \le y_2 \le m)$$$ — the coordinates of left upper corner and right lower corner of the fountain.

Print one number — minimum possible number of tiles mayor has to break in order to pave the whole Theater Square.

6 5
1 2 3 4

5

6 1
3 1 4 1

2

1 12
1 3 1 8

0

One of the optimal ways to pave the Theater Square in the first example: