题目内容

商店一块地面分成 $r$ 行 $c$ 列地砖。行从上到下编号 $1$ 至 $r$，列从左到右编号 $1$ 至 $c$。

有 $m$ 对地砖要各贴一条导购线，按输入顺序编为第 $1$ 对到第 $m$ 对。每对先给起点，再给终点。全部 $2m$ 个端点两两不同。

每条导购线从自己的起点贴到自己的终点，并同时满足：

• 每一步只能走到上下左右相邻的地砖，不能斜着走，也不能走出这块地面；
• 一条导购线不能重复经过同一块地砖；
• 不同导购线不能经过同一块地砖；
• 除自己的起点和终点外，不能经过任何端点；
• 没贴到的地砖可以空着。

一条导购线经过 $t$ 块地砖（含起点和终点）时，长度为 $t-1$。两端相邻时，长度可以是 $1$。总线长是 $m$ 条导购线的长度之和。

求最小总线长。有多种贴法时，只要总线长最小即可。无法同时贴成时，输出 $-1$。

输入描述

第一行三个整数 $r$、$c$、$m$。

接下来 $m$ 行，第 $i$ 行四个整数 $x_1,y_1,x_2,y_2$，表示第 $i$ 对的起点 $(x_1,y_1)$ 和终点 $(x_2,y_2)$。$x$ 是行号，$y$ 是列号。

约束

$1 \le r,c \le 4$

$1 \le m \le 2$

$1 \le x_1,x_2 \le r$

$1 \le y_1,y_2 \le c$

每对的起点和终点不同

$2m$ 个端点两两不同

输出描述

输出一个整数，为最小总线长。无法贴成时输出 $-1$。

样例1

输入

3 4 2
2 1 2 4
2 2 2 3

输出

6

说明

地面有 $3$ 行、$4$ 列。第 $1$ 对连接 $(2,1)$ 与 $(2,4)$，第 $2$ 对连接 $(2,2)$ 与 $(2,3)$。

第 $2$ 对的两端左右相邻，只能直接贴成 $(2,2)\to(2,3)$，长度为 $1$。这两块是端点，第 $1$ 对不能经过，因此不能走 $(2,1)\to(2,2)\to(2,3)\to(2,4)$。

第 $1$ 对从 $(2,1)$ 出发，不能进入 $(2,2)$，只能先到 $(1,1)$ 或 $(3,1)$。

• 先到 $(1,1)$：旁边 $(2,2)$ 是端点，只能沿第 $1$ 行走到 $(1,4)$，再下到终点。路径为 $(2,1)\to(1,1)\to(1,2)\to(1,3)\to(1,4)\to(2,4)$，长度 $5$。
• 先到 $(3,1)$：同样只能贴着第 $3$ 行，路径为 $(2,1)\to(3,1)\to(3,2)\to(3,3)\to(3,4)\to(2,4)$，长度 $5$。

第 $2$ 对换成更长的贴法，$(2,2)$ 和 $(2,3)$ 仍是端点，第 $1$ 对还是过不了第 $2$ 行，总线长只会更大。两种绕行都是 $5+1=6$，最小总线长是 $6$。

样例2

输入

3 3 2
1 2 3 2
2 1 2 3

输出

-1

说明

第 $1$ 对是 $(1,2)$ 与 $(3,2)$，第 $2$ 对是 $(2,1)$ 与 $(2,3)$。四个端点之外只剩 $(1,1)$、$(1,3)$、$(2,2)$、$(3,1)$、$(3,3)$。

$(1,1)$ 只与 $(1,2)$、$(2,1)$ 相邻，而 $(2,1)$ 是第 $2$ 对的端点。第 $1$ 对走进 $(1,1)$ 后只能退回起点。$(1,3)$、$(3,1)$、$(3,3)$ 同样不能作为中间地砖。

第 $1$ 对只剩 $(1,2)\to(2,2)\to(3,2)$，必须占用 $(2,2)$。

此时第 $2$ 对从 $(2,1)$ 出发，相邻的是 $(1,1)$、$(3,1)$ 和已经占用的 $(2,2)$。$(1,1)$ 另一侧是端点 $(1,2)$，$(3,1)$ 另一侧是端点 $(3,2)$。第 $2$ 对到不了 $(2,3)$。

无法同时贴成，输出 $-1$。