CCCGuide

Problem S5: On the Fence

2026 · S5 · Original problem · DMOJ

Problem Description

You recently inherited a beautiful plot of land, which can be viewed as a grid with NN rows and MM columns. Now you want to protect your land from trespassers by building a giant fence on it. You will build this fence by choosing up to KK grid cells and filling each of them with a concrete block; these cells are on the fence. Due to mysterious construction laws, the cell in row RR and column CC must be on the fence. Also, the fence cells must form a single connected component—you should be able to get between any two cells on the fence by moving vertically or horizontally (not diagonally) through fence cells only.

The cells in row 11, column 11, row NN, and column MM are called edge cells. A cell not on the fence is outside the fence if you can get from that cell to an edge cell by moving vertically, horizontally, or diagonally, without going through any fence cells. Otherwise, the cell is inside the fence. The figure below shows some examples of valid and invalid fences.

A 5 by 5 grid with each cell coloured either black or white and the centre cell labelled (R,C). All cells in the first column, fourth column, and bottom row are black. In the middle row, the third and fifth cells are also black.

This is a valid fence made of 1717 blocks, with 55 inside cells.

A 5 by 5 grid with each cell coloured either black or white and the centre cell labelled (R,C). In the 2 by 2 sub-grid in the top-right corner, all 4 cells are black. Also, in the 3 by 3 sub-grid in the bottom-left corner, the 8 cells forming the perimeter are black.

This fence is invalid because it is not connected.

A 5 by 5 grid with each cell coloured either black or white and the centre cell labelled (R,C). All cells in the first column, fourth column, and bottom row are black except for the last two cells in the bottom row. Also, the centre square of the grid is black.

This fence is valid, but it encloses zero inside cells.

You want to protect as much of your land as possible. Find the largest number of inside cells you can enclose within your fence.

Input Specification

The first line of input contains an integer TT, the number of test cases in the input.

The next TT lines each contain a test case, consisting of five space-separated integers: NN, MM, KK, RR, and CC (1≤K≤NM, 1≤R≤N, 1≤C≤M)(1 \le K \le NM,~ 1 \le R \le N,~ 1 \le C \le M).

The table on the next page shows how the available 1515 marks are distributed.

MarksBounds on TTBounds on NN, MMAdditional Constraints
11T≤1000T \le 10001≤N,M≤1091 \le N,M \le 10^9K=NMK=NM
22T≤10T \le 101≤N,M≤61 \le N,M \le 6None
22T≤10T \le 101≤N,M≤401 \le N,M \le 40None
22T≤10T \le 101≤N,M≤3001 \le N,M \le 300None
22T≤10T \le 101≤N,M≤2 0001 \le N,M \le 2\,000None
33T≤10T \le 101≤N,M≤1061 \le N,M \le 10^6None
33T≤1000T \le 10001≤N,M≤1091 \le N,M \le 10^9None

Output Specification

Output TT lines. The tt-th line should contain a single integer, the answer to test case tt.

Sample Input

2
5 6 12 3 4
3 6 18 2 4

Output for Sample Input

4
3

Explanation of Output for Sample Input

Below are optimal fences for the two test cases, which enclose 44 and 33 inside cells, respectively:

A 5 by 6 grid with each cell coloured either black or white and the fourth cell in the middle row labelled (R,C). In the 4 by 4 grid in the top-left corner, the 12 cells forming the perimeter are black.

A 3 by 6 grid with each cell coloured either black or white and the fourth cell in the middle row labelled (R,C). All cells in the top and bottom rows are black. In the middle row, the first, fourth, and last cells are black.