Template Cutting

You are given a rectangular template of width W and height H, along with N parts. Each part is specified by its bottom‐left and top‐right coordinates (x₁, y₁, x₂, y₂). The parts do not overlap and exactly cover the template.

Your task is to cut the template into these parts by performing a series of straight‐line cuts. Each cut must span the entire current subrectangle and may be made either vertically or horizontally.

The cost of a cut is defined as follows:

• A vertical cut (at some x=k) costs the height of the subrectangle, i.e. (y₂ - y₁).
• A horizontal cut (at some y=k) costs the width of the subrectangle, i.e. (x₂ - x₁).

Important: A cut is allowed only if it does not split any part. In other words, you can only perform a cut if for every part completely contained in the current subrectangle, the cut line does not go through the interior of that part.

The problem can be solved using the following recurrence relation: $$ dp(x_1,y_1,x_2,y_2)=\min\Big\{\min_{k=x_1+1}^{x_2-1}\Big\{(y_2-y_1)+dp(x_1,y_1,k,y_2)+dp(k,y_1,x_2,y_2)\Big\}, \\ \min_{k=y_1+1}^{y_2-1}\Big\{(x_2-x_1)+dp(x_1,y_1,x_2,k)+dp(x_1,k,x_2,y_2)\Big\}\Big\} $$ with the base case: if the current subrectangle exactly corresponds to one of the parts, then dp(x₁,y₁,x₂,y₂) = 0.

Output the minimum total cost required to cut the entire template accordingly.

inputFormat

The input is given as follows:

• The first line contains two integers W and H (width and height of the template).
• The second line contains an integer N, the number of parts.
• Then N lines follow, each containing four integers x₁ y₁ x₂ y₂ that represent the coordinates of a part (bottom-left and top-right corners).

outputFormat

Output a single integer, the minimum cost required to cut the template into the given parts.

sample

4 3
1
0 0 4 3

0