Salmon runs a fish delivery company in Fish City. Fish City has $N$ vertical roads numbered $1, 2, ..., N$ from left to right, each spaced 1 unit apart; similarly, there are $M$ horizontal roads numbered $1, 2, ..., M$ from bottom to top, each spaced 1 unit apart. We will denote the intersection between the $x$-th vertical road and the $y$-th horizontal road as $(x, y)$.
Salmon has to make $K$ deliveries, with the $i$-th delivery starting at $(x_i, y_i)$ and ending at $(x'_i, y'_i)$. He can also travel every road with speed $0.5$ (meaning it would take him $2$ units of time to travel $1$ unit of distance). However, Salmon can bribe the mayor of Fish City and make the mayor change exactly one horizontal road to a highway, meaning the speed on that road would increase to $1$.
He wants to choose a road to be a highway such that the sum of durations of all the deliveries is minimum possible. Help him find this minimum sum!
Note that each delivery starts exactly at $(x_i, y_i)$ and ends at $(x'_i, y'_i)$, i.e., we don't count the time taken to travel from $(x'_{i-1}, y'_{i-1})$ to $(x_i, y_i)$ in our answer.

-----Input:-----
The first line contains 3 integers, $N$, $M$ and $K$ ($1 \le N, M, K \le 10^5$).
The next $K$ lines describe deliveries. Each line contains 4 space-separated integers $x_i$, $y_i$, $x'_i$, $y'_i$ ($1 \le x_i, x'_i \le N$, $1 \le y_i, y'_i \le M$), describing the $i$-th delivery.

-----Output:-----
Print one integer -- the minimum sum of durations possible.

-----Subtasks-----
- Subtask 1 [17 points]: $y_i = y_{i-1}$ for all $i>0$.
- Subtask 2 [34 points]: $K \le 10$.
- Subtask 3 [49 points]: No additional constraints.

-----Sample Input 1:-----
5 4 3
2 3 4 1
1 4 5 2
3 3 5 3

-----Sample Output 1:-----
16

-----Explanation:-----

Salmon can turn the 3rd horizontal road into a highway.
- For the first delivery, we can go 2 units to the right taking 2 units of time, and 2 units down taking 4 units of time. The time taken is $2 + 4 = 6$.
- For the second delivery, we can go 1 unit down taking 2 units of time, 4 units right taking 4 units of time, and 1 unit down taking 2 units of time. The time taken is $2 + 4 + 2 = 8$.
- For the third delivery, we can go 2 units right taking 2 units of time.
Therefore, the total time taken is $6 + 8 + 2 = 16$.

-----Sample Input 2:-----
10 2 3
1 2 10 2
2 1 9 1
4 1 7 1

-----Sample Output 2:-----
23

-----Explanation:-----

Salmon can turn the 1st horizontal road into a highway.
- For the first delivery, we can go 1 unit down taking 2 units of time, 9 units right taking 9 units of time, and 1 unit up taking 2 units of time. The time taken is $2 + 9 + 2 = 13$.
- For the second delivery, we can go 7 units right taking 7 units of time.
- For the third delivery, we can go 3 units to the right taking 3 units of time.
Therefore, the total time taken is $13 + 7 + 3 = 23$.

见题面

见题面