CodeEff/ECCO huggingface dataset:
# Original solution
from collections import Counter

N = int(eval(input()))
counter = Counter(list(map(int, input().split())))

sum = 0

for a, cnt in counter.most_common():
    if a > cnt:
        sum += cnt
    else:
        sum += cnt - a

print(sum)


# Optimized solution
from collections import Counter

N = int(eval(input()))
counter = Counter(list(map(int, input().split())))

sum = 0

for a, cnt in list(counter.items()):
    if a > cnt:
        sum += cnt
    else:
        sum += cnt - a

print(sum)
# Original solution
n = int(eval(input())) 
A = [int(i) for i in input().split()] 

setA = list(set(A))

d = {a: A.count(a) for a in setA}


#print(d)
r = 0
for k, v in list(d.items()):
    if v > k:
        r += v - k
    elif k > v:
      	r += v

print(r)

# Optimized solution
n = int(eval(input())) 
A = [int(i) for i in input().split()] 

r = 0
d = {}
pass_list = []
for a in A:
    if a in pass_list:
        r += 1
        continue
    r += 1
    if a in d:
        d[a] += 1
        if d[a] == a:
            r -= a
            pass_list.append(a)
    else:
        d[a] = 1
        if d[a] == a:
          r -= a
          pass_list.append(a)

print(r)
# Original solution
N = int(eval(input()))
a = [int(i) for i in input().split()]
a.sort()
a_key = list(set(a))
ans = 0
for num in a_key:
    if a.count(num) < num:
        ans += a.count(num)
    else:
        ans += a.count(num) - num
print(ans)

# Optimized solution
N = int(eval(input()))
a = [int(i) for i in input().split()]
b = [0] * (N + 1)
ans = 0
for i in range(N):
    if a[i] <= N:
        b[a[i]] += 1
    else:
        ans += 1

for i in range(N + 1):
    if b[i] < i:
        ans += b[i]
    else:
        ans+= b[i] - i
print(ans)
# Original solution
N = int(eval(input()))
A = sorted(list(map(int, input().split())))
ans = 0
for a in A[::-1]:
    if A.count(a) != a:
        A.remove(a)
        ans += 1
print(ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
B = set(A)

result = {}
for b in B:
    result[b] = 0
for a in A:
    result[a] += 1

count = N
for b in B:
    if result[b] >= b:
        count -= b

print(count)
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))
a.sort()
count = 1
ans = 0
for i in range(1,n):
    if a[i] != a[i-1]:
        if a[i-1] < count:
            ans += count - a[i-1]
        elif a[i-1] > count:
            ans += count
        count = 1
    else:
        count+=1
if a[n-1] < count:
    ans += count - a[n-1]
elif a[n-1] > count:
    ans += count
print(ans)

# Optimized solution
n = int(eval(input()))
a = list(map(int,input().split()))
a.sort()
count = 1
ans = 0
for i in range(n-1):
    if a[i+1] != a[i]:
        if count >= a[i]:
            ans += count-a[i]
        else:
            ans += count
        count = 1
    else:
        count+=1
if count >= a[-1]:
    ans += count-a[-1]
else:
    ans += count
print(ans)
# Original solution
N = int(eval(input()))
A = [int(i) for i in input().split()]
a = A.count
cnt = 0
for i in set(A):
  if i < a(i):
    cnt += a(i)-i
  elif i > a(i):
    cnt += a(i)
print(cnt)

# Optimized solution
N = int(eval(input()))
A = sorted(int(i) for i in input().split())+[0]
cnt, ans = 0, 0
a = A[0]
for i in range(len(A)):
  if a == A[i]:
    cnt += 1
  elif a != A[i]:
    if cnt < a:
      ans += cnt
    elif cnt > a:
      ans += cnt-a
    a = A[i]
    cnt = 1
print(ans)
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
a=sorted(a)
b=list(set(a))
ans=0
for i in range(len(b)):
  if a.count(b[i])>=b[i]:
    ans+=a.count(b[i])-b[i]
  else:
    ans+=a.count(b[i])
print(ans)

# Optimized solution
N=int(eval(input()))
a=list(map(int,input().split()))

a=sorted(a)
l=a[0]
cnt=0

b=[]
for i in range(N):
    if a[i]==l:
        cnt+=1
    else:
        b.append([l,cnt])
        l=a[i]
        cnt=1
if cnt>0:
    b.append([l,cnt])

ans=0
for i in range(len(b)):
    if b[i][0]>b[i][1]:
        ans+=b[i][1]
    else:
        ans+=b[i][1]-b[i][0]

print(ans)
# Original solution
from collections import Counter

n = int(eval(input()))
a = list(map(int,input().split()))
ac = Counter(a)
an = len(ac)

cnt = 0
for i in range(an):
  num, count = ac.most_common()[i]
  if count > num:
    cnt += count - num
  elif count < num:
    cnt += count

print(cnt)

# Optimized solution
from collections import Counter

n = int(eval(input()))
a = list(map(int,input().split()))
ac = Counter(a)
an = len(ac)
a_mostcommon = ac.most_common()
cnt = 0
for i in range(an):
  num, count = a_mostcommon[i]
  if count > num:
    cnt += count - num
  elif count < num:
    cnt += count

print(cnt)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
ans = 0

set_A = set(A)

for num in set_A:
    count_num = A.count(num)

    #望ましい数より大きい場合
    if count_num >= num:
        ans += count_num - num
    #望ましい数より小さい場合は0まで削る。
    else:
        ans += count_num

print(ans)


# Optimized solution
N = int(eval(input()))
A = sorted(list(map(int, input().split())))
ans = 0
before_num = A[0]
num_count = 1
A.append(-1)#一番大きい数を計算するとき用

for num in A[1:]:
    if num == before_num:
        num_count += 1
    else:
        if num_count >= before_num:
            ans += num_count - before_num
        else:
            ans += num_count
        num_count = 1
        before_num = num

print(ans)
# Original solution
# Good Sequence
n = int(eval(input()))
a = list(map(int, input().split()))
a_ = set(a)
p = 0
for i in a_:
    if a.count(i) < i:
        p += a.count(i)
    elif a.count(i) > i:
        p += a.count(i) - i
print(p)


# Optimized solution
# Good Sequence
n = int(eval(input()))
a = list(map(int, input().split()))
count = {}
ans = 0
for i in a:
    if i not in count:
        count[i] = 1
    else:
        count[i] += 1
for i, c in list(count.items()):
    if i > c:
        ans += c
    elif i < c:
        ans += c - i
print(ans)
# Original solution
from collections import defaultdict


def dfs(v):
    global ret
    if ret:
        return
    if v == 2:
        if len(used) == cnt:
            ret = True
        return
    for idx, u in enumerate(edges[v]):
        tmp = tuple(sorted((u, v)) + [idx])
        if tmp in used:
            continue
        used.add(tmp)
        dfs(u)
        used.discard(tmp)

while 1:
    edges = defaultdict(list)
    cnt = 0
    try:
        a, b = list(map(int, input().split()))
        edges[a].append(b)
        edges[b].append(a)
        cnt += 1
    except EOFError:
        break
    while 1:
        a, b = list(map(int, input().split()))
        if a == b == 0:
            break
        edges[a].append(b)
        edges[b].append(a)
        cnt += 1
    stack = []
    ret = False
    used = set()
    dfs(1)
    if ret:
        print("OK")
    else:
        print("NG")

# Optimized solution
while 1:
    edges = [0] * 101
    try:
        a, b = list(map(int, input().split()))
        edges[a] += 1
        edges[b] += 1
    except EOFError:
        break
    while 1:
        a, b = list(map(int, input().split()))
        if a == b == 0:
            break
        edges[a] += 1
        edges[b] += 1
    if edges[1] % 2 and edges[2] % 2 and all([a % 2 == 0 for a in edges[3:]]):
        print("OK")
    else:
        print("NG")
# Original solution
x=int(input())
x-=1
ans=6
for i in range(x):
    ans=ans+ans+2
print(ans)


# Optimized solution
x=int(input())
ans=2
for i in range(x):
    ans=ans+ans+2
print(ans)
# Original solution
from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(eval(input()))
edge = [[] for _ in range(n)]
mat = [[1000] * n for _ in range(n)]
for i in range(n):
    s = input().rstrip()
    for j, ch in enumerate(s):
        if ch == "1":
            mat[i][j] = 1
            if j > i:
                edge[i].append(j)
                edge[j].append(i)
for i in range(n):
    mat[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])

ans = 0
dq = deque()
dist = [-1] * n
dq.append((i, 0))
ok = True
while dq:
    v, d = dq.popleft()
    if dist[v] == -1:
        dist[v] = d
    elif dist[v] != d:
        ok = False
        break
    for item in edge[v]:
        if dist[item] == -1:
            dq.append((item, d+1))

if ok:
    ans = 0
    for line in mat:
        ans = max(ans, max(line))
    print((ans + 1))
else:
    print((-1))

# Optimized solution
from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(eval(input()))
edge = [[] for _ in range(n)]
mat = [[1000] * n for _ in range(n)]
for i in range(n):
    s = input().rstrip()
    for j, ch in enumerate(s):
        if ch == "1":
            mat[i][j] = 1
            if j > i:
                edge[i].append(j)
                edge[j].append(i)
for i in range(n):
    mat[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])

ans = 0
dq = deque()
dist = [-1] * n
dq.append((0, 0))
ok = True
while dq:
    v, d = dq.popleft()
    if dist[v] == d:
        continue
    if dist[v] == -1:
        dist[v] = d
    else:
        ok = False
        break
    for item in edge[v]:
        if dist[item] == -1:
            dq.append((item, d+1))

if ok:
    ans = 0
    for line in mat:
        ans = max(ans, max(line))
    print((ans + 1))
else:
    print((-1))
# Original solution
# AGC039B - Graph Partition
from collections import deque


def is_bipartite() -> bool:
    stack = [(1, 1)]
    color = [-1] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = cur_color ^ 1
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if color[u] == -1:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(start) -> int:
    que = deque([start])
    dist = [0] * (N + 1)  # dist[i] := distance from V_start to V_i
    dist[start] = 1
    while que:
        v = que.popleft()
        cur = dist[v]
        for u in E[v]:
            if not dist[u]:
                dist[u] = cur + 1
                que.append(u)
    return max(dist)


def main():
    # if bipartite graph -> diameter of the graph + 1
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1))
        print(ans)
    else:
        print((-1))


if __name__ == "__main__":
    main()

# Optimized solution
# AGC039B - Graph Partition (156ms)
from collections import deque


def is_bipartite() -> bool:
    stack = [(1, 1)]
    color = [0] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = -cur_color
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if not color[u]:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(start) -> int:
    que = deque([start])
    dist = [0] * (N + 1)  # dist[i] := distance from V_start to V_i
    dist[start] = 1
    while que:
        v = que.popleft()
        cur = dist[v]
        for u in E[v]:
            if not dist[u]:
                dist[u] = cur + 1
                que.append(u)
    return max(dist)


def main():
    # if bipartite graph -> diameter of the graph + 1
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1))
        print(ans)
    else:
        print((-1))


if __name__ == "__main__":
    main()
# Original solution
n = str(eval(input()))
rn = ''.join(list(reversed(list(n))))
print(('Yes' if n == rn else 'No'))

# Optimized solution
n = str(eval(input()))
rn = ''.join(reversed(list(n)))
print(('Yes' if n == rn else 'No'))
# Original solution
n = str(eval(input()))
if n[0] == n[2]:
    print("Yes")
else:
    print("No")

# Optimized solution
n = int(eval(input()))
x = list(str(n))
if x == x[::-1]:
    print("Yes")
else:
    print("No")
# Original solution
n, a, b = list(map(int, input().split()))
x = list(map(int, input().split()))

ans = 0
for i in range(n-1):
      ans += min(a * (x[i+1] - x[i]), b)


print(ans)

# Optimized solution

N,A,B = list(map(int, input().split()))

X = list(map(int, input().split()))

ans = 0
for i in range(1,N):
    if (X[i] - X[i-1]) * A <= B:
        ans += (X[i] - X[i-1]) * A
    else:
        ans += B
print(ans)
# Original solution
def main():
    n, a, b, *x = list(map(int, open(0).read().split()))
    ans = 0
    for i, j in zip(x, x[1:]):
        if a * (j - i) > b:
            ans += b
        else:
            ans += a * (j - i)

    print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    n, a, b, *x = list(map(int, open(0).read().split()))
    ans = 0
    it = iter(x)
    nw = it.__next__()
    for nx in it:
        c = (nx - nw) * a
        if c > b:
            ans += b
        else:
            ans += c
        nw = nx

    print(ans)


if __name__ == '__main__':
    main()
# Original solution
N, A, B = list(map(int, input().split()))
X = list(map(int, input().split()))

X.sort()

group=[[X[0]]]
for i in range(N-1):
    if (X[i+1] - X[i]) * A > B:
        group.append([X[i+1]])
    else:
        group[-1].append(X[i+1])
#print(group)

ans = (len(group) - 1) * B
for g in group:
    ans += (max(g) - min(g)) * A
print(ans)

# Optimized solution
N, A, B = list(map(int, input().split()))
X = list(map(int, input().split()))

X.sort()
ans = 0
for i in range(N-1):
    ans += min((X[i+1] - X[i]) * A, B)
print(ans)
# Original solution
N,A,B=list(map(int,input().split()))
X=list(map(int,input().split()))
from collections import deque
X=deque(X)
cost=0
now=X.popleft()
while len(X)>0:
    if (X[0]-now)*A<=B:
        cost+=(X[0]-now)*A
    else:cost+=B
    now=X.popleft()
print(cost)

# Optimized solution
N,A,B=list(map(int,input().split()))
now=0
ans=0
for x in map(int,input().split()):
    if now!=0:
        if (x-now)*A>B:
            ans+=B
        else:
            ans+=(x-now)*A
    now=x
print(ans)
# Original solution
n,a,b = list(map(int, input().split()))
x = list(map(int, input().split()))

ans = 0
for i in range(n-1):
  ans += min(a*(x[i+1]-x[i]), b)
print(ans)

# Optimized solution
n,a,b = list(map(int, input().split()))
x = list(map(int, input().split()))

ans = 0
for i in range(1,n):
  ans += min(b, a*(x[i]-x[i-1]))
print(ans)
# Original solution
# python3 (3.4.3)
import sys
input = sys.stdin.readline

# main
N,A,B = list(map(int,input().split()))
X = list(map(int,input().split()))

ans = 0
for i in range(N-1):
    ans += min(B, A*(X[i+1]-X[i]))

print(ans)

# Optimized solution
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,A,B = list(map(int,input().split()))
X = list(map(int,input().split()))

ans = 0
for i in range(N-1):
    d = X[i+1] - X[i]
    if d*A > B:
        ans += B
    else:
        ans += d*A

print(ans)
# Original solution
N, A, B = list(map(int, input().split()))
X= list(map(int, input().split()))

I = []
for i in range(N-1):
    I.append(X[i+1]-X[i])

M = X[N-1]-X[0]
I_srt = sorted(I)
I_srt.reverse()


ans = min([(M-sum(I_srt[:i]))*A + B*i for i in range(N)])

print(ans)


# Optimized solution
N, A, B = list(map(int, input().split()))
X= list(map(int, input().split()))

I = []
for i in range(N-1):
    I.append(X[i+1]-X[i])

M = X[N-1]-X[0]
I_srt = sorted(I)
I_srt.reverse()

I_sum = [0]
for i in range(N-1):
    I_sum.append(I_srt[i]+I_sum[i])


ans = min([(M-I_sum[i])*A + B*i for i in range(N)])

print(ans)
# Original solution
N, A, B = list(map(int, input().split()))

town = list(map(int, input().split()))
diff = [0]*(N+1)
for i in range(1, N):
    diff[i] = town[i] - town[i-1]

sumz = 0
for i in range(1, N+1):
    if diff[i]*A > B:
        sumz += B
    else:
        sumz += diff[i]*A

print(sumz)


# Optimized solution
N, A, B = list(map(int, input().split()))
num = list(map(int, input().split()))

ans = 0
for i in range(1, N):
    d = num[i] - num[i-1]
    if d*A < B:
       ans += d*A
    else:
        ans += B

print(ans)
# Original solution
N,A,B=list(map(int,input().split()))
*X,=list(map(int,input().split()))
ans = 0
for i in range(N-1):
    ans += min(B,A*(X[i+1]-X[i]))
print(ans)

# Optimized solution
m=lambda:list(map(int,input().split()))
N,A,B=m();*X,=m()
print((sum(min(B,A*(X[i+1]-X[i]))for i in range(N-1))))
# Original solution
from collections import deque

N,A,B = list(map(int, input().split()))
X = list(map(int, input().split()))

INF = float("inf")

dist = deque(X)

next_x = +1
i = 0
ans = 0
while len(dist) != 1:

    if A*abs(dist[i+next_x] - dist[i]) <= B:
        ans += A*abs(dist[i+next_x] - dist[i])
        if next_x == 1:
            dist.popleft()
            i = 0
        else:
            dist.pop()
            i = len(dist)-1
    else:
        ans += B
        if next_x == 1:
            dist.popleft()
            i = len(dist)-1
        else:
            dist.pop()
            i = 0
        
        next_x = -next_x
        
print(ans)

# Optimized solution
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

n,a,b = li()
x = li()

ans = 0
for i in range(n-1):
    if a*(x[i+1]-x[i]) > b:
        ans += b
        
    else:
        ans += a*(x[i+1]-x[i])
        
print(ans)
# Original solution
n,a,b = list(map(int,input().split()))
lst = list(map(int,input().split()))
ans = 0
for i in range(1,n):
    if (lst[i] - lst[i-1]) * a >= b:
        ans += b
    else:
        ans += (lst[i] - lst[i-1]) * a
print(ans)

# Optimized solution
n,a,b = list(map(int,input().split()))
X = list(map(int,input().split()))
pos = X[0]
ans = 0
for i in range(1, n):
    ans += min(b, (X[i] - pos)*a)
    pos = X[i]
print(ans)
# Original solution
N,A,B = list(map(int,input().split()))
X = list(map(int,input().split()))
ans = 0
for i in range(N-1):
  ans += min((X[i+1]-X[i])*A,B)
print(ans)

# Optimized solution
N, A, B = list(map(int, input().split()))
X = list(map(int, input().split()))
ans = 0
pos = X[0]
for i in range(1, N):
    ans += min(A * (X[i] - pos), B)
    pos = X[i]
print(ans)
# Original solution
n,a,b=list(map(int,input().split()))
X=list(map(int,input().split()))
D=[]
for i in range(n-1):
    D.append(X[i+1]-X[i])
ans=0
for i in range(n-1):
    ans+=min(a*D[i],b)
print(ans)

# Optimized solution
n,a,b=list(map(int,input().split()))
X=list(map(int,input().split()))
ans=0
for i in range(n-1):
    ans+=min(a*(X[i+1]-X[i]),b)
print(ans)
# Original solution
from math import factorial
def comb (x,y):
	return factorial(x)//factorial(x-y)//factorial(y)

w,h,ax,ay,bx,by=list(map(int,input().split()))
dx=abs(ax-bx)
dx=min(dx,w-dx)
dy=abs(ay-by)
dy=min(dy,h-dy)
ans=1
if dx*2==w:ans*=2
if dy*2==h:ans*=2
ans*=comb(dx+dy,dx)
print((ans%100000007))

# Optimized solution
from math import factorial
def comb (x,y):
	return factorial(x)//factorial(x-y)//factorial(y)

w,h,ax,ay,bx,by=list(map(int,input().split()))
dx=abs(ax-bx)
dx=min(dx,w-dx)
dy=abs(ay-by)
dy=min(dy,h-dy)
an=1
if dx*2==w:an*=2
if dy*2==h:an*=2
an*=comb(dx+dy,dx)
print((an%int(1E8+7)))
# Original solution
# AOJ 1501: Grid
# Python3 2018.7.13 bal4u

MOD = 100000007
def dp(n, k):
	if tbl[n][k]: return tbl[n][k]
	if (k << 1) > n: k = n-k
	if k == 0: ans = 1
	elif k == 1: ans = n
	else: ans = dp(n-1, k) + dp(n-1, k-1)
	tbl[n][k] = ans % MOD
	return tbl[n][k]

tbl = [[0 for j in range(1001)] for i in range(1001)]
k = 0
r, c, a1, a2, b1, b2 = list(map(int, input().split()))

dr = abs(a1-b1)
if dr > r-dr: dr = r-dr
if (dr << 1) == r: k += 1

dc = abs(a2-b2)
if dc > c-dc: dc = c-dc
if (dc << 1) == c: k += 1

print(((dp(dr+dc, min(dr, dc)) << k) % MOD))



# Optimized solution
# AOJ 1501: Grid
# Python3 2018.7.13 bal4u

from math import factorial
def comb (n, k):
	return factorial(n)//factorial(n-k)//factorial(k)
	
k = 0
r, c, a1, a2, b1, b2 = list(map(int, input().split()))

dr = abs(a1-b1)
if dr > r-dr: dr = r-dr
if (dr << 1) == r: k += 1

dc = abs(a2-b2)
if dc > c-dc: dc = c-dc
if (dc << 1) == c: k += 1

print(((comb(dr+dc, min(dr, dc)) << k) % 100000007))
# Original solution
h, w, n = list(map(int, input().split()))
li = []
l = [w] * h
for _ in range(n):
    x, y = list(map(int, input().split()))
    li.append((x - 1, y - 1))
li.sort()
cnt = 0
ans = h
for x, y in li:
    if x - cnt == y:
        cnt += 1
    elif x - cnt > y:
        ans = min(ans, x)
print(ans)



# Optimized solution
h, w, n = list(map(int, input().split()))
l = [list(map(int, input().split())) for _ in range(n)]
l.sort(key=lambda x: (x[1], x[0]))
t = 0
a = [h + 1]
for x, y in l:
    if x > y + t:
        a.append(x)
    elif x == y + t:
        t += 1
print((min(a) - 1))
# Original solution
H,W,N=list(map(int,input().split()))
XY=[]
for i in range(N):
    XY.append(list(map(int,input().split())))

XY.sort()

conditions=[i-1 for i in range(H+1)]
for xy in XY:
    if conditions[xy[0]]>=xy[1]:
        print(xy[0]-1)
        break
    if xy[1]==conditions[xy[0]]+1:
        conditions=[conditions[i] if i<=xy[0] \
                   else conditions[i]-1 for i in range(H+1)]
 
else:
    print(H)

# Optimized solution
H,W,N=list(map(int,input().split()))
XY=[]
for i in range(N):
    XY.append(list(map(int,input().split())))

XY.sort()

conditions=[2,1]
for xy in XY:
    if xy[0]>conditions[0]:
        conditions=[xy[0],conditions[1]+xy[0]-conditions[0]]
    if conditions[1]>=xy[1]:
        print(xy[0]-1)
        break
    if xy[1]==conditions[1]+1:
        conditions=[conditions[0],conditions[1]-1]
else:
    print(H)
# Original solution
H, W, N = list(map( int, input().split()))
V = [H-1]*W
X = [ tuple( map( int, input().split())) for _ in range(N)]
X.sort()
d = 0
for i in range(N):
    x, y = X[i]
    x, y = x-1, y-1
    if x == y+d:
        d += 1
    elif x > y+d:
        V[y] = min( V[y], x-1)
print(( min(V)+1))

# Optimized solution
H, W, N = list(map( int, input().split()))
X = [ tuple( map( int, input().split())) for _ in range(N)]
X.sort()
d = 0
ans = H
for i in range(N):
    if X[i][1]+d == X[i][0]:
        d += 1
    if X[i][1] + d < X[i][0]:
        ans = X[i][0]-1
        break
print(ans)
# Original solution
H, W, N = list(map(int, input().split()))

Y = [W+100]*(H+1)
P = [[] for i in range(W+1)]
for i in range(N):
    x, y = list(map(int, input().split()))
    if x < y:
        continue
    Y[x-y] = min(Y[x-y], y-1)
    P[y-1].append(x-1)
base = 0
ans = H
for y in range(W):
    while Y[base] == y:
        base += 1
    xmin = y + base
    for x in P[y]:
        if xmin <= x:
            ans = min(x, ans)
print(ans)

# Optimized solution
readline = open(0).readline
write = open(1, 'w').write

H, W, N = list(map(int, readline().split()))

Y = [W+1]*(H+1)
P = [[] for i in range(W+1)]
for i in range(N):
    x, y = list(map(int, readline().split()))
    if x < y:
        continue
    Y[x-y] = min(Y[x-y], y-1)
    P[y-1].append(x-1)
base = 0
ans = H
for y in range(W):
    while Y[base] == y:
        base += 1
    xmin = y + base
    for x in P[y]:
        if xmin <= x:
            ans = min(x, ans)
write("%d\n" % ans)