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

n=int(input())
a=list(map(int,input().split()))
import math
dp=[[-math.inf]*(n+1) for _ in range(n+1)]
dp[0][0]=0
dp[1][0]=0
dp[1][1]=a[0]
for i in range(2,n+1):
    for j in range(n//2-(n-i+1)//2,i//2+1):
        dp[i][j]=max(dp[i-1][j],dp[i-2][j-1]+a[i-1])
print(dp[n][n//2])


### FIXED CODE ###

from collections import defaultdict

n=int(input())
a=list(map(int,input().split()))
#n=2*pow(10,5)
#a=range(1,pow(10,5)+1)
# dp[i][j]:i番目の数字の中からj個数字を取った時の最大。(i//2)-1<=j<=(i+1)//2
# 求めるのはdp[n][n//2]
dp=defaultdict(lambda:-pow(10,18))
dp[(1,1)]=a[0]
for i in range(2,n+1): #i番目の数字はa[i-1]
      for j in range(i//2-1,(i+1)//2+1):
            if j==1:
                  dp[(i,j)]=max(dp[(i-1,1)],a[i-1])
            elif j==0:
                  dp[(i,j)]=0
            else:
                  dp[(i,j)]=max(dp[(i-2,j-1)]+a[i-1],dp[(i-1,j)])
print(dp[(n,n//2)])
### BUGGY CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
cnt = 0
for i in range(200010):
    if n < 10:
        cnt += n
        break
    cnt += (n % 10)
    n = int(n // 10)
if cnt % 9 == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = input()
cnt = 0
for i in range(len(n)):
    cnt += int(n[i])
if cnt % 9 == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n = int(input())

T=[]
A=[]
for i in range(n):
    t,a=map(int,input().split())
    T.append(t)
    A.append(a)

#比に対する掛け率
kake = 1
sum_tmp = 0
t_tmp = 0
a_tmp = 0

for i in range(n):
    kake = 1
    #i+1回目の合計がi回目の合計より大きくなる最小の掛け率を計算する
    while kake*(T[i]+A[i]) < sum_tmp or kake*T[i] < t_tmp or kake*A[i] < a_tmp:
        kake += 1
    
    sum_tmp = kake*(T[i]+A[i])
    t_tmp = kake*T[i]
    a_tmp = kake*A[i]

ans = kake * (T[n-1]+A[n-1])
print(ans)

### FIXED CODE ###

def main():
    n = int(input())

    T=[]
    A=[]
    for i in range(n):
        t,a=map(int,input().split())
        T.append(t)
        A.append(a)

    #比に対する掛け率
    kake = 1
    sum_tmp = 0
    t_tmp = 0
    a_tmp = 0
    for i in range(n):
        if i == 0:
            kake = 1
        else:
            #i+1回目の合計がi回目の合計より大きくなる最小の掛け率を計算する
            if sum_tmp % (T[i]+A[i]) == 0:
                kake_sum = sum_tmp // (T[i]+A[i])
            else:
                kake_sum = sum_tmp // (T[i]+A[i]) + 1
            
            if t_tmp % T[i] == 0:
                kake_t = t_tmp // T[i]
            else:
                kake_t = t_tmp // T[i] + 1
            
            if a_tmp % A[i] == 0:
                kake_a = a_tmp // A[i]
            else:
                kake_a = a_tmp // A[i] + 1
            
            kake = max(kake_sum, kake_t, kake_a)

        sum_tmp = kake*(T[i]+A[i])
        t_tmp = kake*T[i]
        a_tmp = kake*A[i]

    ans = kake * (T[n-1]+A[n-1])
    print(ans)

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

N = int(input())
tt = 0
xx = 0
yy = 0
flag = True
z = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
    t, x, y = z[i]
    s = [[xx, yy]]
    for j in range(t - tt):
        ss = []
        for k in range(len(s)):
            ss.append([s[k][0] + 1, s[k][1]])
            ss.append([s[k][0] - 1, s[k][1]])
            ss.append([s[k][0], s[k][1] + 1])
            ss.append([s[k][0], s[k][1] - 1])
        s = ss
    if [x, y] in s:
        tt = t
        xx = x
        yy = y
    else:
        print('No')
        exit()
print('Yes')

### FIXED CODE ###

N = int(input())
tt = 0
xx = 0
yy = 0
z = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
    t, x, y = z[i]
    dt = t - tt
    dx = abs(x - xx)
    dy = abs(y - yy)
    if dt < dx + dy or (dt - (dx + dy)) % 2:
        print('No')
        exit()
    tt = t
    xx = x
    yy = y
print('Yes')
### BUGGY CODE ###

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

s = 1
ten18 = 10**18
over = False

for b in a:
  s *= b
  if s > ten18:
    #print(-1)
    over = True
  if b == 0:
    over = False
    break
  
if over:
  print(-1)
else:
  print(s)


### FIXED CODE ###

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

s = 1
ten18 = 10**18
over = False

for b in a:
  if not over:
    s *= b
  if s > ten18:
    #print(-1)
    over = True
  if b == 0:
    s = 0
    over = False
    break
  
if over:
  print(-1)
else:
  print(s)
### BUGGY CODE ###

# https://atcoder.jp/contests/agc033/tasks/agc033_a

from heapq import heappop, heappush
H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]
dist = [[-1] * W for _ in range(H)]

def search(h, w):
    queue = [(0, (h, w))]
    while len(queue) > 0:
        cd, (ch, cw) = heappop(queue)
        for (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nh, nw = ch + dh, cw + dw
            if nh < 0 or H <= nh or nw < 0 or W <= nw:
                continue
            if dist[nh][nw] == -1 or (dist[nh][nw] >= 0 and dist[nh][nw] > cd + 1):
                dist[nh][nw] = cd + 1
                heappush(queue, (cd + 1, (nh, nw)))


for h in range(H):
    for w in range(W):
        if M[h][w] == '#':
            search(h, w)

ans = 0
for row in dist:
    ans = max(ans, max(row))
print(ans)

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)

def solve():
    H, W = map(int, input().split())
    M = [[] for _ in range(H)]
    queue = deque()
    for i in range(H):
        M[i] = list(input())
        for j in range(W):
            if M[i][j] == '#':
                queue.append((i, j))
    ans = 0
    while queue:
        # 今の地点から1ステップ変化
        n = len(queue)
        flag = False
        for _ in range(n):
            cy, cx = queue.popleft()
            for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
                ny, nx = cy + dy, cx + dx
                if 0 <= nx < W and 0 <= ny < H and M[ny][nx] == '.':
                    M[ny][nx] = '#'
                    flag = True
                    queue.append((ny, nx))
        if flag:
            ans += 1
    print(ans)


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

from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

q = deque()
d = [[-1]*w for x in range(h)]

for i in range(h):
    for j in range(w):
        if m[i][j] == "#":
            q.append([i,j])
            d[i][j] = 0

while q:
    v = q.popleft()
    count = 0
    for i in m:
        jj = set(i)
        if len(jj) == 2:
            break
    else:
        break
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "#"
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1

######
ans = 0
for i in d:
    ans = max(ans,max(i))
print(ans)

### FIXED CODE ###

from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

q = deque()
d = [[-1]*w for x in range(h)]

for i in range(h):
    for j in range(w):
        if m[i][j] == "#":
            q.append([i,j])
            d[i][j] = 0

aa = 0
while q:
    v = q.popleft()
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "#"
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1
            aa = max(aa,d[ny][nx])

######
print(aa)
### BUGGY CODE ###

N = int(input())
str = "Christmas"
 
if N != 25:
	while N < 25:
		str += " Eve"
		N -= 1
        
print(str)

### FIXED CODE ###

N = int(input())
str = "Christmas"
 
if N != 25:
	while N < 25:
		str += " Eve"
		N += 1
        
print(str)
### BUGGY CODE ###

count=0
N=int(input())
P=[int(i) for i in input().split()]
for i in range(0,N):
  for j in range(0,i+1):
    if P[j]<P[i]:
      break
    if j==i:
      count+=1
print(count)

### FIXED CODE ###

import numpy as np
import sys

count=0
N=int(sys.stdin.readline().rstrip())
P=[int(i) for i in sys.stdin.readline().split()]
minval=np.max(P)
for i in range(0,N):
  if minval>=P[i]:
    minval=P[i]
    count+=1
print(count)
### BUGGY CODE ###

import fractions
"""最大公約数"""
def gcd(a,b):
    return fractions.gcd(a,b)

"""最小公倍数"""
def lcm(a,b):
    f = gcd(a,b)
    return a*b//f

n = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
l = A[0]
for i in range(1, n):
    l = lcm(l, A[i])
res = 0
for a in A:
    res += l//a
    res %= mod
print(res%mod)

### FIXED CODE ###

import functools
"""最大公約数"""
def gcd(a,b):
    import fractions
    return fractions.gcd(a,b)

"""最小公倍数"""
def lcm(a,b):
    f = gcd(a,b)
    return a*b//f

def m(nums):
    return functools.reduce(lcm, nums)

def main():
    n = int(input())
    A = list(map(int,input().split()))
    mod = 10**9+7
    l = m(A)
    res = 0
    print(sum(l// i for i in A) % mod)

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

import sys
input = sys.stdin.readline


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


N, Q = map(int, input().split())
c = list(map(int, input().split()))

lr = []
for i in range(Q):
    l, r = map(int, input().split())
    lr.append([l, r, i])

lr.sort(key=lambda x: x[1])
# print("lr", lr)
rightest = [-1] * (N + 1)
current_q = 0
bit = Bit(N)
ans = [0] * Q

for i in range(N):
    if rightest[c[i]] != -1:
        bit.add(rightest[c[i]] + 1, -1)
    rightest[c[i]] = i
    bit.add(i + 1, 1)
    # print(bit.tree)

    while current_q < Q and lr[current_q][1] == i + 1:
        ans[lr[current_q][2]] = bit.sum(lr[current_q][1]) - bit.sum(lr[current_q][0] - 1)
        current_q += 1

for i in range(Q):
    print(ans[i])


### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


N, Q = map(int, input().split())
c = list(map(int, input().split()))

lr = []
for i in range(Q):
    l, r = map(int, input().split())
    lr.append([l, r, i])

lr.sort(key=lambda x: x[1])
# print("lr", lr)
rightest = [-1] * (N + 1)
current_q = 0
bit = Bit(N)
ans = [0] * Q

for i in range(N):
    if rightest[c[i]] != -1:
        bit.add(rightest[c[i]] + 1, -1)
    rightest[c[i]] = i
    bit.add(i + 1, 1)
    # print(bit.tree)

    while current_q < Q and lr[current_q][1] == i + 1:
        ans[lr[current_q][2]] = bit.sum(lr[current_q][1]) - bit.sum(lr[current_q][0] - 1)
        current_q += 1

for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    A_i = [A[i] - i - 1 for i in range(N)]
    ans = 10 ** 9
    for i in range(min(A_i), max(A_i) + 1):
        sums = 0
        for a in A_i:
            sums += abs(a - i)
        ans = min(ans, sums)
    print(ans)


if __name__ == "__main__":
    solve()

### FIXED CODE ###

import statistics


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    A_i = [A[i] - i - 1 for i in range(N)]
    b = statistics.median_high(A_i)
    print(sum(abs(a - b) for a in A_i))



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

n = int(input())
ans = 1
for i in range(1,n+1):
	ans = ans*i
print(ans%(10**9+7))

### FIXED CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
	ans = (ans*i)%(10**9+7)
print(ans)
### BUGGY CODE ###

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

a  = [0]*n

a = [int(s) for s in input().split()]

nxt = a[0]

seen = [1]
#load = []
res = 0
flag = 0
for i in range(k-1):
    #print(seen)
    #print(nxt)
    if not(nxt in seen):
        seen.append(nxt)
        nxt = a[nxt-1]
    else:
        root = i - seen.index(nxt) + 1
        #print(root)
        #print(k-1-i)
        zansa = (k-1-i)%root
        res = seen[seen.index(nxt)+zansa]
        flag = 1
        break


if(flag == 1):
    print(res)
else:
    print(nxt)

### FIXED CODE ###

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

a  = [0]*n

a = [int(s) for s in input().split()]

nxt = a[0]

seen = [1]
load = set()
load.add(1)
res = 0
flag = 0
for i in range(k-1):
    #print(seen)
    #print(nxt)
    if not(nxt in load):
        seen.append(nxt)
        load.add(nxt)
        nxt = a[nxt-1]
    else:
        root = i - seen.index(nxt) + 1
        #print(root)
        #print(k-1-i)
        zansa = (k-1-i)%root
        res = seen[seen.index(nxt)+zansa]
        flag = 1
        break


if(flag == 1):
    print(res)
else:
    print(nxt)
### BUGGY CODE ###

N, X, Y = list(map(int, input().split(' ')))
X -= 1
Y -= 1
dist_map = {}

def search(origin):
  dist = []
  # X, Yの辺がない場合
  for i in range(N):
    dist.append(abs(origin - i))
  # X, Yの辺がある場合
  if dist[X] < dist[Y]:
    dist[Y] = dist[X] + 1
  elif dist[Y] < dist[X]:
    dist[X] = dist[Y] + 1
  for i in range(X+1, Y):
    dist[i] = min(dist[i-1]+1, dist[i+1]+1, dist[i])
  for i in range(N):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  for i in reversed(range(N)):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  #print(*dist)
  return dist


for i in range(N):
  dist_map[i] = search(i)

print(N)
for k in range(2, N):
  count = 0
  for i in range(N):
    #print('i='+str(i))
    #dist = dist_map[i]
    #print(*dist)
    count += dist_map[i].count(k)
  print(count//2)

### FIXED CODE ###

N, X, Y = list(map(int, input().split(' ')))
X -= 1
Y -= 1
dist_map = {}

def search(origin):
  dist = []
  # X, Yの辺がない場合
  for i in range(N):
    dist.append(abs(origin - i))
  # X, Yの辺がある場合
  if dist[X] < dist[Y]:
    dist[Y] = dist[X] + 1
  elif dist[Y] < dist[X]:
    dist[X] = dist[Y] + 1
  for i in range(N):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  for i in reversed(range(N)):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  #print(*dist)
  return dist

count = [0 for i in range(N)]
for i in range(N):
  dist = search(i)
  for dis in dist:
    count[dis] += 1

for i in range(1, N):
  print(count[i]//2)
### BUGGY CODE ###

A, B, K = map(int, input().split())
l = []
for i in range(A, B+1):
    l.append(i)
    
if B - (A-1) < 2*K:
    for j1 in l:
        print(j1)
else:
    m = l[:K] + l[-K:]
    for j in m:
        print(j)

### FIXED CODE ###

A, B, K = map(int, input().split())
    
if B - (A-1) < 2*K:
    l = []
    for i in range(A, B+1):
        l.append(i)
    for j1 in l:
        print(j1)
else:
    for j2 in range(A, A+K):
        print(j2)
    for j3 in range(B-K+1, B+1):
        print(j3)
### BUGGY CODE ###

H, W = map(int, input().split())
X, Y, U = [], [], []
for _ in range(H):
    X.append(list(map(int, input().split())))
    U.append([set() for _ in range(W)])
for _ in range(H):
    Y.append(list(map(int, input().split())))

U[0][0] = set([ abs(X[0][0] - Y[0][0]) ])

for i in range(W):
    for j in range(H):
        for k in U[j][i]:
            if j + 1 < H:
                U[j + 1][i].add(abs(k + abs(X[j + 1][i] - Y[j + 1][i])))
                U[j + 1][i].add(abs(k - abs(X[j + 1][i] - Y[j + 1][i])))
            if i + 1 < W:
                U[j][i + 1].add(abs(k + abs(X[j][i + 1] - Y[j][i + 1])))
                U[j][i + 1].add(abs(k - abs(X[j][i + 1] - Y[j][i + 1])))
print(min(U[-1][-1]))

### FIXED CODE ###

# at ABC 147 e (500)
import sys
X, Y, U = [], [], []
if True:
    H, W, *nums = map(int, sys.stdin.read().split())
    i = 0
    for _ in range(H):
        X.append(nums[i:i + W])
        i += W
        U.append([0] * W)
    for _ in range(H):
        Y.append(nums[i:i + W])
        i += W
else:    
    H, W = map(int, input().split())
    for _ in range(H):
        X.append(list(map(int, input().split())))
        U.append([0 for _ in range(W)])
    for _ in range(H):
        Y.append(list(map(int, input().split())))

mid = 80*80

init = abs(X[0][0] - Y[0][0])
U[0][0] = (1 << (mid - init)) | (1 << (mid + init))

for i in range(W):
    for j in range(H):
        k = abs(X[j][i] - Y[j][i])
        if j > 0:
            U[j][i] |= (U[j - 1][i] << k)
            U[j][i] |= (U[j - 1][i] >> k)
        if i > 0:
            U[j][i] |= (U[j][i - 1] << k)
            U[j][i] |= (U[j][i - 1] >> k)
#        U[j][i] = U[j][i] & ((1 << (2 * mid)) - 1)
    
i = 0
min_ = float("inf")
while True:
     if U[-1][-1] & 1:
         min_ = min(min_, abs(i - mid))
     U[-1][-1] = U[-1][-1] >> 1
     i += 1
     if i >= 2 * mid:
         break
print(min_)
### BUGGY CODE ###

n,a,b=map(int,input().split())
I=10**9+7
def g(k,r):
  return 1 if k<2 or r in (0,k) else (g(k-1,r-1)+g(k-1,r))%I
p=1
for i in range(n):
  p=p*2%I
print((p-g(n,a)-g(n,b)-1)%I)

### FIXED CODE ###

n,a,b=map(int,input().split())
M=10**9+7
def c(k):
  s=t=1
  for i in range(k): s=s*(n-i)%M; t=t*(i+1)%M
  return s*pow(t,M-2,M)%M
print((pow(2,n,M)-c(a)-c(b)-1)%M)
### BUGGY CODE ###

N = int(input())
S = list(input())

Rindex = set(i for i in range(N) if S[i] == 'R')
Gindex = set(i for i in range(N) if S[i] == 'G')
Bindex = set(i for i in range(N) if S[i] == 'B')

ans = 0

for i in Rindex:
    for j in Gindex:
        for k in Bindex:
            if abs(i - j) == abs(j - k) or abs(j - k) == abs(k - i) or abs(k - i) == abs(i - j):continue
            ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
S = input()
cnt = Counter(S)

ans = cnt['R']*cnt['G']*cnt['B']
#まずansに要請１を満たす(i, j, k)の組の数を入れておき，ここから，要請２を満たさないものを除いていく。

for i in range(N-2):
    for j in range(i+1, N-1):
        k = j + (j - i)
        #kは　j - i = k - j を満たす。ただし，（i, j, k）が要請１を満たしているとは限らない。
        if k < N:
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                ans -= 1

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

abc = input().split()
a = int(abc[0])
b = int(abc[1])
c = int(abc[2])
d = int(abc[3])
e = int(abc[4])
f = int(abc[5])

x = []
y = []
pair = []
con = []


for i in range(f):
    for j in range(f):
        canx = ((a*i)+(b*j))*100
        if canx<=f:
            x.append(canx)

if x == []:
    print('x is empty')
            
for i in range(f):
    for j in range(f):
        cany = (c*i)+(d*j)
        if cany<=f:
            y.append(cany)
            
if y == []:
    print('y is empty')
            
for i in x:
    for j in y:
        if i+j<=f:
            if i!=0:
                if 100*j/i<=e:
                    pair.append([i, j])

if pair == []:
    print('pair is empty')

for i in pair:
    if sum(i)!=0:
        con.append(i[1]/sum(i))
    
if con == []:
    print('con is empty')
    
ans = pair[con.index(max(con))]
print(sum(ans), ans[1])

### FIXED CODE ###

abc = input().split()
a = int(abc[0])
b = int(abc[1])
c = int(abc[2])
d = int(abc[3])
e = int(abc[4])
f = int(abc[5])

x = []
y = []
pair = []
con = []


for i in range(int((f/100)+1)):
    for j in range(int((f/100)+1)):
        canx = ((a*i)+(b*j))*100
        if canx<=f:
            x.append(canx)

if x == []:
    print('x is empty')
            
for i in range(f):
    for j in range(f):
        cany = (c*i)+(d*j)
        if cany<=f:
            y.append(cany)
            
if y == []:
    print('y is empty')
            
for i in x:
    for j in y:
        if i+j<=f:
            if i!=0:
                if 100*j/i<=e:
                    pair.append([i, j])

if pair == []:
    print('pair is empty')

for i in pair:
    if sum(i)!=0:
        con.append(i[1]/sum(i))
    
if con == []:
    print('con is empty')
    
ans = pair[con.index(max(con))]
print(sum(ans), ans[1])
### BUGGY CODE ###

stairs_num, broken_num = tuple(int(i) for i in input().split(" "))
broken_list = []
for i in range(broken_num):
    broken_list.append(int(input()))
trance_num_list = []
if len(broken_list) >= 1 and broken_list[0] == 1:
    trance_num_list.append(0)
else:
    trance_num_list.append(1)
if (len(broken_list) >= 1 and broken_list[0] == 2) or \
 (len(broken_list) >= 2 and broken_list[1] == 2):
    trance_num_list.append(0)
else:
    if trance_num_list[0] == 0:
        trance_num_list.append(1)
    else:
        trance_num_list.append(2)
if stairs_num > 2:
    for i in range(stairs_num - 2):
        if i + 3 in broken_list:
            trance_num_list.append(0)
        else:
            trance_num_list.\
             append((trance_num_list[-1] + trance_num_list[-2]) % 1000000007)
print(trance_num_list[stairs_num - 1])


### FIXED CODE ###

from math import floor  
stairs_num, broken_num = tuple(int(i) for i in input().split(" "))
broken_list = []
for i in range(broken_num):
    broken_list.append(int(input()))
trance_num_list = []
if len(broken_list) >= 1 and broken_list[0] == 1:
    trance_num_list.append(0)
else:
    trance_num_list.append(1)
if (len(broken_list) >= 1 and broken_list[0] == 2) or \
 (len(broken_list) >= 2 and broken_list[1] == 2):
    trance_num_list.append(0)
else:
    if trance_num_list[0] == 0:
        trance_num_list.append(1)
    else:
        trance_num_list.append(2)
if stairs_num > 2:
    a = len(broken_list)
    for i in range(stairs_num - 2):
        key = 0
        left = 0
        right = a
        while left < right:
            midle = floor((left + right) / 2)
            if broken_list[midle] < i + 3:
                left = midle + 1
            elif broken_list[midle] == i + 3:
                key = 1
                break
            else:
                right = midle
        if key:
            trance_num_list.append(0)
        else:
            trance_num_list.\
             append((trance_num_list[-1] + trance_num_list[-2]) % 1000000007)
print(trance_num_list[stairs_num - 1])
### BUGGY CODE ###

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

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
ans=1
m=p[0]
for i in range(1,len(p)):
    if p[i]==1:
        ans=ans+1
        break
    elif p[i]>m:
        continue
    else:
        ans=ans+1
        m=p[i]
print(ans)
### BUGGY CODE ###

from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    dp = [[0, 0]]
    item = [list(map(int, input().split())) for _ in range(n)]
    item.sort()
    for i in range(n):
        dp.sort()
        x = len(dp)
        for j in reversed(range(x)):
            p = dp[j][0] + item[i][0]
            q = dp[j][1] + item[i][1]
            if p > w:
                continue
            f = True
            for k in range(j+1, x):
                if dp[k][0] == p:
                    dp[k][1] = max(dp[k][1], q)
                    f = False
            if f:
                dp.append([p, q])
    dp.sort(key=lambda x: x[1], reverse=True)
    print(dp[0][1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for p, q in item:
        for j in reversed(range(p, min(w+1, x+p+1))):
            dp[j] = max(dp[j-p]+q, dp[j])
        x += p
    print(max(dp))

if __name__ == "__main__":
    main()