Harvesting the Farm

A farm has $R$ rows and $C$ columns. There is one crop in each of $N$ distinct cells. The $i$-th crop is in row $Y_i$ and column $X_i$.

A harvesting machine occupies a consecutive segment of rows in one column. Initially, it occupies only the cell in row $S_r$ and column $S_c$. That cell has no crop.

You may perform either of these operations:

• Extend: Add one cell to the top or bottom end of the machine.
• Move: Shift every cell occupied by the machine one column to the left or right.

After an operation, every crop in a cell occupied by the machine is harvested immediately. No part of the machine may leave the farm during an operation.

Find the minimum number of operations needed to harvest every crop.

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$R\ C$ $S_r\ S_c$ $N$ $Y_1\ X_1$ $Y_2\ X_2$ $\vdots$ $Y_N\ X_N$

$T$ is the number of test cases. Each case gives the farm dimensions, the machine’s initial cell, the number of crops, and the position of each crop.

For each test case, print the minimum number of operations on one line.

• $1 \leq T \leq 50\,000$.
• $1 \leq R$, $1 \leq C$, $2 \leq R\cdot C \leq 100\,000$.
• $1 \leq S_r \leq R$, $1 \leq S_c \leq C$.
• $1 \leq N \leq R\cdot C-1$.
• $1 \leq Y_i \leq R$, $1 \leq X_i \leq C$ ($1 \leq i \leq N$).
• There is no crop in the machine’s initial cell.
• All crop positions are distinct.
• The sum of $N$ over all test cases is at most $100\,000$.