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$.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'n,m,k=map(int, input().split())\na = []\ncheck = [0]*m\nwhile k!= 0:\n x1,y1,x2,y2 =map(int,input().split())\n a.append([x1,y1,x2,y2])\n check[y1-1] += 1\n check[y2-1] += 1\n k-= 1\nmaxi = check.index(max(check))+1\nsum = 0\nk = 0\nfor i in range(len(a)):\n x1,y1,x2,y2 = a[i]\n if (y1 > maxi and y2 > maxi) or (y1<maxi and y2 < maxi):\n  sum+= abs(y2-y1)*2\n  sum += abs(x2-x1)*2\n else:\n  if y1 != maxi:\n   k = abs(y1-maxi)\n   sum+= k*2\n  if x1 != x2:\n   k = abs(x2-x1)\n   sum += k\n  if y2 != maxi:\n   k = abs(y2-maxi)\n   sum+= k*2\nprint(sum)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13529