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: UNKNOWN_DIFFICULTY

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) = 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)


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)


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


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
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)