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

Difficulty: interview

Starter code:

Solutions:
n,m,k=map(int, input().split())
a = []
check = [0]*m
while k!= 0:
 x1,y1,x2,y2 =map(int,input().split())
 a.append([x1,y1,x2,y2])
 check[y1-1] += 1
 check[y2-1] += 1
 k-= 1
maxi = check.index(max(check))+1
sum = 0
k = 0
for i in range(len(a)):
 x1,y1,x2,y2 = a[i]
 if (y1 > maxi and y2 > maxi) or (y1<maxi and y2 < maxi):
  sum+= abs(y2-y1)*2
  sum += abs(x2-x1)*2
 else:
  if y1 != maxi:
   k = abs(y1-maxi)
   sum+= k*2
  if x1 != x2:
   k = abs(x2-x1)
   sum += k
  if y2 != maxi:
   k = abs(y2-maxi)
   sum+= k*2
print(sum)

n,m,k=map(int, input().split())
a = []
check = [0]*m
while k!= 0:
 x1,y1,x2,y2 =map(int,input().split())
 a.append([x1,y1,x2,y2])
 check[y1-1] += 1
 #check[y2-1] += 1
 k-= 1
maxi = check.index(max(check))+1
sum = 0
k = 0
for i in range(len(a)):
 x1,y1,x2,y2 = a[i]
 if y1 != maxi:
  k = abs(y1-maxi)
  sum+= k*2
 if x1 != x2:
  k = abs(x2-x1)
  sum += k
 if y2 != maxi:
  k = abs(y2-maxi)
  sum+= k*2
print(sum)

n,m,k=map(int, input().split())
a = []
check = [0]*m
while k!= 0:
 x1,y1,x2,y2 =map(int,input().split())
 a.append([x1,y1,x2,y2])
 check[y1-1] += 1
 check[y2-1] += 1
 k-= 1
maxi = check.index(max(check))+1
sum = 0
k = 0
for i in range(len(a)):
 x1,y1,x2,y2 = a[i]
 if y1 != maxi:
  k = abs(y1-maxi)
  sum+= k*2
 if x1 != x2:
  k = abs(x2-x1)
  sum += k
 if y2 != maxi:
  k = abs(y2-maxi)
  sum+= k*2
print(sum)

n,m,k=map(int, input().split())
a = []
check = [0]*m
while k!= 0:
 x1,y1,x2,y2 =map(int,input().split())
 a.append([x1,y1,x2,y2])
 check[y1-1] += 1
 k-= 1
maxi = check.index(max(check))+1
sum = 0
k = 0
for i in range(len(a)):
 x1,y1,x2,y2 = a[i]
 if y1 != maxi:
  k = abs(y1-maxi)
  sum+= k*2
 if x1 != x2:
  k = abs(x2-x1)
  sum += k
 if y2 != maxi:
  k = abs(y2-maxi)
  sum+= k*2
print(sum)

# cook your dish here
N,M,K=list(map(int,input().split()))
l1=[]
d={}
for i in range(K):
 l=list(map(int,input().split()))
 l1.append(l)
 if l[1] in d:
  d[l[1]]=d[l[1]]+l.count(l[1])
 elif l[3] in d:
  d[l[3]]=d[l[3]]+l.count(l[1])
 else:
  d[l[1]]=l.count(l[1])
  d[l[3]]=l.count(l[3])
k=max(d, key=d.get)
s=0
for i in range(K):
 s=s+2*(abs(l1[i][1]-k))+2*(abs(l1[i][3]-k))+(abs(l1[i][0]-l1[i][2]))
print(s)
 


# cook your dish here
import collections
n,m,k=list(map(int,input().split()))
l = [[int(j) for j in input().split()] for i in range(k)]

p=[]
for i in range(k):
 p.append(l[i][1])

f={}

for i in range(len(p)):
 if p[i] in f:
  f[p[i]]+=1
 else:
  f[p[i]]=1

key=0
max=0
for i in list(f.keys()):
 if f[i]>max:
  max=f[i]
  key=i

min=0
for i in range(k):
 min=min+(abs(l[i][1]-key)*2)+(abs(l[i][0]-l[i][2]))+(abs(l[i][3]-key)*2)
 
print(min)
 

















 
 
 
 
 


# cook your dish here
import sys
import statistics 
from statistics import mode
readline = sys.stdin.readline
try:
  
 INF = 10**18+3
 N, M, K = map(int, readline().split())
 Points = [tuple(map(int, readline().split())) for _ in range(K)]
 ABC = [(p[1], p[3], abs(p[0] - p[2])) for p in Points]
 ans = INF
 l=[]
 if K <= 10:
  ans = INF
  for m in range(1, M+1):
   res = 0
   for a, b, c in ABC:
    res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
   ans = min(ans, res)
  print(ans)
 else:
  def horiz():
   ans=0
 
   for a,c,x in ABC:
     max1=0
     lv=1
     dist=[0]*M
     yo=min(a,c)
     y1=max(a,c)
     if (yo-x//4)>1:
      lv=yo-x//4
     up=M
     if (x//4+y1)<up:
      up=x//4+y1
     for j in range(lv,up+1):
      if j < yo:
       dist[j]+=x-4*(yo-j)
      elif j>=yo and j<=y1:
       dist[j]+=x
      else:
       dist[j]+=x-4*(j-y1)
      if dist[j]>dist[max1]:
       max1=j
   return dist[max1]
 

  m = horiz()
  res = 0
  for a, b, c in ABC:
   res += (2*abs(a-b) +2*c)
  print(res-m)
except:
 pass

try:
 a,b,c=list(map(int,input().split()))
 r=0
 for _ in range(c):
  w,x,y,z=list(map(int,input().split()))
  r+=abs(w-y)
  r+=2*abs(x-z)
 print(r)
except:
 pass


import sys
import statistics 
from statistics import mode
readline = sys.stdin.readline
try:
  
 INF = 10**18+3
 N, M, K = map(int, readline().split())
 Points = [tuple(map(int, readline().split())) for _ in range(K)]
 ABC = [(p[1], p[3], abs(p[0] - p[2])) for p in Points]
 ans = INF
 l=[]
 ans = INF
 for m in range(1, M+1):
   res = 0
   for a, b, c in ABC:
    res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
   ans = min(ans, res)
 print(ans)

except:
 pass

import sys
import statistics 
from statistics import mode
readline = sys.stdin.readline
try:
  
 INF = 10**18+3
 N, M, K = map(int, readline().split())
 Points = [tuple(map(int, readline().split())) for _ in range(K)]
 ABC = [(p[1], p[3], abs(p[0] - p[2])) for p in Points]
 ans = INF
 l=[]
 if K <= 10:
  ans = INF
  for m in range(1, M+1):
   res = 0
   for a, b, c in ABC:
    res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
   ans = min(ans, res)
  print(ans)
 else:
  def horiz():
   ans=0
 
   for a,c,x in ABC:
     max1=0
     lv=1
     dist=[0]*M
     yo=min(a,c)
     y1=max(a,c)
     if (yo-x//4)>1:
      lv=yo-x//4
     up=M
     if (x//4+y1)<up:
      up=x//4+y1
     for j in range(lv,up+1):
      if j < yo:
       dist[j]+=x-4*(yo-j)
      elif j>=yo and j<=y1:
       dist[j]+=x
      else:
       dist[j]+=x-4*(j-y1)
      if dist[j]>dist[max1]:
       max1=j
   return dist[max1]
 

  m = horiz()
  res = 0
  for a, b, c in ABC:
   res += (2*abs(a-b) +2*c)
  print(res-m)
except:
 pass

import sys
import statistics 
from statistics import mode
readline = sys.stdin.readline
try:
  
 INF = 10**18+3
 N, M, K = map(int, readline().split())
 Points = [tuple(map(int, readline().split())) for _ in range(K)]
 ABC = [(p[1], p[3], abs(p[0] - p[2])) for p in Points]
 ans = INF
 l=[]
 if K <= 10:
  ans = INF
  for m in range(1, M+1):
   res = 0
   for a, b, c in ABC:
    res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
   ans = min(ans, res)
  print(ans)
 else:
  def horiz():
   ans=0
 
   for yo,y1,x in ABC:
     max1=0
     lv=1
     dist=[0]*M
     if (yo-x//4)>1:
      lv=yo-x//4
     up=M
     if (x//4+y1)<up:
      up=x//4+y1
     for j in range(lv,up+1):
      if j < yo:
       dist[j]+=x-4*(yo-j)
      elif j>=yo and j<=y1:
       dist[j]+=x
      else:
       dist[j]+=x-4*(j-y1)
      if dist[j]>dist[max1]:
       max1=j
   return dist[max1]
 

  m = horiz()
  res = 0
  for a, b, c in ABC:
   res += (2*abs(a-b) +2*c)
  print(res-m)
except:
 pass

import sys
import statistics 
from statistics import mode
readline = sys.stdin.readline
try:
  
 INF = 10**18+3
 N, M, K = map(int, readline().split())
 Points = [tuple(map(int, readline().split())) for _ in range(K)]
 ABC = [(p[1], p[3], abs(p[0] - p[2])) for p in Points]
 ans = INF
 l=[]
 if K <= 10:
  ans = INF
  for m in range(1, M+1):
   res = 0
   for a, b, c in ABC:
    res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
   ans = min(ans, res)
  print(ans)
 else:
  def horiz():
   ans=0
 
   for yo,y1,x in ABC:
     max1=0
     lv=1
     dist=[0]*M
     if (yo-x//4)>1:
      lv=yo-x//4
     up=M
     if (x//4+y1)<up:
      up=x//4+y1
     for j in range(lv,up+1):
      if j < yo:
       dist[j]+=x-4*(yo-j)
      elif j>=yo and j<=y1:
       dist[j]+=x
      else:
       dist[j]+=x-4*(j-y1)
      if dist[j]>dist[max1]:
       max1=j
     return dist[max1]
 

  m = horiz()
  res = 0
  for a, b, c in ABC:
   res += (2*abs(a-b) +2*c)
  print(res-m)
except:
 pass

import sys
import statistics 
from statistics import mode
readline = sys.stdin.readline
try:
  
 INF = 10**18+3
 N, M, K = map(int, readline().split())
 Points = [tuple(map(int, readline().split())) for _ in range(K)]
 ABC = [(p[1], p[3], abs(p[0] - p[2])) for p in Points]
 ans = INF
 l=[]
 if K <= 10:
  ans = INF
  for m in range(1, M+1):
   res = 0
   for a, b, c in ABC:
    res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
   ans = min(ans, res)
  print(ans)
 else:
  def horiz():
   ans=0
 
   for yo,y1,x in ABC:
     max1=0
     lv=1
     dist=[0]*M
     if (yo-x//4)>1:
      lv=yo-x//4
     up=M
     if (x//4+y1)<up:
      up=x//4+y1
     for j in range(lv,up+1):
      if j < yo:
       dist[j]+=x-4*(yo-j)
      elif j>=yo and j<=y1:
       dist[j]+=x
      else:
       dist[j]+=x-4*(j-y1)
      if dist[j]>dist[max1]:
       max1=j
     return dist[max1]
 

  m = horiz()
  res = 0
  for a, b, c in ABC:
   res += (2*abs(a-b) +2*c)
  print(ans-m)
except:
 pass

import sys
import statistics 
from statistics import mode
readline = sys.stdin.readline
try:
  
 INF = 10**18+3
 N, M, K = map(int, readline().split())
 Points = [tuple(map(int, readline().split())) for _ in range(K)]
 ABC = [(p[1], p[3], abs(p[0] - p[2])) for p in Points]
 ans = INF
 l=[]
 if K <= 10:
  ans = INF
  for m in range(1, M+1):
   res = 0
   for a, b, c in ABC:
    res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
   ans = min(ans, res)
  print(ans)
 else:
  def horiz():
   ans=0
 
   for yo,y1,x in ABC:
     max1=0
     lv=1
     dist=[0]*M
     if (yo-x//4)>1:
      lv=yo-x//4
     up=M
     if (x//4+y1)<up:
      up=x//4+y1
     for j in range(lv,up+1):
      if j < yo:
       dist[j]+=x-4*(yo-j)
      elif j>=yo and j<=y1:
       dist[j]+=x
      else:
       dist[j]+=x-4*(j-y1)
      if dist[j]>dist[max1]:
       max1=j
     return max1
 
 
    
  m = horiz()
  res = 0
  for a, b, c in ABC:
   res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
  ans = min(ans, res)
  print(ans)
except:
 pass

import sys
import statistics 
from statistics import mode
readline = sys.stdin.readline
try:
  
 INF = 10**18+3
 N, M, K = map(int, readline().split())
 Points = [tuple(map(int, readline().split())) for _ in range(K)]
 ABC = [(p[1], p[3], abs(p[0] - p[2])) for p in Points]
 ans = INF
 l=[]
 if K <= 10:
  ans = INF
  for m in range(1, M+1):
   res = 0
   for a, b, c in ABC:
    res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
   ans = min(ans, res)
  print(ans)
 else:
  def horiz():
   ans=0
 
   for yo,y1,x in ABC:
     max1=0
     lv=1
     dist=[0]*M
     if (yo-x//4)>1:
      lv=yo-x//4
     up=M
     if (x//4+y1)<up:
      up=x//4+y1
     for j in range(lv,up+1):
      if j < yo:
       dist[j]+=x-4*(yo-j)
      elif j>=yo and j<=y1:
       dist[j]+=x
      else:
       dist[j]+=x-4*(j-y1)
      if dist[j]>dist[max1]:
       max1=j
   return max1
 
 
    
  m = horiz()
  res = 0
  for a, b, c in ABC:
   res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
  ans = min(ans, res)
  print(ans)
except:
 pass

import sys
import statistics 
from statistics import mode
readline = sys.stdin.readline
try:
  
 INF = 10**18+3
 N, M, K = map(int, readline().split())
 Points = [tuple(map(int, readline().split())) for _ in range(K)]
 ABC = [(p[1], p[3], abs(p[0] - p[2])) for p in Points]
 ans = INF
 l=[]
 if K <= 10:
  ans = INF
  for m in range(1, M+1):
   res = 0
   for a, b, c in ABC:
    res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
   ans = min(ans, res)
  print(ans)
 else:
  def horiz():
   ans=0
 
   for yo,y1,x in ABC:
     lv=1
     dist=[0]*M
     if (yo-x//4)>1:
      lv=yo-x//4
     up=M
     if (x//4+y1)<up:
      up=x//4+y1
     for j in range(lv,up+1):
      if j < yo:
       dist[j]+=x-4*(yo-j)
      elif j>=yo and j<=y1:
       dist[j]+=x
      else:
       dist[j]+=x-4*(j-y1)
      if dist[j]>dist[max1]:
       max1=j
   return max1
 
 
    
  m = horiz()
  res = 0
  for a, b, c in ABC:
   res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
  ans = min(ans, res)
  print(ans)
except:
 pass

import sys
import statistics 
from statistics import mode
readline = sys.stdin.readline
INF = 10**18+3
N, M, K = map(int, readline().split())
Points = [tuple(map(int, readline().split())) for _ in range(K)]
ABC = [(p[1], p[3], abs(p[0] - p[2])) for p in Points]
ans = INF
l=[]
if K <= 10:
 ans = INF
 for m in range(1, M+1):
  res = 0
  for a, b, c in ABC:
   res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
  ans = min(ans, res)
 print(ans)
else:
 def horiz():
  ans=0

  for yo,y1,x in ABC:
    lv=1
    dist=[0]*M
    if (yo-x//4)>1:
     lv=yo-x//4
    up=M
    if (x//4+y1)<up:
     up=x//4+y1
    for j in range(lv,up+1):
     if j < yo:
      dist[j]+=x-4*(yo-j)
     elif j>=yo and j<=y1:
      dist[j]+=x
     else:
      dist[j]+=x-4*(j-y1)
     if dist[j]>dist[max1]:
      max1=j
  return max1


   
 m = horiz()
 res = 0
 for a, b, c in ABC:
  res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
 ans = min(ans, res)
 print(ans)

import sys
try:
 n,m,k=list(map(int,sys.stdin.readline().split()))
 xo,yo,x1,y1=[0]*k,[0]*k,[0]*k,[0]*k
 dist=[0]*(m+1)
 max1=0
 for i in range(0,k):
  h1,u1,h2,u2=list(map(int,sys.stdin.readline().split()))
  xo[i]=min(h1,h2)
  x1[i]=max(h1,h2)
  yo[i]=min(u1,u2)
  y1[i]=max(u1,u2)
  lv=1
  x=x1[i]-xo[i]
  if (yo[i]-x//4)>1:
   lv=yo[i]-x//4
  up=m
  if (x//4+y1[i])<up:
   up=x//4+y1[i]
  for j in range(lv,up+1):
   if j < yo[i]:
    dist[j]+=x-4*(yo[i]-j)
   elif j>=yo[i] and j<=y1[i]:
    dist[j]+=x
   else:
    dist[j]+=x-4*(j-y1[i])
   if dist[j]>dist[max1]:
    max1=j
 cost=0
 for i in range(k):
  cost+=2*((x1[i]-xo[i])+(y1[i]-yo[i]))
 print(cost-dist[max1])

except:
 pass








try:
 n,m,k=list(map(int,input().split()))
 xo,yo,x1,y1=[0]*k,[0]*k,[0]*k,[0]*k
 dist=[0]*(m+1)
 max1=0
 cost=0
 for i in range(0,k):
  h1,u1,h2,u2=list(map(int,input().split()))
  xo[i]=min(h1,h2)
  x1[i]=max(h1,h2)
  yo[i]=min(u1,u2)
  y1[i]=max(u1,u2)
 if (min(yo)==max(yo)) or (min(y1)==max(y1)):
  print(sum(x1)-sum(xo)+2*(sum(yo)-sum(y1)))
 else:
  cost=0
  for i in range(k):
   cost+=2*((x1[i]-xo[i])+(y1[i]-yo[i]))
   lv=1
   x=x1[i]-xo[i]
   if (yo[i]-x//4)>1:
    lv=yo[i]-x//4
   up=m
   if (x//4+y1[i])<up:
    up=x//4+y1[i]
   for j in range(lv,up+1):
    if j < yo[i]:
     dist[j]+=x-4*(yo[i]-j)
    elif j>=yo[i] and j<=y1[i]:
     dist[j]+=x
    else:
     dist[j]+=x-4*(j-y1[i])
    if dist[j]>dist[max1]:
     max1=j
  print(cost-dist[max1])

except:
 pass








try:
 n,m,k=list(map(int,input().split()))
 dist=[0]*(m+1)
 max1=0
 cost=0
 for i in range(0,k):
  h1,u1,h2,u2=list(map(int,input().split()))
  xo=min(h1,h2)
  x1=max(h1,h2)
  yo=min(u1,u2)
  y1=max(u1,u2)
  cost+=2*((x1-xo)+(y1-yo))
  lv=1
  x=x1-xo
  if (yo-x//4)>1:
   lv=yo-x//4
  up=m
  if (x//4+y1)<up:
   up=x//4+y1
  for j in range(lv,up+1):
   if j < yo:
    dist[j]+=x-4*(yo-j)
   elif j>=yo and j<=y1:
    dist[j]+=x
   else:
    dist[j]+=x-4*(j-y1)
   if dist[j]>dist[max1]:
    max1=j
 print(cost-dist[max1])

except:
 pass








try:
 n,m,k=list(map(int,input().split()))
 xo,yo,x1,y1=[0]*k,[0]*k,[0]*k,[0]*k
 dist=[0]*(m+1)
 max1=0
 for i in range(0,k):
  h1,u1,h2,u2=list(map(int,input().split()))
  xo[i]=min(h1,h2)
  x1[i]=max(h1,h2)
  yo[i]=min(u1,u2)
  y1[i]=max(u1,u2)
  lv=1
  x=x1[i]-xo[i]
  if (yo[i]-x//4)>1:
   lv=yo[i]-x//4
  up=m
  if (x//4+y1[i])<up:
   up=x//4+y1[i]
  for j in range(lv,up+1):
   if j < yo[i]:
    dist[j]+=x-4*(yo[i]-j)
   elif j>=yo[i] and j<=y1[i]:
    dist[j]+=x
   else:
    dist[j]+=x-4*(j-y1[i])
   if dist[j]>dist[max1]:
    max1=j
 cost=0
 for i in range(k):
  cost+=2*((x1[i]-xo[i])+(y1[i]-yo[i]))
 print(cost-dist[max1])

except:
 pass








import sys
import statistics 
from statistics import mode
readline = sys.stdin.readline
INF = 10**18+3
N, M, K = map(int, readline().split())
Points = [tuple(map(int, readline().split())) for _ in range(K)]
ABC = [(p[1], p[3], abs(p[0] - p[2])) for p in Points]
ans = INF
l=[]
if K <= 10:
 ans = INF
 for m in range(1, M+1):
  res = 0
  for a, b, c in ABC:
   res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
  ans = min(ans, res)
 print(ans)
else:
 def horiz():
  for x,y,z in ABC:
   l.append(x)
   l.append(y)
  return mode(l)
 m = horiz()
 res = 0
 for a, b, c in ABC:
  res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
 ans = min(ans, res)
 print(ans)

import sys
import statistics 
from statistics import mode
readline = sys.stdin.readline
INF = 10**18+3
N, M, K = map(int, readline().split())
Points = [tuple(map(int, readline().split())) for _ in range(K)]
ABC = [(p[1], p[3], abs(p[0] - p[2])) for p in Points]
ans = INF
l=[]
def horiz():
 for x,y,z in ABC:
  l.append(x)
  l.append(y)
 return mode(l)
m = horiz()
res = 0
for a, b, c in ABC:
 res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
ans = min(ans, res)
print(ans)

import sys
readline = sys.stdin.readline
INF = 10**18+3
N, M, K = map(int, readline().split())
Points = [tuple(map(int, readline().split())) for _ in range(K)]
ABC = [(p[1], p[3], abs(p[0] - p[2])) for p in Points]
if K <= 10:
 ans = INF
 for m in range(1, M+1):
  res = 0
  for a, b, c in ABC:
   res += min(2*abs(a-m) + 2*abs(b-m) + c, 2*abs(a-b) + 2*c)
  ans = min(ans, res)
 print(ans)