Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import itertools

h, w, m = map(int,input().split())

h_dict = dict()
w_dict = dict()

targets = [None] * (3 * 10 ** 5)

for i in range(m):
    temp_h, temp_w, = map(int,input().split())

    h_dict[temp_h] = h_dict.get(temp_h, default=0) + 1
    w_dict[temp_w] = w_dict.get(temp_w, default=0) + 1

    targets[i] = (temp_h, temp_w)

max_h = max(h_dict.values())
max_w = max(w_dict.values())

h_candidates = [k for k, v in h_dict.items() if v == max_h]
w_candidates = [k for k, v in w_dict.items() if v == max_w]

for temp_h, temp_w in itertools.product(h_candidates, w_candidates):
    if not ((temp_h, temp_w) in targets):
        print(h_dict[temp_h] + w_dict[temp_w])
        break
else:
    print(h_dict[temp_h] + w_dict[temp_w] - 1)

### FIXED CODE ###

h, w, m = map(int,input().split())

h_dict = dict()
w_dict = dict()

targets = list()

for i in range(m):
    temp_h, temp_w, = map(int,input().split())

    h_dict[temp_h] = h_dict.get(temp_h, default=0) + 1
    w_dict[temp_w] = w_dict.get(temp_w, default=0) + 1

    targets.append((temp_h, temp_w))

h_dict_values = list(h_dict.values())
w_dict_values = list(w_dict.values())

max_h = max(h_dict_values)
max_w = max(w_dict_values)

nh = h_dict_values.count(max_h)
nw = w_dict_values.count(max_w)

x = 0

for i in range(m):
    temp_h, temp_w = targets[i]
    if h_dict[temp_h]==max_h and w_dict[temp_w]==max_w:
        x += 1

ans = max_h + max_w

if x == nh * nw:
    ans -= 1

print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import math
INT_MAX = 2**31 - 1
def update(tree,x,y,N):
    x += N - 1
    tree[x] = y
    while True:
        if(x <= 0):
            break
        x = math.floor((x - 1)/2)
        left = x*2+1
        right = x*2+2
        tree[x] = min(tree[left],tree[right])

def find(tree,x,y,k,l,r):

    if (r <= x or y <= l):
        return INT_MAX - 1
    if ( x <= l and r <= y):
        return tree[k]
    v_left = find(tree, x, y, k*2 + 1, l, int((l+r)/2))
    v_right = find(tree, x, y, k*2 + 2, int((l+r)/2), r)
    return min(v_left, v_right)

_N,k = map(int, input().split())
*arr, = map(int,input().split())
N = 1
res = []
while True:
    if(N >= _N):
        break
    N *= 2
if not (N == 1):
    A_bin_tree = [INT_MAX]*(2*N - 1)
else:
    A_bin_tree = [INT_MAX]
for i in range(_N):
    update(A_bin_tree,i,arr[i],N)

for i in range(_N-k+1):
    z = find(A_bin_tree,i,i+k,0,0,N)
    res.append(z)

print(*res)



### FIXED CODE ###

INTMAX = (1<<31) - 1

def ans():
    for i in range(k):
        x = i + OFS
        A[x] = arr[i]
        while True:
            if(x <= 0):
                break
            x = (x - 1)//2
            l = A[x*2+1]
            r = A[x*2+2]
            A[x] = l if l < r else r#min(tree[left],tree[right])
    res = []
    c = 0
    for i in range(_N-k):
        res.append(A[0])
        x = c + OFS
        A[x] = arr[i+k]
        while True:
            if(x <= 0):
                break
            x = (x - 1)//2
            l = A[x*2+1]
            r = A[x*2+2]
            A[x] = l if l < r else r
        c += 1
        if(c == k):
            c = 0
    res.append(A[0])
    print(*res)

_N,k = map(int, input().split())
*arr, = map(int,input().split())
if(k==1):
    print(*arr)
else:
    N = 2**(_N-1).bit_length()
    A = [INTMAX]*(2*N)
    OFS = N - 1
    ans()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = 0
ans = 0
dic = {}
for i in set(a):
    b = a.count(i)
    dic.setdefault(i, a.count(i))
    if b > 1:
        ans += b*(b-1)//2
for i in a:
    print(ans - (dic[i] - 1))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = 0
ans = 0
dic = {}
for i in a:
    if i not in dic.keys():
        dic[i] = 1
    else:
        dic[i] += 1
for i in dic.values():
    ans += i*(i-1)//2
for i in a:
    print(ans - (dic[i] - 1))
### BUGGY CODE ###

n, m = map(int, input().split())
xl = [int(i) for i in input().split()]
xl.sort()
d = m - n
if d <= 0:
    print(0)
else:
    dl = []
    for i in range(len(xl)-1):
        dl.append(xl[i+1] - xl[i])
        dl.sort()
    print(sum(dl[:d]))

### FIXED CODE ###

import numpy as np

n, m = map(int, input().split())
xl = [int(i) for i in input().split()]
xl.sort()
d = m - n
if d <= 0:
    print(0)
else:
    darray = np.sort(np.array(xl[1:]) - np.array(xl[:-1]))
    print(np.sum(darray[:d]))
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

n=int(input())
cnt=0
for i in range(1,n+1):
  for j in range(1,n+1):
    if i*j<n:
      cnt+=1
    else:
      break


print(cnt)

### FIXED CODE ###

import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

n=int(input())
cnt=0
for i in range(1,n+1):
  for j in range(i+1,n+1):
    if i*j<n:
      cnt+=2
    else:
      break
      
for j in range(1,n+1):
  if j*j<n:
    cnt+=1

print(cnt)
### BUGGY CODE ###

mod=10**9+7
n,k=map(int,input().split())
N=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  N[a-1]+=[b-1]
  N[b-1]+=[a-1]
Chk=[False]*n
S=[0]
Chk[0]=True
ans=k
while S:
  ss=S.pop(-1)
  for sss in N[ss]:
    if Chk[sss]==True:
      continue
    else:
      ct=1
      for ssss in N[ss]:
        if Chk[ssss]==True:
          ct+=1
      ans=(ans*max(k-ct,0))%mod
      Chk[sss]=True
      S.append(sss)
print(ans%mod)



### FIXED CODE ###

import sys
input = sys.stdin.readline

mod=10**9+7
n,k=map(int,input().split())
N=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  N[a-1]+=[b-1]
  N[b-1]+=[a-1]
Chk=[0]*n
S=[0]
Chk[0]=1
ans=k
while S:
  ss=S.pop()
  for sss in N[ss]:
    if Chk[sss]>0:
      continue
    else:
      ans=(ans*max(k-Chk[ss],0))%mod
      Chk[ss]+=1
      Chk[sss]=2
      S.append(sss)
print(ans%mod)
### BUGGY CODE ###

import math


def calc(A, b):
    retval = 0
    for a in A:
        retval += abs(a - b)
    return retval


def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] -= (i + 1)

    left = min(A)
    right = max(A)

    while left < right:
        c1 = math.floor((left + left + right) / 3)
        c2 = math.ceil((left + right + right) / 3)
        if calc(A, c1) <= calc(A, c2):
            right = c2 - 1
        else:
            left = c1 + 1
    print(calc(A, left))


if __name__ == "__main__":
    main()


### FIXED CODE ###


def calc(A, b):
    retval = 0
    for a in A:
        retval += abs(a - b)
    return retval


def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] -= (i + 1)

    print(calc(A, sorted(A)[(N)//2]))

#    left = min(A)
#    right = max(A)
#
#    while left < right:
#        c1 = (left + left + right) // 3       # floor
#        c2 = -(-(left + right + right) // 3)  # ceil
#        if calc(A, c1) <= calc(A, c2):
#            right = c2 - 1
#        else:
#            left = c1 + 1
#    print(calc(A, left))


if __name__ == "__main__":
    main()
### BUGGY CODE ###

n,k = map(int,input().split())
total = 0
for i in range(k,n+2):
    m = sum(range(0,i))
    M = sum(range(n-i+1,n+1))
    total += M - m + 1
print(total % (10**9 + 7))

### FIXED CODE ###

n,k = map(int,input().split())
total = 0
for i in range(k,n+2):
    m = i*(i-1)//2
    M = i*n-(i*(i-1))//2
    total += M - m + 1
print(total % (10**9 + 7))
### BUGGY CODE ###

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

for k in range(n):
    if k:
        for m in range(1,10**18):
            if a[k-1][0] <= m*a[k][0] and a[k-1][1] <= m*a[k][1]:
                a[k] = [m*a[k][0], m*a[k][1]]
                break
print(sum(a[n-1]))


### FIXED CODE ###

import math
from decimal import Decimal
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

for k in range(n):
    if k:
        m0 = math.ceil(Decimal(a[k-1][0])/Decimal(a[k][0]))
        m1 = math.ceil(Decimal(a[k-1][1])/Decimal(a[k][1]))
        m = max(m0, m1)
        a[k] = [m*a[k][0], m*a[k][1]]
print(sum(a[n-1]))
### BUGGY CODE ###

n, k = list(map(int, input().split()))
li = list(map(int, input().split())) + [0] * (k-1)

dp = [0] + [float("inf")] * (n + k -1)

for i in range(n-1):
    for k in range(1,k+1):
        dp[i+k] = min(dp[i+k], dp[i] + abs(li[i+k] - li[i]))

print(dp[n-1])

### FIXED CODE ###

import numpy as np

n,k = list(map(int, input().split()))
h = np.array(list(map(int, input().split())))

dp = np.array([0] * n)

for i in range(1,n):
    s = max(i-k,0)
    dp[i] = min(dp[s : i] + abs(h[i] - h[s:i]))

print(dp[n-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C


# See:
# https://qiita.com/suecharo/items/30f5d817da4c948c3be6
def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr

    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right


if __name__ == '__main__':
    n = int(input())
    x = list(map(int, input().split()))
    order = list(x)

    for i in range(n):
        tmp = order[i]
        x.remove(tmp)
        x = quick_sort(x)
        print(x[(n // 2) - 1])
        x += [tmp]


### FIXED CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    n = int(input())
    x = list(map(int, input().split()))
    sorted_x = sorted(x)

    low = sorted_x[(n // 2) - 1]
    high = sorted_x[(n // 2)]

    for i in range(n):
        if x[i] < high:
            print(high)
        else:
            print(low)
### BUGGY CODE ###

n = int(input())
arr = map(int, input().split())
zero = False
ans = 1
ok = True
for e in arr:
	if e == 0:
		zero = True
	ans = ans * e;
	if ans > 10**18:
		ok = False
if zero:
	print(0)
else:
	if ok:
		print(ans)
	else:
		print(-1)


### FIXED CODE ###

n = int(input())
arr = list(map(int,input().split()))
if 0 in arr:
    print(0)
else:
    res = 1
    flag = 0
    for i in arr:
        res = res*i
        if res>10**18:
            flag = 1
            break
    if flag==1:
        print(-1)
    else:
        print(res)
### BUGGY CODE ###

from collections import deque
N=int(input())
A=deque(map(int,input().split()))
B=deque([])
x=A.popleft()
B.append(x)
s=0
for i in range(N-1):
    x=A.popleft()
    for j in range(i+1):
        if B[j]+x-i-1+j==0:
           s+=1
    B.append(x)
print(s)

### FIXED CODE ###

def count(dic,x):
    if x in dic:
        dic[x]+=1
    else:
        dic[x]=1

N=int(input())
A=list(map(int,input().split()))
dic1={}
dic2={}
s=0
for i in range(N):
    count(dic1,i-A[i])
    count(dic2,i+A[i])
for x in dic1:
    if x in dic2:
        s+=dic1[x]*dic2[x]
print(s)
### BUGGY CODE ###

N, K = map(int, input().split(" "))
H = list(map(int, input().split(" ")))

costs = [0]*(N+10)
for i in range(1, N):
    j = max(0, i-K)
    costs[i] = min(cost+abs(H[i]-h) for cost, h in zip(costs[j:i], H[j:i]))

print(costs[N-1])

### FIXED CODE ###

N, K = map(int, input().split(" "))
H = list(map(int, input().split(" ")))

costs = [0]*(N+10)
for i in range(1, N):
    j = max(0, i-K)
    h_i = H[i]
    costs[i] = min(cost+abs(h_i-h) for cost, h in zip(costs[j:i], H[j:i]))

print(costs[N-1])
### BUGGY CODE ###

n=int(input())
import fractions 
from functools import reduce
arr = list(map(int,input().split()))

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcma(numbers):
    return reduce(lcm_base, numbers, 1)
  
a = lcma(arr)

ans = [(a//i)%1000000007 for i in arr]

print(sum(ans)%1000000007)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
 
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
 
a = 1
for i in range(N):
    a = lcm(a, A[i])
 
ans = 0
for i in range(N):
    ans += a * pow(A[i], mod-2, mod)
 
print(ans % mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n,m = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    e[a].append(b)
    e[b].append(a)
qv = int(input())
Q = [list(map(int,input().split())) for i in range(qv)]
Q = Q[::-1]
l = [[0]*(11) for i in range(n+1)]
for v,d,c in Q:
    if l[v][d] > 0:
        continue
    l[v][d] = c
dic = {}
color = [0]*(n+1)

left = [i for i in range(1,n+1)]
num = 0
while num < qv and left:
    v,d,c = Q[num]
    if v not in dic:
        for i in range(10,-1,-1):
            if l[v][i] > 0:
                M = i
                break
        dic[v] = [set() for i in range(M+1)]
        s = set()
        s.add(v)
        dic[v][0] |= s
        q = [v]
        for i in range(1,M+1):
            nq = []
            for now in q:
                for nex in e[now]:
                    if nex in s:
                        continue
                    nq.append(nex)
                    s.add(nex)
            dic[v][i] |= s
            q = nq
    nl = []
    
    for i in left:
        if i in dic[v][d]:
            color[i] = c
        else:
            nl.append(i) 
    num += 1
    left = nl
    
for i in color[1:]:
    print(i)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**6)
n,m = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    e[a].append(b)
    e[b].append(a)
qv = int(input())
Q = [list(map(int,input().split())) for i in range(qv)]

color = [0]*(n+1)
used = [-1]*(n+1)

for v,d,c in Q[::-1]:
    if used[v] > d:
        continue
    
    q = deque([[v,d]])
    while q:
        now, dis = q.popleft()
        if dis < 0:
            continue
        if color[now] == 0:
            color[now] = c
        for nex in e[now]:
            if used[nex] < dis-1:
                used[nex] = dis-1
                q.append([nex,dis-1])
    
for i in color[1:]:
    print(i)
### BUGGY CODE ###

import sys, threading
sys.setrecursionlimit(10 ** 6)  # max depth of recursion
threading.stack_size(2 ** 27)
from bisect import bisect_left, bisect_right
INF = 10**10
def main():
    #print = out.append
    ''' Cook your dish here! '''
    h, n = get_list()
    wepons = dict()
    for _ in range(n):
        a,b = get_list()
        if a in wepons:
            wepons[a] = min(b, wepons[a])
        else: wepons[a] = b

    dp = [-1]*(h+1)
    dp[0] = 0
    #print(wepons)
    def calc(n):
        if n<0: return 0
        if dp[n]!=-1: return dp[n]
        #print(n)
        cst = INF
        for wepon in wepons:
            #print(n-wepon)
            cst = min(cst, calc(n-wepon) + wepons[wepon])
        dp[n] = cst
        #print(n, cst)
        return cst
    print(calc(h))


import sys
#rom collections import defaultdict, Counter
#from bisect import bisect_left, bisect_right
#from functools import reduce
#import math
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
get_int = lambda: int(input())
get_list = lambda: list(map(int, input().split()))
threading.Thread(target=main).start()

### FIXED CODE ###

''' Hey stalker :) '''
INF = 10**10
def main():
    #print = out.append
    ''' Cook your dish here! '''
    h, n = get_list()
    wepons = dict()
    for _ in range(n):
        a,b = get_list()
        if a in wepons:
            wepons[a] = min(b, wepons[a])
        else: wepons[a] = b
    dp = [0]*(h+1)
    for i in range(1, h+1):
        ans = INF
        for wp in wepons:
            if wp>i: ans = min(ans, wepons[wp])
            else: ans = min(ans, wepons[wp] + dp[i-wp])
        dp[i] = ans
    print(dp[-1])

''' Pythonista fLite 1.1 '''
import sys
#from collections import defaultdict, Counter
#from bisect import bisect_left, bisect_right
#from functools import reduce
#import math
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda: int(input())
get_list = lambda: list(map(int, input().split()))
main()
#[main() for _ in range(int(input()))]
print(*out, sep='\n')
### BUGGY CODE ###

n, k = list(map(int, input().split()))
mod = int(1e9 + 7)

def comb(a, b):
    dp = [[0 for i in range(b+1)] for j in range(a+1)]
    for j in range(b+1):
        dp[0][j] = 0
    for i in range(a + 1):
        dp[i][0] = 1

    for i in range(1, a+1):
        for j in range(1, b+1):
            dp[i][j] = dp[i-1][j-1] % mod + dp[i-1][j] % mod
    return dp[a][b] % mod


for i in range(1, k+1):
    print(comb(n-k+1, i) * comb(k-1, i-1) % mod)


### FIXED CODE ###

n, k = list(map(int, input().split()))
mod = int(1e9 + 7)

a, b = 2000, 2000
dp = [[0 for i in range(b+1)] for j in range(a+1)]
for j in range(b+1):
    dp[0][j] = 0
for i in range(a + 1):
    dp[i][0] = 1

for i in range(1, a+1):
    for j in range(1, b+1):
        dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod


for i in range(1, k+1):
    print(dp[n-k+1][i] * dp[k-1][i-1] % mod)
### BUGGY CODE ###

# D - Even Relation

# 木なのでノードAB間の辺を辿ればそれがAB間の最短経路となる

from collections import deque

N = int(input())

dist = [[0]*N for _ in range(N)]
neighbor = [[] for _ in range(N)]

for _ in range(N-1):
    u, v, w = map(int, input().split())
    dist[u-1][v-1] = w%2 + 2
    dist[v-1][u-1] = w%2 + 2
    neighbor[u-1].append(v-1)
    neighbor[v-1].append(u-1)

d = deque([0])
color = [0] + [-1]*(N-1)

while d:
    current_point = d.popleft()
    for next_point in neighbor[current_point]:
        if color[next_point] != -1:
            continue
        else:
            color[next_point] = (color[current_point] + dist[current_point][next_point]) % 2
            d.append(next_point)

for idx in range(N):
    print(color[idx])

### FIXED CODE ###

# D - Even Relation

# 木なのでノードAB間の辺を辿ればそれがAB間の最短経路となる
# 全ての｢辺｣についてループする

from collections import deque

N = int(input())

edge = [[] for _ in range(N)]

for _ in range(N-1):
    u, v, w = map(int, input().split())
    edge[u-1].append([v-1, w])
    edge[v-1].append([u-1, w])

color = [0] + [-1]*(N-1)
d = deque([0])

while d:
    current_point = d.pop()
    for current_edge in edge[current_point]:
        if color[current_edge[0]] == -1:
            color[current_edge[0]] = (color[current_point] + current_edge[1]) % 2
            d.append(current_edge[0])

for idx in range(N):
    print(color[idx])
### BUGGY CODE ###

from collections import Counter

s=input()[::-1]
ans=0
lst=[0]
num=0
p=1
for i in s:
    lst.append((int(i)*p+lst[-1])%2019)
    p=p*10

cou=dict(Counter(lst))
for x in cou.values():
    ans+=x*(x-1)/2
print(int(ans))

### FIXED CODE ###

from collections import Counter

s=input()[::-1]
ans=0
lst=[0]
num=0
p=1
for i in s:
    lst.append((int(i)*p+lst[-1])%2019)
    p=p*10%2019

ans=sum(x*(x-1)//2 for x in Counter(lst).values())
print(ans)
### BUGGY CODE ###

#abc164-4
import collections
s = input()

counts = []#modの値と個数を記録するリスト

for i in range(len(s)):
    counts.append(int(s[i:]) % 2019)
counts.append(0)
c = collections.Counter(counts)
mlist = list(c.values())
sumcount = 0
for m in mlist:
    sumcount += m*(m-1)/2
print(int(sumcount))
    

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

import sys
import copy
R, C, K = map(int, input().split())
item = [[0] * (C + 1) for _ in range(R + 1)]  # dp配列と合わせるために, 0行目, 0列目を追加している.
for s in sys.stdin.readlines():
    r, c, v = map(int, s.split())
    r -= 1
    c -= 1
    item[r][c] = v
    
dp0 = [[0] * (C+1) for r in range(R+1)]
dp1 = [[0] * (C+1) for r in range(R+1)]
dp2 = [[0] * (C+1) for r in range(R+1)]
dp3 = [[0] * (C+1) for r in range(R+1)]

for r in range(R):
   for c in range(C):
      dp3[r][c] = max(dp3[r][c], dp2[r][c] + item[r][c])
      dp2[r][c] = max(dp2[r][c], dp1[r][c] + item[r][c])
      dp1[r][c] = max(dp1[r][c], dp0[r][c] + item[r][c])
      dp1[r][c+1] = max(dp1[r][c], dp1[r][c+1])
      dp2[r][c+1] = max(dp2[r][c], dp2[r][c+1])
      dp3[r][c+1] = max(dp3[r][c], dp3[r][c+1])
      dp0[r+1][c] = max(dp0[r+1][c], dp1[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp2[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp3[r][c])
ans = max(dp0[R-1][C-1], dp1[R-1][C-1])
ans = max(ans, dp3[R-1][C-1])
ans = max(ans, dp2[R-1][C-1])
print(ans)



### FIXED CODE ###

import sys
import copy
R, C, K = map(int, input().split())
item = [[0] * (C + 1) for _ in range(R + 1)]  # dp配列と合わせるために, 0行目, 0列目を追加している.
for s in sys.stdin.readlines():
    r, c, v = map(int, s.split())
    r -= 1
    c -= 1
    item[r][c] = v
    
dp0 = [[0] * (C+1) for r in range(R+1)]
dp1 = [[0] * (C+1) for r in range(R+1)]
dp2 = [[0] * (C+1) for r in range(R+1)]
dp3 = [[0] * (C+1) for r in range(R+1)]

for r in range(R):
   for c in range(C):
      dp3[r][c] = max(dp3[r][c], dp2[r][c] + item[r][c])
      dp2[r][c] = max(dp2[r][c], dp1[r][c] + item[r][c])
      dp1[r][c] = max(dp1[r][c], dp0[r][c] + item[r][c])
      dp1[r][c+1] = max(dp1[r][c], dp1[r][c+1])
      dp2[r][c+1] = max(dp2[r][c], dp2[r][c+1])
      dp3[r][c+1] = max(dp3[r][c], dp3[r][c+1])
      dp0[r+1][c] = max(dp0[r+1][c], dp1[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp2[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp3[r][c])
ans = max(dp0[R-1][C-1], dp1[R-1][C-1])
ans = max(ans, dp3[R-1][C-1])
ans = max(ans, dp2[R-1][C-1])
print(ans)
### BUGGY CODE ###

import sys
from io import StringIO
import unittest

def resolve():
    n = int(input())
    s = input()
    ans = s.count('R') * s.count('G') * s.count('B')

    for i in range(n):
        for j in range(1, n, 1):
            if i + 2 * j < n:
                if s[i] != s[i + j] and s[i] != s[i + 2 * j] and s[i + j] != s[i + 2 * j]:
                    ans -= 1

    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4
RRGB"""
        output = """1"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"""
        output = """1800"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

### FIXED CODE ###

import sys
from io import StringIO
import unittest

def resolve():
    n = int(input())
    s = input()
    ans = s.count('R') * s.count('G') * s.count('B')

    for i in range(n):
        for j in range(1, (n - 1)//2 + 1, 1):
            if i + 2 * j < n:
                if s[i] != s[i + j] and s[i] != s[i + 2 * j] and s[i + j] != s[i + 2 * j]:
                    ans -= 1

    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4
RRGB"""
        output = """1"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"""
        output = """1800"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()
### BUGGY CODE ###

n = int(input())
a_list = [int(x) for x in input().split()]

count = 0
max = a_list[0]

for a in a_list:
    for _ in range(n):
        if max > a:
            count += 1
            a += 1
    max = a
print(count)

### FIXED CODE ###

n = int(input())
a_list = [int(x) for x in input().split()]

# count = 0
# max = a_list[0]

# for a in a_list:
#     for _ in range(n):
#         if max > a:
#             count += 1
#             a += 1
#     max = a
# print(count)

max = a_list[0]
count = 0

for a in a_list:
    if max > a:
        d = max - a
        count += d
        a += d
    max = a

print(count)