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

r, c = map(int, input().split())
ans = 0

map = []
for i in range(r):
    map.append(input())

L = [[0]*c for i in range(r)]
R = [[0]*c for i in range(r)]
D = [[0]*c for i in range(r)]
U = [[0]*c for i in range(r)]

for i in range(r):
    for j in range(c):
        if map[i][j] == ".":
            L[i][j] = L[i][j - 1] + 1
        else:
            L[i][j] = 0
for i in range(r):
    for j in range(c - 1, -1, -1):
        if j == c - 1:
            if map[i][j] == ".":
                R[i][j] = 1
            continue
        if map[i][j] == ".":
            R[i][j] = R[i][j + 1] + 1
        else:
            R[i][j] = 0
for i in range(r):
    for j in range(c):
        if map[i][j] == ".":
            D[i][j] = D[i - 1][j] + 1
        else:
            D[i][j] = 0
for i in range(r - 1, -1, -1):
    for j in range(c):
        if i == r - 1:
            if map[i][j] == ".":
                U[i][j] = 1
            continue
        if map[i][j] == ".":
            U[i][j] = U[i + 1][j] + 1
        else:
            U[i][j] = 0

for i in range(r):
    for j in range(c):
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

print(ans)

### FIXED CODE ###

r, c = map(int, input().split())
ans = 0

map = []
for i in range(r):
    map.append(input())

L = [[0]*c for i in range(r)]
R = [[0]*c for i in range(r)]
D = [[0]*c for i in range(r)]
U = [[0]*c for i in range(r)]

for i in range(r):
    for j in range(c):
        if map[i][j] == ".":
            L[i][j] = L[i][j - 1] + 1
        else:
            L[i][j] = 0
for i in range(r):
    for j in range(c - 1, -1, -1):
        if j == c - 1:
            if map[i][j] == ".":
                R[i][j] = 1
            continue
        if map[i][j] == ".":
            R[i][j] = R[i][j + 1] + 1
        else:
            R[i][j] = 0
for i in range(r):
    for j in range(c):
        if map[i][j] == ".":
            D[i][j] = D[i - 1][j] + 1
        else:
            D[i][j] = 0
for i in range(r - 1, -1, -1):
    for j in range(c):
        if i == r - 1:
            if map[i][j] == ".":
                U[i][j] = 1
            continue
        if map[i][j] == ".":
            U[i][j] = U[i + 1][j] + 1
        else:
            U[i][j] = 0

for i in range(r):
    for j in range(c):
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

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

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

# M回の握手の幸福度最大化
# X以上になる握手を全て採用したときに、M通りを越える
# Xの最大値を求める

import bisect

ok=-1
ng=(10**10)+2

# x以上の握手をm通り以上作れるか
def isOk(x,m):
  cnt=0
  # 左手をループする
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    # minright以上の数を数える
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOk(mid,m):
    ok=mid
  else:
    ng=mid

x=ok
# x以上となる幸福度を足し合わせる
# 足し合わせた握手がMを越える場合、xぴったりを足し過ぎている

# 効率化のため累積和を作成
Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  
# Aの添字i以降を全て足すときは、
# Asum[-1]-Asum[i]

ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)


### FIXED CODE ###

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

# M回の握手の幸福度最大化
# X以上になる握手を全て採用したときに、M通りを越える
# Xの最大値を求める

import bisect

ok=-1
ng=(10**10)+2

# x以上の握手をm通り以上作れるか
def isOk(x,m):
  cnt=0
  # 左手をループする
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    # minright以上の数を数える
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOk(mid,m):
    ok=mid
  else:
    ng=mid

x=ok
# x以上となる幸福度を足し合わせる
# 足し合わせた握手がMを越える場合、xぴったりを足し過ぎている

# 効率化のため累積和を作成
Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  
# Aの添字i以降を全て足すときは、
# Asum[-1]-Asum[i]

ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)
### BUGGY CODE ###

A, B, K = map(int, input().split())
for num in range(A, B+1):
  if num <= A+K-1 or num >= B-K+1:
    print(num)
    


### FIXED CODE ###

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

nums = []
for num in range(A, min(A+K, B+1)):
  nums.append(num)
for num in range(max(B-K+1, A), B+1):
  if not num in nums:
    nums.append(num)
nums.sort()
for num in nums:
  print(num)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
T = [input()[::-1].strip() for i in range(N)]

class TrieTree:
    class Node:
        def __init__(self):
            self.ch = defaultdict(TrieTree.Node)
            self.cnt = 0
            self.end = False

    def __init__(self):
        self.root = self.Node()

    def register(self,word):
        node = self.root
        for w in word:
            node.cnt += 1
            node = node.ch[w]
        node.cnt += 1
        node.end = True
    
    def prefix(self, word):
        node = self.root
        for w in word:
            if w not in node.ch:
                return False
            else:
                node = node.ch[w]
        return node

tt = TrieTree()
for word in T:
    tt.register(word)

ans = 0
for word in T:
    pre = word[:-1]
    last = word[-1]
    node = tt.prefix(pre)
    if not node:
        continue
    df = [node]
    while df:
        node = df.pop()
        for c, nnode in node.ch.items():
            if c == last:
                ans += node.ch[last].cnt
            else:
                df.append(nnode)
    ans -= 1
    
print(ans)



### FIXED CODE ###

import sys
import string
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
T = [input()[::-1].strip() for i in range(N)]

#N = 100
#M = 10000
#import random
#import string
#T = [''.join(random.choices(string.ascii_lowercase, k=random.randint(M,M))) for i in range(N)]

class TrieTree:
    class Node:
        def __init__(self):
            #self.clue = defaultdict(int)
            self.clue = [0]*26
            self.ch = defaultdict(TrieTree.Node)
            self.cnt = 0
            self.end = False

    def __init__(self):
        self.root = self.Node()

    def register(self,word):
        node = self.root
        for w in word:
            node.cnt += 1
            node = node.ch[w]
        node.cnt += 1
        node.end = True
    
    def prefix(self, word):
        node = self.root
        for w in word:
            if w not in node.ch:
                return False
            else:
                node = node.ch[w]
        return node

tt = TrieTree()
for word in T:
    tt.register(word)

route = []

st = [tt.root]
while st:
    node = st.pop()
    route.append(node)
    st.extend(node.ch.values())

f = lambda c : ord(c)-97
for node in route[::-1]:
    for c,nnode in node.ch.items():
        for i,v in enumerate(nnode.clue):
            node.clue[i] += v
        node.clue[f(c)] += nnode.cnt - nnode.clue[f(c)]

ans = 0
for word in T:
    pre = word[:-1]
    last = word[-1]
    node = tt.prefix(pre)
    if not node:
        continue
    ans += node.clue[f(last)] - 1
    
print(ans)
### BUGGY CODE ###

s = input()
k = int(input())

index = []

for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        jyuhuku = 0
        for a in index:
            if(a == s[i:j]):
                jyuhuku = 1
        if(jyuhuku == 0):
            index.append(s[i:j])
    

print(sorted(index)[k-1])


### FIXED CODE ###

s = input()
k = int(input())

index = []

for i in range(len(s)):
    for j in range(i+1,i+k+1):
        index.append(s[i:j])
    
print(sorted(list(set(index)))[k-1])
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if l[k] - l[j] < l[i]:
                ans += 1
            else:
                break
print(ans)

### FIXED CODE ###

from bisect import bisect_left,bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
#c - b < a < c + b
for i in range(n-1):
    for j in range(i+1,n):
        sahen = bisect(l,l[j]-l[i])
        uhen = bisect_left(l,l[j]+l[i])
        ans += uhen - sahen
        if sahen <= i <= uhen -1:
            ans -= 1
        if sahen <= j <= uhen -1:
            ans -= 1
print(ans//3)
### BUGGY CODE ###

N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= K:
    print(0)
    exit()

a = [a[i] for i in range(N) if a[i]<K]
a.reverse()
N = len(a)
ans = N
dp = [False]*K
dp[0] = True
Smax = 0
for i,a_ in enumerate(a):
    if Smax + a_ >= K:
        ans = N-i-1
    updated = True
    for j in range(min(Smax,K-a_-1),-1,-1):
        if dp[j]:
            dp[j+a_]=True
            if updated:
                Smax = max(Smax,j+a_)
                updated = False

print(ans)

### FIXED CODE ###

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

def f(N,K,a):
    a.sort()
    if a[0] >= K:
        print(0)
        exit()

    a = [a[i] for i in range(N) if a[i]<K]
    N = len(a)
    ans = N
    dp = [False]*K
    dp[0] = True
    Smax = 0
    for i,a_ in reversed(list(enumerate(a))):
        if Smax + a_ >= K:
            ans = i
        updated = True
        for j in range(min(Smax,K-a_-1),-1,-1):
            if dp[j]:
                dp[j+a_]=True
                if updated:
                    Smax = max(Smax,j+a_)
                    updated = False
    return ans

print(f(N,K,a))
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
a_list_min = sorted(a_list)
cnt = 0

#print(a_list_min)

for i in range(0, n):
    for j in range(i+1):
        if i != n-1 and a_list_min[i] == a_list_min[i+1]:
            break
        if j == i:
            cnt += 1
            break
        if a_list_min[i] % a_list_min[j] == 0:
            break
#                print(i,j)

print(cnt)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

A = set(A)
MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if (X[a] == 1) and (C[a] == 1)])
print(ans)
### BUGGY CODE ###

n = int(input())
H = list(map(int,input().split()))
ans = 0

for i in range(n):
    tmp = 0
    for j in range(i,n):
        if j == i:
            continue
        if H[j] <= H[j-1]:
            tmp += 1
        else:
            break
    ans = max(ans,tmp)

print(ans)

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
ans = 0
tmp = 0

for i in range(n-1):
    if h[i+1] <= h[i]:
        tmp += 1
    else:
        ans = max(ans,tmp)
        tmp = 0

print(max(ans,tmp))
### BUGGY CODE ###

N, M = map(int, input().split()) 
HEIGHT = list(map(int, input().split()))
tenbou = list(range(1,N+1))
for i in range(M):
    hasi1, hasi2 = map(int, input().split())
    #橋の両端の標高を比較し、低かったほうは除外する
    if HEIGHT[hasi1-1] > HEIGHT[hasi2-1] and hasi2 in tenbou:
        tenbou.remove(hasi2)
        #print(tenbou)
    elif HEIGHT[hasi1-1] < HEIGHT[hasi2-1] and hasi1 in tenbou:
        tenbou.remove(hasi1)
        #print(tenbou)
    elif HEIGHT[hasi1-1] == HEIGHT[hasi2-1]:
        if hasi1 in tenbou:
            tenbou.remove(hasi1)
        if hasi2 in tenbou:
            tenbou.remove(hasi2)
       #print(tenbou)
print(len(tenbou))

### FIXED CODE ###

N, M = map(int, input().split()) 
HEIGHT = list(map(int, input().split()))
MA = []
for i in range(N):
    MA.append(0)
for i in range(M):
    hasi1, hasi2 = map(int, input().split())
    #print(max(MA[hasi1-1], HEIGHT[hasi2-1]))
    MA[hasi1-1] = max(MA[hasi1-1], HEIGHT[hasi2-1])
    MA[hasi2-1] = max(MA[hasi2-1], HEIGHT[hasi1-1])
    #間違い：リストの要素　〇LIST[i]　×LIST(i)
    #MA.insert(hasi1-2,max(MA[hasi1-2], HEIGHT(hasi1-1)))
result = 0
for i in range(N):
    if HEIGHT[i] > MA[i]:
        result += 1
print(result)
### BUGGY CODE ###

N = int(input())
emp = list(map(int,input().split()))
def rem_val(arr, value):
    while value in arr:
        try:
            arr.remove(value)
        except:
            break
for i in range(N):
    print(emp.count(i+1))
    rem_val(emp,i+1)


### FIXED CODE ###

N = int(input())
emp = list(map(int,input().split()))
ans_l = [0]*(N+1)
for i in range(N-1):
    a = emp[i]
    ans_l[a] +=1
for i in range(1,N+1):
    print(ans_l[i])
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x

        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

def solve(uf, first_order_friends):
    ret = [0]
    for i in range(1, N + 1):
        ret.append(len(list(set(uf.members(i)) - first_order_friends[i])) - 1)
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    first_order_friends = [set() for _ in range(N + 1)]
    blocked_list = [set() for _ in range(N + 1)]
    uf = UnionFind(N + 1)

    for _ in range(M):
        a, b = map(int, input().split())
        first_order_friends[a].add(b)
        first_order_friends[b].add(a)
        uf.union(a, b)

    for _ in range(K):
        c, d = map(int, input().split())
        first_order_friends[c].add(d)
        first_order_friends[d].add(c)

    for ans in solve(uf, first_order_friends)[1:]:
        print(ans, end=' ')

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x

        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]

def solve(uf, except_list):
    ret = [0]
    for i in range(1, N + 1):
        ret.append(uf.size(i) - 1 - len(except_list[i]))
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    except_list = [[] for _ in range(N + 1)]
    uf = UnionFind(N + 1)

    for _ in range(M):
        a, b = map(int, input().split())
        except_list[a].append(b)
        except_list[b].append(a)
        uf.union(a, b)

    for _ in range(K):
        c, d = map(int, input().split())
        if not uf.same(c, d):
            continue
        except_list[c].append(d)
        except_list[d].append(c)

    for ans in solve(uf, except_list)[1:]:
        print(ans, end=' ')
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [input() for _ in range(h)]

v = [[-1] * w for _ in range(h)]
d = [(0,1), (0,-1), (1,0), (-1,0)]
d2 = [(2,2), (2,1), (2,0), (2,-1), (2,-2), (1,2), (1,1), (1,-1), (1,-2), (0,2), (0,-2), (-1,2), (-1,1),(-1,-1), (-1,-2), (-2,2), (-2,1), (-2,0),(-2,-1),(-2,-2)]

v[ch-1][cw-1] = 0

q = deque([(ch-1, cw-1)])
tmp = 0

while True:
    while q:
        i,j = q.popleft()
        for ii,jj in d:
            if 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp
                    q.append((i+ii,j+jj))

    for i in range(h):
        for j in range(w):
            for ii,jj in d2:
                if v[i][j] == tmp and 0 <= i + ii < h and 0 <= j + jj < w:
                    if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                        v[i+ii][j+jj] = tmp+1
                        q.append((i+ii,j+jj))
    if not q:
        break
    tmp += 1

print(v[dh-1][dw-1])


### FIXED CODE ###

import sys
from collections import deque
import copy

input = sys.stdin.readline

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [input() for _ in range(h)]

v = [[-1] * w for _ in range(h)]
d = [(0,1), (0,-1), (1,0), (-1,0)]
d2 = [(2,2), (2,1), (2,0), (2,-1), (2,-2), (1,2), (1,1), (1,-1), (1,-2), (0,2), (0,-2), (-1,2), (-1,1),(-1,-1), (-1,-2), (-2,2), (-2,1), (-2,0),(-2,-1),(-2,-2)]

v[ch-1][cw-1] = 0

q = deque([(ch-1, cw-1)])
q2 = [(ch-1, cw-1)]
tmp = 0

while True:
    while q:
        i,j = q.popleft()
        for ii,jj in d:
            if 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))

    cnt = 0
    for k in range(len(q2)):
        i,j = q2[k][0], q2[k][1]
        for ii,jj in d2:
            if v[i][j] == tmp and 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp+1
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))
                    cnt += 1
    if not q:
        break
    tmp += 1
    q2 = q2[-cnt:]
print(v[dh-1][dw-1])
### BUGGY CODE ###

n = int(input())
L = sorted(list(map(int, input().split())))
cnt = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        v = L[i] + L[j]
        left = j + 1
        right = n
        while left < right:
            mid = (left + right) // 2
            if L[mid] == v:
                cnt += mid - 1 - j
                break
            elif L[mid] > v:
                right = mid
            else:
                left = mid + 1
        else:
            if left == n:
                cnt += n - 1 - j
            elif L[left] < v:
                cnt += left - j
            else:
                cnt += left - 1 - j
print(cnt)


### FIXED CODE ###

import bisect
N = int(input())
L = sorted(list(map(int, input().split())))
cnt = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        a = L[i]
        b = L[j]
        v = bisect.bisect_left(L, a + b)
        cnt += v - j - 1
print(cnt)
### BUGGY CODE ###

N, A, B = list(map(int, input().split(" ")))
h = []
for _ in range(N):
    h.append(int(input()))
    
def argmax(l):
    return l.index(max(l))

ans = 0
while True:
    if max(h) <= 0:
        break
    max_idx = argmax(h)
    minus = [B for _ in range(N)]
    minus[max_idx] = A
    h = [x - y for x, y in zip(h, minus)]
    ans += 1

print (ans)

### FIXED CODE ###

from math import ceil

N, A, B = map(int, input().split())
H = []
for _ in range(N):
    H.append(int(input()))
    
left = 0
right = max(H)//B + 1

while right - left > 1:
    mid = (right + left) // 2
    c = sum([ceil((h-B*mid)/(A-B)) for h in H if h > B*mid])
    
    if c > mid:
        left = mid
    else:
        right = mid
print(right)
### BUGGY CODE ###

L, R = map(int, input().split())

res = 10 ** 9
flag = False

for i in range(L, R+1):
    for j in range(L, R+1):
        if i%2019 == 0 or j%2019 == 0:
            res = 0
            flag = True
            break

        if i != j:

            res = min(res, i*j%2019)

    if flag:
        break

print(res)


### FIXED CODE ###

L, R = map(int, input().split())

res = 10 ** 9
flag = False

for i in range(L, R+1):
    for j in range(L, R+1):
        if i%2019 == 0 or j%2019 == 0:
            res = 0
            flag = True
            break

        if i != j:

            res = min(res, i*j%2019)

    if flag:
        break

print(res)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())

def calc_idx(x, y):
    if x > y:
        x, y = y, x
    return x + y*(y-1)//2

# create graphs & calc indegree
n_game = n * (n-1) // 2
edge = [[] for i in range(n_game)]
indegree = [0] * n_game
for i in range(n):
    ai = list(map(int, input().split()))

    for j in range(1, n-1):
        g1 = calc_idx(i, ai[j-1]-1)
        g2 = calc_idx(i, ai[j]-1)
        edge[g1].append(g2)
        indegree[g2] += 1


ans = 0
cand = deque([(i, 1) for i in range(n_game) if indegree[i] == 0])
n_ts = 0
while len(cand) > 0:
    u, day = cand.popleft()
    ans = max(ans, day)
    n_ts += 1
    for v in edge[u]:
        indegree[v] -= 1
        if indegree[v] == 0:
            cand.append((v, day+1))

if n_ts != n_game:
    ans = -1

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]

def calc_idx(x, y):
    if x > y:
        x, y = y, x
    return x + y*(y-1)//2

n_game = n * (n-1) // 2
edge = [[] for i in range(n_game)]
for i in range(n):
    for j in range(1, n-1):
        g1 = calc_idx(i, a[i][j-1])
        g2 = calc_idx(i, a[i][j])
        edge[g1].append(g2)

indegree = [0] * n_game
for i in range(n_game):
    for v in edge[i]:
        indegree[v] += 1

ans = 0
cand = [i for i in range(n_game) if indegree[i] == 0]
ts = []
while cand:
    ts.extend(cand)
    cand2 = []
    for ci in cand:
        for v in edge[ci]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand2.append(v)
    cand = cand2
    ans += 1

if len(ts) != n_game:
    ans = -1

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

n,m = list(map(lambda x: int(x), input().split()))

jobs = []
for i in range(n):
    a,b = list(map(lambda x: int(x), input().split()))
    jobs.append([b,a])

# 貪欲解法
# 最終日から決める
jobs.sort()
jobs.reverse()
ans = 0
for i in range(m+1):
    # 給料大きい順にみて、振り込みがi+1以内なら働く
    for j in range(len(jobs)):
        if jobs[j][1] < i+1:
            ans += jobs[j][0]
            del jobs[j]
            break

            
print (ans)

### FIXED CODE ###

import heapq

n,m = list(map(lambda x: int(x), input().split()))

jobs = {}
for i in range(n):
    a,b = list(map(lambda x: int(x), input().split()))
    if a in jobs.keys():
        jobs[a].append(b)
    else:
        jobs[a] = [b]

# 貪欲解法
# 最終日から決める
ans = 0
day = m

possible_job = []
# heapqでjobを管理すれば現時点で最大の給与を得ることのできる仕事を容易に取り出せる
for i in range(m+1):
    if i in jobs.keys():
        for x in jobs[i]:
            heapq.heappush(possible_job, -1 * x)
    if len(possible_job)>0:
        day_work = heapq.heappop(possible_job)
        ans += -1 * day_work
    
print (ans)
### BUGGY CODE ###

n,k = map(int, input().split( ))
h = list(map(int, input().split( )))
#h = [0]+h#h[0]=0追加
inf = 10**15

dp = [[inf]*n for _ in range(n+1)] #dp[i][j]右端がi、j+1本残す
mn = h[0]
for i in range(n):
    mn = min(mn,h[i])
    dp[i][0] = min(mn,h[i])

for i in range(n):##右端
    for j in range(i+1):#本数
        for t in range(i):#右から2番目,
            dp[i][j] = min(dp[i][j], dp[t][j-1] + max(h[i]-h[t], 0))

ans = inf 

for i in range(n):
    ans = min(ans, dp[i][n-k-1])
print(ans)


### FIXED CODE ###

n,k = map(int, input().split( ))
if n==k:
    print(0)
    exit()
h = list(map(int, input().split( )))
#h = [0]+h#h[0]=0追加
inf = 10**15

dp = [[inf]*n for _ in range(n+1)] #dp[i][j]右端がi、j+1本残す
mn = h[0]
for i in range(n):
    #mn = min(mn,h[i])
    dp[i][0] = h[i]#min(mn,h[i])

for i in range(1,n):##右端
    for j in range(i+1):#本数
        for t in range(j-1,i):#右から2番目,
            dp[i][j] = min(dp[i][j], dp[t][j-1] + max(h[i]-h[t], 0))

ans = inf 

for i in range(n):
    ans = min(ans, min(dp[i][n-k-1:]))###
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

n = 0
while len(A)>0:
    n+=1
    t = A[0]
    left = []
    for a in A[1:]:
        if a>t: t=a
        else: left.append(a)
    A = left

print(n)

### FIXED CODE ###

import bisect

N = int(input())
A = [-int(input()) for _ in range(N)]

x = [A[0]]

for a in A[1:]:
    i = bisect.bisect(x,a)
    if i==len(x): x.append(a)
    else: x[i]=a

print(len(x))