Harryxun/stf_run huggingface dataset:
from collections import defaultdict
#n=int(input())
#a_=list(map(int,input().split()))
import numpy as np
n=2000
a_=range(1,n+1)
a=[]
for i,ai in enumerate(a_):
      a.append([1+i,ai])
a.sort(key=lambda x:x[1],reverse=True)
dp=np.zeros((n+1,n+1),np.int64) #dp[i,j]:i人目までを配置し終えていて、そのうちj人を右に置いた時の最大値。j<=i
dp[1,1]=a[0][1]*(n-a[0][0])
dp[1,0]=a[0][1]*(a[0][0]-1)
for i in range(2,n+1):#i人目の幼児。a[i-1]
      dp[i,0]=dp[i-1,0]+a[i-1][1]*abs((a[i-1][0]-1-(i-1))) #i人目を左にする。その時左に溜まっているのはi-1人
      dp[i,i]=dp[i-1,i-1]+a[i-1][1]*abs((n-a[i-1][0]-(i-1))) #i人目を右にする。その時右に溜まっているのはi-1人
      #i人目を左に
      l=dp[i-1,1:i]+[a[i-1][1]*abs((a[i-1][0]-1-j))for j in range(i-2,-1,-1)] #j:左に溜まっている人数
      #i人目を右に
      r=dp[i-1,:i-1]+[a[i-1][1]*abs((n-a[i-1][0]-j)) for j in range(i-1)] #j:右に溜まっている人数
      dp[i,1:i]=np.maximum(l,r)
print(max(dp[n]))


### FIXED CODE ###

from collections import defaultdict
n=int(input())
a_=list(map(int,input().split()))
a=[]
for i,ai in enumerate(a_):
      a.append([1+i,ai])
a.sort(key=lambda x:x[1],reverse=True)
dp=defaultdict(lambda:0)
dp[(0,1)]=max(a[0][1]*(n-a[0][0]),0)
dp[(1,0)]=max(a[0][1]*(a[0][0]-1),0)
for i in range(2,n+1):#i人目の幼児。a[i-1]
      for x in range(i+1):
            y=i-x
            if x==0:
                  dp[(x,y)]=dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1))
            elif y==0:
                  dp[(x,y)]=dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1))
            else:
                  dp[(x,y)]=max(dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1)),dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1)))
ans=0
for i in range(n+1):
      ans=max(ans,dp[(i,n-i)])
print(ans)
yy,dd,mm = int(input().split('/'))
x = 0
if(yy<=2019):
  if(mm<=4):
    if(dd<=30):
     x = 1

if(x == 1):
  print('Heisei')
else:
  print('TBD')
    
  

### FIXED CODE ###

yy,mm,dd =map(int,input().split('/'))
x = 0
if(yy<=2019):
  if(mm<=4):
    if(dd<=30):
      x = 1
         
if(x == 1):
  print('Heisei')
else:
  print('TBD')
a, b, c = list(map(int, input().split()))
import math

if math.sqrtl(a) + math.sqrtl(b) < math.sqrtl(c):
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a, b, c = list(map(int, input().split()))

if c - a - b > 0 and 4 * a * b < (c - a - b) ** 2:
  print('Yes')
else:
  print('No')
import collections
n = int(input())
v = list(map(int, input().split()))
c_odd  = collections.Counter(v[::2])
c_even = collections.Counter(v[1::2])
odd    = c_odd.most_common()[:2]
even   = c_even.most_common()[:2]
if (len(odd) == 1) & (len(even) == 1):
	if odd[0][0] == even[0][0]:
		ans = odd[0][1]
	else:
		ans = 0
elif len(odd) == 1:
	if odd[0][0] == even[0][0]:
		ans = n - odd[0][1] - even[1][1]
	else:
		ans = n - odd[0][1] - even[0][1]
elif len(even) == 1:
	if odd[0][0] == even[0][0]:
		ans = n - odd[1][1] - even[0][1]
	else:
		ans = n - odd[0][1] - even[0][1]
print(ans)

### FIXED CODE ###

import collections
n = int(input())
v = list(map(int, input().split()))
c_odd  = collections.Counter(v[::2])
c_even = collections.Counter(v[1::2])
odd    = c_odd.most_common()[:2]
even   = c_even.most_common()[:2]
if (len(odd) == 1) & (len(even) == 1):
	if odd[0][0] == even[0][0]:
		ans = odd[0][1]
	else:
		ans = 0
elif len(odd) == 1:
	if odd[0][0] == even[0][0]:
		ans = n - odd[0][1] - even[1][1]
	else:
		ans = n - odd[0][1] - even[0][1]
elif len(even) == 1:
	if odd[0][0] == even[0][0]:
		ans = n - odd[1][1] - even[0][1]
	else:
		ans = n - odd[0][1] - even[0][1]
else:
	if odd[0][0] == even[0][0]:
		ans = min(n - odd[0][1] - even[1][1], n - odd[1][1] - even[0][1])
	else:
		ans = n - odd[0][1] - even[0][1]
print(ans)
def visit(u):
    global color, d, f, t
    color[u] = GRAY
    d[u] += t
    t += 1
    for v in range(n):
        if (M[u][v] == 0):
            continue
        else:
            if (color[v] == WHITE):
                visit(v)
    color[u] = BLACK
    f[u] = t
    t += 1

n = int(input())
M = [[False for i in range(n)] for i in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    for i in range(tmp[1]):
        M[tmp[0]-1][tmp[i+2]-1] = 1

WHITE = 0
GRAY = 1
BLACK = 2
color, d, f = [WHITE for i in range(n)]
t = 1
for u in range(n):
    if (color[u] == WHITE):
        visit(u)
for u in range(n):
    print(str(u+1), str(d[u]), str(f[u]), sep = " ")

### FIXED CODE ###

def dfs(u):
    global dfs_color, d, f, t
    color[u] = GRAY
    d[u] += t
    t += 1
    for v in range(n):
        if (M[u][v] == 0):
            continue
        else:
            if (color[v] == WHITE):
               dfs(v)
    color[u] = BLACK
    f[u] = t
    t += 1

n = int(input())
M = [[False for i in range(n)] for j in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(tmp[1]):
        M[tmp[0]-1][tmp[j+2]-1] = True

WHITE = 0
GRAY = 1
BLACK = 2
color = [WHITE for i in range(n)]
d = [0 for i in range(n)]
f = [0 for i in range(n)]
t = 1

for u in range(n):
    if (color[u] == WHITE):
        dfs(u)
for u in range(n):
    print(str(u+1), str(d[u]), str(f[u]), sep = " ")
from collections import *
h,w,n = map(int,input().split())
dic = defaultdict(int)
for _ in range(n):
  a,b = map(int,input().split())
  for i in range(9):
    dic[a - i //3,b - i % 3] += 1
ans =[0]*n
for i, j in dic:
  ans[dic[i,j]] += h-1 > i > 0 < j < w -1
ans[0] = (h -2)*(w-2) - sum(ans)
for item in ans:
  print(item)

### FIXED CODE ###

from collections import *
h,w,n = map(int,input().split())
dic = defaultdict(int)
for _ in range(n):
  a,b = map(int,input().split())
  for i in range(9):
    dic[a - i //3,b - i % 3] += 1
ans =[0]*10
for i, j in dic:
  ans[dic[i,j]] += h-1 > i > 0 < j < w -1
ans[0] = (h -2)*(w-2) - sum(ans)
for item in ans:
  print(item)
n = int(input())
p = [int(input()) for _ in range(n)]

p.sort()
print(sum(p[:-1] + p[-1] // 2))

### FIXED CODE ###

n = int(input())
p = [int(input()) for _ in range(n)]

p.sort()
print(sum(p[:-1]) + p[-1] // 2)
N,K =  list(map(int,input().split()))
listA = []
for i in range(K):listA.append(input())
listA.sort()
print("".join(listA))

### FIXED CODE ###

N,L =  list(map(int,input().split()))
listA = []
for i in range(N):listA.append(input())
listA.sort()
print("".join(listA))
N = int(input())
MOD = 10**9 + 7
memo = [{} for i in range(N+1)]

def ok(last4):
    for i in range(1,4):
        t = list(last4)
        t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') >=1:
            return False
    return True
        
def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1:
    ret = 0
    for c in "ATGC":
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0,'TTT'))



### FIXED CODE ###


N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for i in range(N+1)]
def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True
def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret
print(dfs(0, 'TTT'))
n = int(input())
w = [""] * n 
result = "Yes"

for i in range(n):
    tmp = input()
    if tmp in w:
        result = "No"
        break
    w[i] = tmp 
for i in range(n-1):
    if w[i][-1] == w[i+1][0]:
        pass
    else:
        result = "No"
print(result)

### FIXED CODE ###

n = int(input())
w = [""] * n 
result = "Yes"

for i in range(n):
    tmp = input()
    if tmp in w:
        result = "No"
    w[i] = tmp 
for i in range(n-1):
    if w[i][-1] == w[i+1][0]:
        pass
    else:
        result = "No"
print(result)
s=input()
t=input()
print(sum(1 for i in range(len(s)) if s[i] == l[i]))

### FIXED CODE ###

s=input()
t=input()
print(sum(1 for i in range(len(s)) if s[i] == t[i]))
import math
n, d = list(map(int, input().split()))
count = 0
for _ in range(n):
  x, y = list(map(int, input().split()))
  if math.sqrt(x**2 + y**2) >= d
  count += 1
print(count)

### FIXED CODE ###

import math
n, d = list(map(int, input().split()))
count = 0
for _ in range(n):
  x, y = list(map(int, input().split()))
  if math.sqrt(x**2 + y**2) <= d:
    count += 1
print(count)
import sys
import numpy as np

input = sys.stdin.readline


def main():
    X, N = list(map(int, input().split(" ")))
    if N==0:
        print(X)
        exit(0)
    arr = list(map(int, input().split(" ")))
    if X not in arr:
        print(X)

    arr.sort()
    for i in range(len(arr)):
        if arr[i] >= X:
            diff = 1
            while True:
                if X - diff not in arr:
                    print(X-diff)
                    exit(0)
                if X + diff not in arr:
                    print(X+diff)
                    exit(0)
                diff +=1


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline


def main():
    X, N = list(map(int, input().split(" ")))
    if N == 0:
        print(X)
        exit(0)
    arr = list(map(int, input().split(" ")))
    if X not in arr:
        print(X)
        exit(0)

    arr.sort()
    for i in range(len(arr)):
        if arr[i] >= X:
            diff = 1
            while True:
                if X - diff not in arr:
                    print(X - diff)
                    exit(0)
                if X + diff not in arr:
                    print(X + diff)
                    exit(0)
                diff += 1


if __name__ == '__main__':
    main()
N = input().split()

if N[0] == N[2]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

# coding: utf-8
# Your code here!

N = input()
 
if N[0] == N[2]:
  print('Yes')
else:
  print('No')
N, M = map(int, input().split())
AB = [[] for _ in range(M + 10)]
ans = 0
for _ in range(N):
  a, b = map(int, input().split())
  if a > m:
    continue
  AB[a].append(b)
import heapq
reward = []
heapq.heapify(reward)
for i in range(1, M + 1):
  for item in AB[i]:
    heapq.heappush(reward, -item)
  if reward:
    ans -= heapq.heappop(reward)
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
AB = [[] for _ in range(M + 10)]
ans = 0
for _ in range(N):
  a, b = map(int, input().split())
  if a > M:
    continue
  AB[a].append(b)
import heapq
reward = []
heapq.heapify(reward)
for i in range(1, M + 1):
  for item in AB[i]:
    heapq.heappush(reward, -item)
  if reward:
    ans -= heapq.heappop(reward)
print(ans)
N = input()
numN = int(N)
S =0
for i in range(len(N)):
    S += int(N[i])

if N % S == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N = input()
numN = int(N)
S =0
for i in range(len(N)):
    S += int(N[i])
 
if numN % S == 0:
    print('Yes')
else:
    print('No')
N, K=map(int,input().split())

fruit = list(input().split())
price = list(map(int, input().split()))

price2 = sorted(price)
i = 0
sum = 0
while (i < K):
  sum += price2[i]
  i += 1

print(sum)

### FIXED CODE ###

N, K=map(int,input().split())

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

price2 = sorted(price)
i = 0
sum = 0
while (i < K):
  sum += price2[i]
  i += 1

print(sum)
S = list(input())
T = list(input())

length = int(len(S))
difference = 0

for i in range(length):
    if S[i] != T[i]:
        difference = difference + 1

if difference%2 == 0:
    change = difference/2
if differenc%2 != 0:
    change = (difference+1)/2
    
print(str(change))

### FIXED CODE ###

S = list(input())
T = list(input())

length = int(len(S))
difference = 0

for i in range(length):
    if S[i] != T[i]:
        difference = difference + 1

   
print(str(difference))
import math
 
def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n, k = map(int, input().split())

if n == k:
  for i in range(1, k+1):
    if i == 1:
      print(1)
    else:
      print(0)
else:
  for i in range(1,k+1):
    p1 = combinations_count(n-k+1, i)
    p2 = combinations_count(k-1, i-1)
    ans = p1*p2
    ans = ans%(10**9+7)
    print(ans)
  
  

### FIXED CODE ###

import math
 
def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n, k = map(int, input().split())

if n == k:
  for i in range(1, k+1):
    if i == 1:
      print(1)
    else:
      print(0)
else:
  for i in range(1,k+1):
    if i <= n-k+1:
      p1 = combinations_count(n-k+1, i)
      p2 = combinations_count(k-1, i-1)
      ans = p1*p2
      ans = ans%(10**9+7)
      print(ans)
    else:
      print(0)
#!/bin/env python
  

if __name__=='__main__':
  val_n = input()
  list_v = list(map(int,input().split()))
  list_c = list(map(int,input().split()))

  answer = 0
  for i in range(len(list_v)):
    if(list_v[i] - list_c[i] > 0):
      answer += list_v[i] - list_c[i]
  print(answer)

### FIXED CODE ###

#!/bin/env python
  
import sys

def validate(input):
    if input < 0 or input > 20:
        return False
    return True

def biscuitGen(input_a, input_b, input_t):
    biscuits = 0
    if validate(input_a) and validate(input_b) and validate(input_t):
        biscuits = int(input_t / input_a) * input_b
    return biscuits

if __name__=='__main__':
    '''
    print how many biscuit will be generated 
    A: Seconds to generate biscuit
    B: Number of biscuit pieces to generate once
    T: Limit of the seconds to generate biscuit
    1 <= A,B,T <= 20
    '''
    biscuit = 0
    inarray = list(map(int,input().split()))
    if len(inarray) != 3:
        print("Please input 3 numbers")
        sys.exit()
    biscuit = biscuitGen(inarray[0], inarray[1], inarray[2])
    print(biscuit)
raw_input()
S = map(int, raw_input().split())
T = map(int, raw_input().split())
count = 0
for i in T:
    if(S in i):
        count += 1
print count

### FIXED CODE ###

raw_input()
S = map(int, raw_input().split())
raw_input()
T = map(int, raw_input().split())
count = 0
for i in T:
    if(i in S):
        count += 1
print count
n, m = map(int, input().split())
ans = ["-1" for i in range(n)]
for i in range(m):
    s, c = input().split()
    s = int(s)
    if s == 1 and c == '0':
        print(-1)
        exit()
    if ans[s-1] == "-1":
        ans[s-1] = c
    else:
        if ans[s-1] != c:
            print(-1)
            exit()
if ans[0] == '-1':
    ans[0] = 1
print(("".join(ans)).replace("-1","0"))


### FIXED CODE ###

n, m = map(int, input().split())
ans = ["-1" for i in range(n)]
for i in range(m):
    s, c = input().split()
    s = int(s)
    if s == 1 and c == '0' and n != 1:
        print(-1)
        exit()
    if ans[s-1] == "-1":
        ans[s-1] = c
    else:
        if ans[s-1] != c:
            print(-1)
            exit()
if ans[0] == '-1':
    ans[0] = "1"
if m == 0:
    ans[n-1] = "0"
print(("".join(ans)).replace("-1","0"))
N=int(input())
s=set()
for i in range(N):
  s^=｛input()｝
print(len(s))


### FIXED CODE ###

N=int(input())
s=set()
for i in range(N):
  a=int(input())
  if a in s:
    s.remove(a)
  else:
    s.add(a)
print(len(s))
N, M = map(int, input().split())
A = list(map(int, input().split()))
 
sum_A =0
for i in range(N):
    sum_A += A[i]
 
if (4*M*A[M] < sum_A):
    print('No')
else:
    print('Yes')

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
 
sum_A =0
for i in range(N):
    sum_A += A[i]

ans = 0
for i in range(N):
    if (4*M*A[i] >= sum_A):
        ans+=1
    else:
    	ans+=0
    	
if (ans >= M):
    print('Yes')
else:
    print('No')
A,B,K = map(int,input().split())
x = []
if A >= B:
  for i in range(1,A):
    if A % i == 0 and B % i == 0:
      x.append(i)
else:
  for i in range(1,B):
    if A % i == 0 and B % i == 0:
      x.append(i)
print(x[K - 1])
  

### FIXED CODE ###

a, b, k = map(int, input().split())
print([i for i in range(1,101) if a%i+b%i<1][-k])
i = 1
while n >= k**i:
    i += 1

print(i)

### FIXED CODE ###

n, k  = map(int, input().split())

i = 1
while n >= k**i:
    i += 1

print(i)
import sys
from functools import lru_cache


@lru_cache(maxsize=None)
def dfs(v):
    lv = links[v]
    return max(dfs(u) for u in lv) + 1 if lv else 0


n, m = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    sss.discard(y)
    links[x].add(y)

print(max(dfs(v) for v in sss))


### FIXED CODE ###

import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)


@lru_cache(maxsize=None)
def dfs(v):
    lv = links[v]
    return max(map(dfs, lv)) + 1 if lv else 0


n, m = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    sss.discard(y)
    links[x].add(y)

print(max(map(dfs, sss)))
A= int(input())
B= int(input())
C = int(input())

#575を作れるか判定
if A == B ==5 and C ==7:
    print('YES')
elif A ==C ==5 and B==7:
    print('YES')
elif A ==7 and B ==C ==5:
    print('YES')
    
else:
    print('NO')

### FIXED CODE ###

#ABC.042A
a,b,c = map(int,input().split())
if a ==b==5 and c ==7:
    print('YES')
elif a ==c==5 and b ==7:
    print('YES')
elif b==c==5 and a ==7:
    print('YES')
else:
    print('NO')
n = [int,input() for i in range(1,5)]

x = min(n[1], n[2])+ min(n[3], n[4])

print(x)

### FIXED CODE ###

l = [int(input()) for i in range(1, 5)]
print(min(l[0], l[1]) + min(l[2], l[3]))
n, k = map(int,input().split())
result = float("Inf")
length = 0
for i in range(N):
  a, b = map(int,input().split())
  if(length < k):
    length += b
    result = max(result, a)
  else:
    if(a < result):
      length += b
      if(length > k):
        result = a
print(result)

### FIXED CODE ###

import heapq
n, k = map(int,input().split())
hq = []
for i in range(n):
  heapq.heappush(hq, tuple(map(int, input().split())))
length = 0
while(length < k):
  a, b = heapq.heappop(hq)
  length += b
print(a)
#coding:utf-8
n = int(input())
blue = []
plus = [0]*n
for i in range(n):
    s = input()
    if s in blue:
        plus[blue.index(s)] += 1
    else:
        blue.append(s)
        plus[blue.index(s)] += 1
m = int(input())
for i in range(m):
    s = input()
    if s in blue:
        plus[blue.index(s)] -= 1
    else:
        blue.append(s)
        plus[blue.index(s)] -= 1
print(max(0, max(plus)))

### FIXED CODE ###

#coding:utf-8
n = int(input())
blue = []
plus = []
for i in range(n):
    s = input()
    if s in blue:
        plus[blue.index(s)] += 1
    else:
        blue.append(s)
        plus.append(1)
m = int(input())
for i in range(m):
    s = input()
    if s in blue:
        plus[blue.index(s)] -= 1
    else:
        blue.append(s)
        plus.append(-1)
print(max(0, max(plus)))
k=int(input())
x=int(input())
if x <= k :
  print("Yes")
else :
  print("No")

### FIXED CODE ###

k,x = map(int,input().split())
if x <= 500*k :
    print('Yes')
else :
    print('No')
n=int(input())
def lima():
    return list(map(int,input().split()))

a=lima()
b=lima()
c=lima()

sum=0
for i in range(n-1):
    sum+=b[a[i]-1]+c[a[i]-1]*(a[i]+1==a[i+1])

print(sum)

### FIXED CODE ###

n=int(input())
def lima():
    return list(map(int,input().split()))

a=lima()
b=lima()
c=lima()

sum=sum(b)
for i in range(n-1):
    if a[i]+1==a[i+1]:
        sum+=c[a[i]-1]        
print(sum)
def nCk(n, k):
    return bunbo(n,k)/bunshi(k)
def bunbo(n,k):
    p = 1
    for i in range(k):
        p = p*(n-i)
    return p
def bunshi(k):
    p = 1
    for i in range(k):
        p = p*(i+1)
    return p
    

N, M = map(int,input().split())
a=[-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
#print(a)
D=[]
for i in range(M+1):
    D.append((a[i+1]-1)-(a[i]+1))
#print(D)

ans=1
for i in range(len(D)):
    temp = 0
    for j in range(D[i]//2+1):
        temp += nCk(D[i]-j,j)
    ans=(ans%1000000007)*(temp%1000000007)
print(int(ans%1000000007))

### FIXED CODE ###

import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [-1]+ a+ [N+1]
fib = [0,1]
for i in range(10**5):
    fib.append((fib[-1]+fib[-2])%1000000007)
ans = 1
for i in range(len(b)-1):
    ans= (ans*fib[b[i+1]-b[i]-1])%1000000007
print(ans)
N,M=input().split()
N,M=[int(N),int(M)]
#M ga retu j
#N ga gyou i
status = [[1]*M]*N

#0 0 0 0 0 0 0
#print(status)

def countCard(j,i):
	#print("-------------")
	#print("status[{}][{}]={}".format(i,j,status[i][j]))
	count = 0
	left=0
	right=0
	up =0
	down=0

	if j-1 >= 0:
		left = 1

	if j+1 < M:
		right = 1

	if i-1 >= 0:
		up = 1

	if i+1 < N:
		down = 1

	a= left + right + up + down
	#print("left:{},right:{},up:{},down:{}".format(left,right,up,down))
	if a == 4:
		return 0	#9
	elif a == 3:
		return 1	#6
	elif a == 2:
		if left + right == 0 or up+down==0:
			return 0	#3
		else:
			return 1	#4
	elif a == 1:
		return 1	#2
	elif a == 0:
		return 0
	else:
		print('error')
		quit()

ans = 0
for i in range(N):
	for j in range(M):
		status[i][j] = countCard(j,i)
		ans += status[i][j]
		#print("status[{}][{}]={}".format(i,j,status[i][j]))


#print(status)

#for i in range(N):
#	ans += sum(status[i])
ans = (M*N) - ans
print(ans)

### FIXED CODE ###

N,M=input().split()
N,M=[int(N),int(M)]

def countCard(j,i):
	count = 0
	left=0
	right=0
	up =0
	down=0

	if j-1 >= 0:
		left = 1

	if j+1 < M:
		right = 1

	if i-1 >= 0:
		up = 1

	if i+1 < N:
		down = 1

	a= left + right + up + down
	if a == 4:
		return 0	#9
	elif a == 3:
		return 1	#6
	elif a == 2:
		if left + right == 0 or up+down==0:
			return 0	#3
		else:
			return 1	#4
	elif a == 1:
		return 1	#2
	elif a == 0:
		return 0

ans = 0

if M >= 3 and N >=3:
	ans = (M-2)*(N-2)
elif M == 1 and N ==1:
	ans = 1
elif N == 1 and M > 2:
	ans = M -2
elif M ==1 and N>2:
	ans = N-2
else:
	status = [[1]*M]*N
	for i in range(N):
		for j in range(M):
			status[i][j] = countCard(j,i)
			ans += status[i][j]
	ans = (M*N) - ans

print(ans)
print(input().replase('?', 'D'))

### FIXED CODE ###

print(input().replace('?', 'D'))
n = int(input())
l = list(map(int,input().split()))
m = []
for i in range(1,n+1):
  if l[i-1]>l[i]:
     m.append(l[i-1]-l[i])
    l[i-1],l[i] = l[i],l[i-1]

print(sum(m))
  


### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
m = []
for i in range(n-1):
  if l[i]>l[i+1]:
     m.append(l[i]-l[i+1])
     l[i+1] = l[i]

print(sum(m))
def myInput():
  n=input()
  s=input()
  return(n,[int(i) for i in s.split()])

def func():
  n, lst1 = nyInput()
  cnt = 0
  for i in range(1, int(n)-1):
    if min(lst[i+1],max(lst1[i],lst1[i-1])) == lst1[i]:
      cnt+=1
    elif min(lst1[i-1], max(lst1[i],lst1[i+1])) == lst1[i]:
      cnt+=1
  return cnt
print(func())

### FIXED CODE ###

def myInput():
  n = input()
  s = input()
  return (n, [int(i) for i in s.split()])

def func():
  n, lst1 = myInput()
  cnt = 0
  for i in range(1, int(n)-1):
    if min(lst1[i+1],max(lst1[i], lst1[i-1])) == lst1[i]:
      cnt+=1
    elif min(lst1[i-1],max(lst1[i],lst1[i+1])) == lst1[i]:
      cnt += 1
  return cnt
print(func())
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
BC = []
for _ in range(M):
  b,c = map(int,input().split())
  BC.append([b,c])

totals = [sum(A)]

for i in range(M):
  b = BC[i][0]
  part = A[:b]
  c = [BC[i][1]] * b
  print(part,c)
  if sum(part) < sum(c):
    left = c
    right = A[b:]
    total = sum(left) + sum(right)
    totals.append(total)
    
print(max(totals))

  

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]

A.sort()

#同じカードを書き換える操作は無駄なため、cが降順となるようにソート
BC.sort(key=lambda x:-x[1])

i = 0

for B,C in BC:
  for j in range(i,min(N,i + B)):
    if A[j] < C:
      A[j] = C
  #B枚分先を飛ばす BCはCに関して降順のため問題ない
  i = i + B

print(sum(A))
N=input()

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

Rate=[]
for i in range(9):
    Rate.append(0)

for i in A:
    index=i/400
    if index>8:
        index=8
    Rate[index]=Rate[index]+1

a=0

for i in range(8):
    if Rate[i]>0:
        a=a+1

Max=a+Rate[8]
Min=min(a,1)

print(Min, Max)



### FIXED CODE ###

import math
N=input()

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

Rate = []
for i in range(9):
    Rate.append(0)

for i in A:
    index=math.floor(i/400)
    if index > 8:
        index = 8
    Rate[index] = Rate[index] + 1

a = 0

for i in range(8):
    if Rate[i] > 0:
        a=a+1

Max = a + Rate[8]
Min = max(a, 1)

print(Min, Max)