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

import sys
#import numpy as np
import bisect
sys.setrecursionlimit(10 ** 7)

# TLE
# PyPy3 (2.4.0) 2112 ms

N, Q = map(int, input().split())
STX = []
for _ in range(N):
    s, t, x = map(int, input().split())
    STX.append((s, t, x))

PEOPLE = []
for i in range(Q):
    d = int(input())
    PEOPLE.append((d, i))

ans = [-1] * Q

STX.sort(key=lambda x: x[2])

for s, t, x in STX:
    if len(PEOPLE) == 0:
        break

    i = bisect.bisect_left(PEOPLE, (s - x, -1))
    j = bisect.bisect_left(PEOPLE, (t - x, -1))

    if i == j:
        continue

    use = [PEOPLE[x][1] for x in range(i, j)]

    #print(len(PEOPLE), use)
    for k in use:
        if ans[k] == -1:
            ans[k] = x

    del PEOPLE[i:j]


print("\n".join(map(str, ans)))


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

print('\n'.join(map(str,answer)))
### BUGGY CODE ###

import itertools
import sys
input = sys.stdin.readline
k,s=map(int,input().split())
x=[x for x in range(0,k+1)]
y=[y for y in range(0,k+1)]
z=[z for z in range(0,k+1)]
data=list(itertools.product(x,y,z))
ans=[sum(i) for i in (data)]
print(ans.count(s))

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <= k and x+y+z == s:
            ans += 1
print(ans)
### BUGGY CODE ###

s=input().rstrip();mod=10**9+7
dp = [[0]*13for _ in range(len(s)+1)]
dp[0][0]=1
for i in range(len(s)):
  if s[i]=='?':
    for j in range(13):
      for k in range(10):
        dp[i+1][(10*j+k)%13] += dp[i][j]
        dp[i+1][(10*j+k)%13] %= mod
  else:
    for j in range(13):
      dp[i+1][(10*j+int(s[i]))%13] += dp[i][j]
      dp[i+1][(10*j+int(s[i]))%13] %= mod
print(dp[len(s)][5])

### FIXED CODE ###

s=input();mod=10**9+7
dp = [[0]*13for _ in range(len(s)+1)]
dp[0][0]=1
for i in range(len(s)):
  if s[i]=='?':
    for j in range(13):
      for k in range(10):
        dp[i+1][(10*j+k)%13] += dp[i][j]
        dp[i+1][(10*j+k)%13] %= mod
  else:
    for j in range(13):
      dp[i+1][(10*j+int(s[i]))%13] += dp[i][j]
      dp[i+1][(10*j+int(s[i]))%13] %= mod
print(dp[len(s)][5])
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]

word_list=list(map(lambda x: ''.join(sorted(x)),S))

import itertools
word_set=set(word_list)
total_counts=[]
for word in word_set:
  num = len(list(itertools.combinations(range(word_list.count(word)),2)))
  total_counts.append(num)
  
print(sum(total_counts))

### FIXED CODE ###

N = int(input())
S = [input() for i in range(N)]

list = {}
for i in S:
  i=''.join(sorted(i))
  if i in list:
    list[i] = list[i] + 1
  else:
    list[i] = 1

count = 0
for i in list.values():
  n = i - 1
  count = count + int(((n * (n + 1)) / 2))
  
print(count)
### BUGGY CODE ###

import sys

H, W = map(int, input().split())
s = []
nb = 0
for _ in range(H):
    s.append(list(input()))
    nb += s[-1].count("#")

nw = H * W - nb

sy, sx = 0, 0
gy, gx = H - 1, W - 1

# たどりつけない場合
if s[gy - 1][gx] == "#" and s[gy][gx - 1] == "#":
    print(-1)
    sys.exit()

q = [[sy, sx]]
visited = [[int(1e10)]*W for _ in range(H)]
visited[sy][sx] = 0
counter = 0
while True:
    nq = []
    counter += 1
    for ty, tx in q:
        if [gy, gx] in q:
            break
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ny, nx = ty + dy, tx + dx
            if 0 <= ny < H and 0 <= nx < W and s[ny][nx] == "." and visited[ny][nx] > counter:
                visited[ny][nx] = counter
                nq.append([ny, nx])
                if ny == gy and nx == gx:
                    break
    q = nq
    if [gy, gx] in q:
        temp = visited[gy][gx]
        break

print(nw - temp - 1)

### FIXED CODE ###

H, W = map(int, input().split())
s = []
nb = 0
for _ in range(H):
    s.append(list(input()))
    nb += s[-1].count("#")

nw = H * W - nb

sy, sx = 0, 0
gy, gx = H - 1, W - 1

q = [[sy, sx]]
visited = [[int(1e10)]*W for _ in range(H)]
visited[sy][sx] = 0
while q:
    ty, tx = q.pop(0)
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = ty + dy, tx + dx
        if 0 <= ny < H and 0 <= nx < W and s[ny][nx] != "#":
            if visited[ny][nx] > visited[ty][tx] + 1:
                visited[ny][nx] = visited[ty][tx] + 1
                q.append([ny, nx])
    if [gy, gx] in q:
        temp = visited[gy][gx]
        break
if visited[gy][gx] == int(1e10):
    print(-1)
else: print(nw - temp - 1)
### BUGGY CODE ###

#
import sys
import math
import numpy as np
import itertools

n = int(input())
a=[]
b=[]
c=[]
d=[]
for j in range(0,n):
    t1,t2,t3,t4 = (int(i) for i in input().split())  
    a.append(t1)
    b.append(t2)
    c.append(t3)
    d.append(t4)
    
for i in range(0,n):
    if a[i] < b[i]:
        print("No")
    elif d[i] < b[i]:
        print("No")
    else:
        flag=1
        for j in range(0,b[i]):
            p= (a[i]+j*d[i]) % b[i]
            if p > c[i] and p != 0 :
                flag=0
                break
        if flag == 1:
            print("Yes")
        else:
            print("No")
    



### FIXED CODE ###

#
import sys

n = int(input())
a=[]
b=[]
c=[]
d=[]
for j in range(0,n):
    t1,t2,t3,t4 = (int(i) for i in input().split())  
    a.append(t1)
    b.append(t2)
    c.append(t3)
    d.append(t4)
    
for i in range(0,n):
    if a[i] < b[i]:
        print("No")
    elif d[i] < b[i]:
        print("No")
    else:
        p= b[i]
        q= d[i]
        while p%q :
            r=q
            q=p%q
            p=r
        if (b[i]-q)+a[i]%q > c[i]:
            print("No")
        else:
            print("Yes")
### BUGGY CODE ###

import sys
import heapq
n, m = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
for i in range(n):
    A[i] = -A[i]
heapq.heapify(A)
#(A)
for j in range(m):
    A[0] = int(A[0]/2)
    #print(A)
    heapq.heapify(A)

print(-sum(A))

### FIXED CODE ###

import sys
import heapq
n, m = map(int, sys.stdin.readline().split())
A = list(map(lambda x:-int(x), sys.stdin.readline().split()))
heapq.heapify(A)

for j in range(m):
    heapq.heappush(A ,int(A[0]/2))
    heapq.heappop(A)

print(-sum(A))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def f(c1, c2, c3):
    if dp[c1][c2][c3] != -1:
        return dp[c1][c2][c3]

    s = c1 + c2 + c3

    res = n
    if c1 > 0:
        res += f(c1 - 1, c2, c3) * c1
    if c2 > 0:
        res += f(c1 + 1, c2 - 1, c3) * c2
    if c3 > 0:
        res += f(c1, c2 + 1, c3 - 1) * c3
    res /= s
    dp[c1][c2][c3] = res
    return res


n = int(input())
a = tuple(map(int, input().split()))

c1 = a.count(1)
c2 = a.count(2)
c3 = a.count(3)

dp = tuple(
    tuple(
        [-1] * (n + 1) for _ in range(n + 1)
    ) for _ in range(n + 1))
dp[0][0][0] = 0
# dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

print(f(c1, c2, c3))

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p


### FIXED CODE ###

def main():
    from collections import Counter

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              / (r1 + r2 + r3)

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした
# resの加算を複数回に分けると
# 三項演算子より遅くなる
# 再帰関数を辞めた
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
pow2 = [1]
for i in range(31):
    pow2.append(pow2[-1] * 2)
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    if d[a[i]] == 0:
        continue
    for k in range(30, -1, -1):
        if pow2[k] - a[i] != a[i]:
            if d[pow2[k] - a[i]] > 0 and d[a[i]] > 0:
                p = min(d[pow2[k] - a[i]], d[a[i]])
                num += p
                d[pow2[k] - a[i]] -= p
                d[a[i]] -= p
                break
        else:
            if d[a[i]] >= 2:
                num += d[a[i]] // 2
                d[a[i]] %= 2
                break
print(num)


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
pow2 = [1]
for i in range(31):
    pow2.append(pow2[-1] * 2)
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    if d[a[i]] == 0:
        continue
    for k in range(30, -1, -1):
        inv = pow2[k] - a[i]
        if inv < 0 or inv > a[i]:
            continue
        if inv != a[i]:
            if d[inv] > 0 and d[a[i]] > 0:
                p = min(d[inv], d[a[i]])
                num += p
                d[inv] -= p
                d[a[i]] -= p
                break
        else:
            if d[a[i]] >= 2:
                num += d[a[i]] // 2
                d[a[i]] %= 2
                break
print(num)
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))
d = np.inf
dp = np.array([d] * N)
dp[0] = 0
cc = np.arange(1, N)
for i in cc:
  j = i - min(i, K)
  dp[i] = min(dp[j:i]+np.abs(h[i]-h[j:i]))
print(int(dp[N-1]))

### FIXED CODE ###

import sys
import numpy as np

# inputを高速化する。
input = sys.stdin.readline

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

# dpの配列を作る。
dp = np.zeros(n, dtype=int)
# hの配列を作る。
h = np.array(h)


for i in range(1, n):
    # start は負になることはない。
    start = max(0, i-k)
    # 行列として足し算できるのでforを使う必要がない。
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

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

import numpy as np
import time

n = int(input())
aaa = np.fromiter(map(int, input().split()), np.int64)
bbb = np.fromiter(map(int, input().split()), np.int64)
st = time.time()

while time.time() - st < 1.9:
    np.random.shuffle(bbb)
    if (aaa != bbb).all():
        print('Yes')
        print(*bbb)
        exit()

print('No')


### FIXED CODE ###

from itertools import groupby

n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))

idx_a = {}
cnt_a = {}
i = 0
for a, itr in groupby(aaa):
    cnt = len(list(itr))
    i += cnt
    idx_a[a] = i
    cnt_a[a] = cnt

idx_b = {}
cnt_b = {}
i = 0
for b, itr in groupby(bbb):
    cnt = len(list(itr))
    idx_b[b] = i
    cnt_b[b] = cnt
    i += cnt

slide = 0
for a in idx_a:
    if a not in idx_b:
        continue
    if cnt_a[a] + cnt_b[a] > n:
        print('No')
        exit()
    slide = max(slide, idx_a[a] - idx_b[a])

print('Yes')
if slide > 0:
    bbb = bbb[-slide:] + bbb[:-slide]
print(*bbb)
### BUGGY CODE ###

s=input()
q=int(input())
querys=[0]*q
for i in range(q):
  x = input().split()
  if len(x) == 1:
    querys[i] = [int(x[0])]
  else:
    querys[i] = [int(x[0]), int(x[1]), x[2]]
trans=0
for query in querys:
  if query[0]==1:
    trans += 1
  elif (query[1] & 1) ^ (trans & 1):
    s = query[2] + s
  else: # 後
    s += query[2]
res = ''
if trans % 2 == 0:
  res = s
else:
  res = ''.join([s[len(s)-i-1] for i in range(len(s))])
print(res)

### FIXED CODE ###

#import time
#t1=time.time()
s=input()
q=int(input())
trans=0
head=''
#t2=time.time()
for i in range(q):
  query = input().split()
  if query[0]=='1':
    trans += 1
  elif (int(query[1]) & 1) ^ (trans & 1):
    head += query[2]
  else:
    s += query[2]
res = ''
#t3=time.time()
if trans % 2 == 0:
  res = ''.join([head[len(head)-i-1] for i in range(len(head))]) + s
else:
  res = ''.join([s[len(s)-i-1] for i in range(len(s))]) + head
print(res)
#t4=time.time()
#print(int((t2-t1)*1000),int((t3-t2)*1000),int((t4-t3)*1000),int((t4-t1)*1000))
### BUGGY CODE ###

import fractions
from functools import reduce


n, m = map(int, input().split())
A = list(set(map(int, input().split())))


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


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


hA = [a//2 for a in A]
lcm = lcm_list(hA)

for a in A:
    if lcm % a == 0:
        print(0)
        break
else:
    if (m//lcm) % 2 == 0:
        print(m//lcm//2)
    else:
        print(m//lcm//2 + 1)


### FIXED CODE ###

import fractions
from functools import reduce


n, m = map(int, input().split())
A = list(set(map(int, input().split())))

hA = [a//2 for a in A]
lcm = 1
for a in hA:
    lcm = (lcm * a) // fractions.gcd(lcm, a)
    if lcm > m:
        print(0)
        break
else:
    for a in A:
        if lcm % a == 0:
            print(0)
            break
    else:
        if (m//lcm) % 2 == 0:
            print(m//lcm//2)
        else:
            print(m//lcm//2 + 1)
### BUGGY CODE ###

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

A = [int(i) for i in input().split()]

L = []
for i in range(m):
    b,c = map(int, input().split())
    L.append((b,c))
    
A = sorted(A)

from bisect import bisect_left
for l in L:
    tmp0 = l[0]
    tmp1 = l[1]
    A_len = bisect_left(A, tmp1)
    if tmp0 < A_len:
        A = A[tmp0:A_len]+[tmp1 for i in range(tmp0)]+A[A_len:]
    else:
        A = [tmp1 for i in range(A_len)]+A[A_len:]
        
        
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]

D = {}
for i in range(M):
    b,c = map(int, input().split())
    if c in D:
        D[c] += b
    else:
        D[c] = b
        
for a in A:
    if a in D:
        D[a] += 1
    else:
        D[a] = 1
        
D_sort = sorted(D.items(), reverse=True)
check = 0
ans = 0
for d in D_sort:
    check += d[1]
    if check <= N:
        ans += d[0] * d[1]
    else:
        ans += d[0] * (d[1] - (check - N))
        break
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

A,B,Q = map(int, input().split())

s = [int(input()) for i in range(A)]
t = [int(input()) for i in range(B)]
x = [int(input()) for i in range(Q)]

for i in x : 
    min_s = abs(i -s[0])
    j_count = 0
    j_k_count = 0
    min_t = abs(i -t[0])
#    min_t_s = abs(i -s[0])
    k_count = 0
    k_j_count = 0
#Sから攻める
    for j in s : 
        if abs(i-j) <= min_s : 
            min_s = abs(i-j)
            j_count = j
            
    min_s_t = abs(j_count -t[0])
            
    for k in t : 
        if abs(j_count-k) <= min_s_t : 
            min_s_t = abs(j_count-k)
            j_k_count = k
    min0 = abs(i-j_count)+abs(j_count-j_k_count)

# ---------------------------------------------

    for m in t : 
        if abs(i-m) <= min_t : 
            min_t = abs(i-m)
            m_count = m
            
    min_t_s = abs(m_count -s[0])
            
    for n in s : 
        if abs(m_count-n) <= min_t_s : 
            min_t_s = abs(m_count-n)
            m_n_count = n
    min1 = abs(i-m_count)+abs(m_count-m_n_count)

#小さい方採用

    print(min(min0, min1))
    

### FIXED CODE ###

import bisect

A, B, Q = map(int, input().split())
INF = 10 ** 18

s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]


for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b-1], s[b]] : 
        for T in [t[d-1], t[d]] : 
            d1, d2 = abs(S-x) + abs(T-S), abs(T-x) + abs(S-T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
sys.setrecursionlimit(10 ** 7)

def main():
    s = ns()
    Q = ni()

    T1 = 0
    FrontS = ""
    BackS = ""
    for _ in range(Q):
        T = stdin.readline().split()
        if T[0] == "1":
            T1 += 1
        else:
            if T1 % 2 == 0:
                # これは元通り
                
                s = FrontS + s + BackS
                FrontS = ""
                BackS = ""

                if T[1] == "1":
                    FrontS = T[2] + FrontS
                else:
                    BackS += T[2]
            else:
                # これは逆向き

                s = FrontS + s + BackS
                FrontS = ""
                BackS = ""
                
                if T[1] == "1":
                    BackS = T[2] + BackS
                else:
                    FrontS = T[2] + FrontS
    
    if BackS != "":
        s += BackS
    if FrontS != "":
        s = FrontS + s

    if T1 % 2 == 0:
        print(s)
    else:
        print(s[::-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
sys.setrecursionlimit(10 ** 7)

def main():
    s = ns()
    Q = ni()

    T1 = 0
    FrontS = ""
    BackS = ""
    for _ in range(Q):
        T = stdin.readline().split()
        if T[0] == "1":
            FrontS, BackS = BackS, FrontS
            T1 += 1
        else:
            if T[1] == "1":
                FrontS += T[2]
            else:
                BackS += T[2]
                
    FrontS = FrontS[::-1]

    if T1 % 2 == 0:
        print(FrontS + s + BackS)
    else:
        print(FrontS + s[::-1] + BackS)

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

import numpy as np
n=int(input())
P=np.array(list(map(float,input().split())))
DP=np.zeros(n+1)
DP[0]=1.0

for i in range(n):
  D=np.zeros(n+1)
  p=P[i]
  for j in range(i+2):
    D[j] = DP[j-1] * p + DP[j] * (1-p)
  DP=D
print(sum(DP[n//2+1:]))

### FIXED CODE ###

import numpy as np
n=int(input())
P=np.array(list(map(float,input().split())))
DP=np.zeros(n+1)
DP[0]=1.0

for i in range(n):
  DP = np.roll(DP * P[i], 1) + DP * (1-P[i])
print(sum(DP[n//2+1:]))
### BUGGY CODE ###

N=int(input())
actlist=list(map(int,input().split()))
As = sorted([(A, i) for i, A in enumerate(actlist)])[::-1]

INF = float('inf')
left=1
right=N
maxnum=0

dp = [[-INF] * (N+1) for _ in range(N+1)]

for r in range(N+1):
    for l in range(N-r+1):
        if r==0 and l==0:
            dp[l][r]=0
        else:
            dp[l][r]=max(dp[l][r-1]+As[l+r-1][0]*abs(N-r-As[l+r-1][1]),\
              dp[l-1][r]+As[l+r-1][0]*abs(l-1-As[l+r-1][1]))

for m in range(N):
    if(dp[m][N-m] > maxnum):
        maxnum = dp[m][N-m]
    
print(maxnum)

### FIXED CODE ###

def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)
 
  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0
 
  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)
 
main()
### BUGGY CODE ###

N = int(input())
ans = {}
for i in range(N):
    a = input()
    ans[a] = ans.get(a,0) + 1

ans2 = [k for k, v in ans.items() if v == max(ans.values())]
ans2.sort()
[print(i) for i in ans2]


### FIXED CODE ###

N = int(input())
ans = {}
for i in range(N):
    a = input()
    ans[a] = ans.get(a,0) + 1

t = max(ans.values())
ans2 = [k for k, v in ans.items() if v ==t ]
ans2.sort()
[print(i) for i in ans2]
### BUGGY CODE ###

#https://atcoder.jp/contests/abc110/tasks/abc110_c

s = list(str(input()))
t = list(str(input()))
u = []
v = []
flag = 'Yes'


for i in range(len(s)):
    for j in range(i+1, len(s)):
        if s[i] == s[j] and t[i] != t[j]:
            flag = 'No'
            break
        elif t[i] == t[j] and s[i] != s[j]:
            flag = 'No'
            break
    if flag == 'No':
        break

print(flag)


### FIXED CODE ###

import sys
s = str(input())
t = str(input())
l = len(s)
tmp = [[], []]
for i in range(l):
    if (not s[i] in tmp[0]) and (not t[i] in tmp[1]):
        tmp[0].append(s[i])
        tmp[1].append(t[i])
    else:
        if s[i] in tmp[0]:
            tmp2 = 0
            for j in range(len(tmp[0])):
                if s[i] == tmp[0][j]:
                    tmp2 = j
            if t[i] != tmp[1][tmp2]:
                print('No')
                sys.exit()
        else:
            print('No')
            sys.exit()
print('Yes')
### BUGGY CODE ###

import math
import collections
import fractions
import itertools
import functools
import operator

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    ruiseki = [1]
    for i in range(1, n+1):
        ruiseki.append(a[i-1]*ruiseki[i-1])
    for i in range(k-1, n-1):
        if ruiseki[i+1]//ruiseki[i-k+1] >= ruiseki[i+2]//ruiseki[i+2-k]:
            print("No")
        else:
            print("Yes")
    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###

import math
import collections
import fractions
import itertools
import functools
import operator

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(k, n):
        print("Yes") if a[i] > a[i-k] else print("No")
    return 0

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

#!/usr/bin/env python3
N = int(input())

def solve():
    for h in range(1, 3501):
        for w in range(1, 3501):
            a = N * h * w
            b = 4 * h * w - N * h - N * w
            if b < 1:
                continue
            n = a / b
            if n == int(n):
                print(h, int(n), w)
                return

solve()


### FIXED CODE ###

#!/usr/bin/env python3
N = int(input())

def solve():
    for h in range(1, 3501):
        for w in range(h, 3501):
            a = N * h * w
            b = 4 * h * w - N * h - N * w
            if b < 1:
                continue
            n = a / b
            if n == int(n):
                print(h, int(n), w)
                return

solve()
### BUGGY CODE ###

n = int(input())
s = []
for i in range (n):
    a = input()
    if a not in s:
        s.append(a)
print(len(s))

### FIXED CODE ###

n = int(input())
s = []
for i in range (n):
    s.append(input())
ss = sorted(s)
count = 1
for i in range(n-1):
    if ss[i] != ss[i + 1]:
        count += 1
print(count)