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

N, W = map(int, input().split())
w, v = [0]*N, [0]*N
for i in range(N):
  w[i], v[i] = map(int, input().split())

dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(1, N+1):
  for w_sum in range(1, W+1):
    if w_sum >= w[i-1]:
      dp[i][w_sum] = max(dp[i-1][w_sum-w[i-1]] + v[i-1], dp[i-1][w_sum])
    else:
      dp[i][w_sum] = dp[i-1][w_sum]
      
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
w, v = [0]*(N+1), [0]*(N+1)
for i in range(N):
  w[i+1], v[i+1] = map(int, input().split())
  
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
  for j in range(W+1):
    if j < w[i]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j-w[i]]+v[i], dp[i-1][j])
print(dp[N][W])
### BUGGY CODE ###

def main():
    N = int(input())
    GA, SA, BA = map(int, input().split())
    GB, SB, BB = map(int, input().split())

    def napsac(x, g1, s1, b1, g2, s2, b2):
        dp = [None for _ in range(x+1)]
        dp[0] = 0

        # def case(i, m1, m2):
        #     return 0 if i - m1 < 0 else dp[i-m1] + m2

        # for i in range(1,x+1):
        #     dp[i] = max(i, case(i, g1, g2), case(i, s1, s2), case(i, b1, b2))

        gsbs = ((g1, g2), (s1, s2), (b1, b2))

        for i in range(1,x+1):
            dp[i] = i
            for m in gsbs:
                dp[i] = max(dp[i], 0 if i - m[0] < 0 else dp[i-m[0]] + m[1])
            
        return dp[-1]

    print(napsac(napsac(N, GA, SA, BA, GB, SB, BB), GB, SB, BB, GA, SA, BA))

if __name__ == "__main__":
    main()

### FIXED CODE ###

N = int(input())
GA, SA, BA = map(int, input().split())
GB, SB, BB = map(int, input().split())

def napsac(x, g1, s1, b1, g2, s2, b2):
    dp = [0 for _ in range(x+1)]
    dp[0] = 0

    def case(i, m1, m2):
        return 0 if i - m1 < 0 else dp[i-m1] + m2

    for i in range(1,x+1):
        dp[i] = max(i, case(i, g1, g2), case(i, s1, s2), case(i, b1, b2))

    return dp[-1]

print(napsac(napsac(N, GA, SA, BA, GB, SB, BB), GB, SB, BB, GA, SA, BA))
### BUGGY CODE ###

def main():
    S = list(input())
    N = len(S)
    ans = 0
    m = 2019
    div_list = [0]*m
    div_list[0] += 1
    num = 0
    for i in range(N):
        num += 10**i*int(S[N-i-1])
        div_list[num%m] += 1

    for item in div_list:
        if item >= 2:
            ans += int(item*(item-1)/2)

    print(ans)

if __name__ == "__main__":
    main()



### FIXED CODE ###

from sys import stdin
input = stdin.readline

def main():
    S = list(input())
    S.pop()
    m = 2019
    div_list = [0]*m
    num = 0
    for i, l in enumerate(reversed(S)):
        num += pow(10, i, m)*int(l)
        div_list[num%m] += 1

    div_list[0] += 1
    ans = 0
    for item in div_list:
        ans += int(item*(item-1)/2)

    print(ans)

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

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

def found_cut(X):
    p1 = sum(X)/2
    count1 = 0
    for i in range(len(X)):
        count1 += X[i]
        if p1 <= count1:
            if abs(count1-p1) < abs(count1-X[i]-p1):
                index = i
                break
            else:
                index = i-1
                break
    return index

def found_ans(X,Y,Z,W):
    ans_list = []
    ans_list.append(sum(X))
    ans_list.append(sum(Y))
    ans_list.append(sum(Z))
    ans_list.append(sum(W))
    return max(ans_list)-min(ans_list)

ANS = []
for x in range(1,N-2):
    A_first = A[:x+1]
    A_second = A[x+1:]
    if len(A_first) >= 2 and len(A_second) >= 2:
        wp1 = found_cut(A_first)
        wp2 = found_cut(A_second)
        pattern3_1 = A_first[:wp1+1]
        pattern3_2 = A_first[wp1+1:]
        pattern3_3 = A_second[:wp2+1]
        pattern3_4 = A_second[wp2+1:]
        ANS.append(found_ans(pattern3_1,pattern3_2,pattern3_3,pattern3_4))
print(min(ANS))

### FIXED CODE ###

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

S = [0]*N
S[0] = A[0]
for i in range(1, N):
    S[i] = A[i]+S[i-1]
    
ans = 2*10**14
l = 0
temp = 2*10**14
r = 2
#for i in range(2, N):
#    if abs(S[-1]-2*S[i]+S[1]) < temp:
#        temp = abs(S[-1]-2*S[r]+S[1])
#        r = i
        
for i in range(2, N-1):
    r = max(r, i)
    while l+1 < i-1 and abs(S[i-1]-2*S[l]) > abs(S[i-1]-2*S[l+1]):
        l += 1
    while r+1 < N-1 and abs(S[N-1]-2*S[r]+S[i-1])  > abs(S[N-1]-2*S[r+1]+S[i-1]):
        r += 1
    t = max(S[N-1]-S[r], S[r]-S[i-1], S[i-1]-S[l], S[l]) - min(S[N-1]-S[r], S[r]-S[i-1], S[i-1]-S[l], S[l])
    ans = min(ans, t)
    
print(ans)
### BUGGY CODE ###

import math, queue

h, w = map(int, input().split(" "))
sY, sX = map(int, input().split(" "))
gY, gX = map(int, input().split(" "))
smap = [list(input()) for _ in range(h)]
visited = [[False for _ in range(w)] for _ in range(h)]

for y in range(h):
    for x in range(w):
        if smap[y][x] == ".":
            smap[y][x] = 100000000000

sY, sX = sY - 1, sX - 1
gY, gX = gY - 1, gX - 1

q = queue.Queue()
q.put([sY, sX])
smap[sY][sX] = 0
visited[sY][sX] = True

mv0 = [[-1, 0], [1, 0], [0, -1], [0, 1]]
mv1 = [[-1, -1], [1, -1], [-1, 1], [1, 1], [-2, -2], [-2, -1],
       [-2, 0], [-2, 1], [-2, 2], [-1, 2], [0, 2], [1, 2], [2, 2], [2, 1],
       [2, 0], [2, 1], [2, -2], [1, -2], [0, -2], [-1, -2]]

while q.qsize() != 0:
    crntY, crntX = q.get()
    for i, [stepY, stepX] in enumerate(mv0 + mv1):
        nextY = crntY + stepY
        nextX = crntX + stepX
        if nextY < 0 or h <= nextY or nextX < 0 or w <= nextX:
            continue
        if visited[nextY][nextX] or smap[nextY][nextX] == "#":
            continue
        cost = smap[crntY][crntX]
        if i >= 4:
            cost += 1
        smap[nextY][nextX] = min(cost, smap[nextY][nextX])
        q.put([nextY, nextX])
    visited[crntY][crntX] = True

if smap[gY][gX] == 100000000000:
    print(-1)
else:
    print(smap[gY][gX])

### FIXED CODE ###

import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())
cy -= 1
cx -= 1
gy -= 1
gx -= 1
grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())
q = deque()
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e + 1)
                    continue
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e + 1))
print(-1 if ans == float("inf") else ans)
### BUGGY CODE ###

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

for i in range(N):
    ans = 0
    a = A[:i]+A[i+1:]
    C = collections.Counter(a)
    for v in C.values():
        ans += (v*(v-1))//2
    print(ans)

### FIXED CODE ###

import collections

def main(): 
    N = int(input())
    A = list(map(int, input().split()))
    cnt = [0]*(N+1)
    C = collections.Counter(A)
    
    for k, v in C.items():
        cnt[k] = v*(v-1)//2
    S = sum(cnt)
    
    for i in A:
        print(S - cnt[i] + (C[i]-1)*(C[i]-2)//2)
        
main()
### BUGGY CODE ###

import numpy as np

def solve(_list,_k):
  start = 0
  sum = -1
  for i in range(len(_l)-_k+1):
    s = np.sum(_l[i:i+_k])
    if sum < s:
      sum = s
      start = i

  ans = 0.
  for item in _l[start:start+_k]:
    upper = np.sum([j for j in range(item+1)])
    ans += upper / item

  return ans


if __name__ == "__main__":
  _n, _k = map(int, input().split())
  _l = [int(i) for i in input().split()]
  _l = np.array(_l)

  result = solve(_l, _k)
  print(result)


### FIXED CODE ###

def solve(_list,_k):
  accumulate_list = [0.]
  for i in _list:
    accumulate_list.append((i+1)/2 + accumulate_list[-1])

  ans = -1.0
  for i in range(len(accumulate_list)-_k):
    ans = max(ans, accumulate_list[i+_k]-accumulate_list[i])
  return ans

if __name__ == "__main__":
  _n, _k = map(int, input().split())
  _l = [int(i) for i in input().split()]

  result = solve(_l, _k)
  print(result)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
a_old = 1
for i in range(K):
    a_old = a_old*A[i]
a_new = a_old
for i in range(K, N):
    a_new = (a_old // A[i-K])*A[i]
    if a_new > a_old:
        print('Yes')
    else:
        print('No')
    a_old = a_new

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
a = K
b = 0
for _ in range(N-K):
    if A[a] > A[b]:
        print('Yes')
    else:
        print('No')
    a += 1
    b += 1
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import collections
import itertools


def solve(N: int, S: str):
    dp = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        if S[i] == S[-1]:
            dp[i][N-1] = 1

    res = 0
    for i in range(N-2,-1,-1):
        for j in range(N-2,i,-1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1
                l = dp[i][j]
                if j >= i+l:
                    res = max(res,l)

    print(res)



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections
import itertools


def solve(N: int, S: str):
    dp = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        if S[i] == S[-1]:
            dp[i][N-1] = 1

    res = 0
    for i in range(N-2,-1,-1):
        for j in range(N-2,i,-1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1
                l = dp[i][j]
                if j >= i+l:
                    res = max(res,l)

    print(res)



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

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

import math

class SegmentTree():
    def __init__(self, size):
        self.size = 2**((size-1).bit_length())
        self.val = [0]*(self.size*2)
    
    def update(self, i, x):
        i += self.size
        self.val[i] = x
        
        while i > 0:
            i = i >> 1
            self.val[i] = self.val[2*i] + self.val[2*i+1]
    
    def rangeSum(self, l, r):
        l += self.size
        r += self.size

        l_sum = 0
        r_sum = 0

        while l < r:
            if l & 1:
                l_sum += self.val[l]
                l += 1
            l = l >> 1

            if r & 1:
                r -= 1
                r_sum += self.val[r]
            r = r >> 1

        return l_sum + r_sum
        
p = 998244353

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

hop = []

for i in range(K):
    L, R = map(int, input().split())
    for j in range(L, R + 1):
        hop.append(j)

dp = SegmentTree(N)

dp.update(0,1)

for i in range(N - 1):
    for j in range(len(hop)):
        d_val = dp.rangeSum(i, i + 1) % p
        if i + hop[j] < N:
            d_val_n = dp.rangeSum(i + hop[j], i + hop[j] + 1) % p
            dp.update(i + hop[j], d_val_n + d_val)

print(dp.rangeSum(N - 1, N) % p)

### FIXED CODE ###

class BITRAQ:
    def __init__(self, n, mod):
        self.n = n + 1
        self.mod = mod
        self.bit = [[0]*(self.n) for _ in range(2)]
    
    def add_sub(self, p, i, x):
        while i < self.n:
            self.bit[p][i] += x
            self.bit[p][i] %= self.mod
            i += i & -i
    
    def add(self, l, r, x):
        self.add_sub(0, l, -x * (l - 1))
        self.add_sub(0, r, x * (r - 1))
        self.add_sub(1, l, x)
        self.add_sub(1, r, -x)

    def sum_sub(self, p, i):
        s = 0
        while i > 0:
            s += self.bit[p][i]
            i -= i & -i
        return s
    
    def sum(self, i):
        return self.sum_sub(0, i) + self.sum_sub(1, i) * i

    def get(self, i):
        return self.sum(i) % self.mod - self.sum(i - 1) % self.mod

p = 998244353

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

hop = []

for i in range(K):
    hop.append(tuple(map(int, input().split())))

dp = BITRAQ(N, p)

dp.add(1, 2, 1)

for i in range(N - 1):
    for j in range(K):
        dp.add(i + hop[j][0] + 1, min(N + 1, i + hop[j][1] + 2), dp.get(i + 1) % p)

print(dp.get(N) % p)
### BUGGY CODE ###

s = input()

dp = [[0 for j in range(4)] for i in range(len(s)+1)]
dp[0][0] = 1
mod = 10**9+7
for i in range(len(s)):
    for j in range(4):
        dp[i+1][j] = dp[i][j]
        dp[i+1][j] %= mod
    if s[i] == "A":
        dp[i+1][1] += dp[i][0]
    elif s[i] == "B":
        dp[i+1][2] += dp[i][1]
    elif s[i] == "C":
        dp[i+1][3] += dp[i][2]
    else:
        dp[i+1][0] += dp[i][0] * 2
        dp[i+1][1] += dp[i][1] * 2 + dp[i][0]
        dp[i+1][2] += dp[i][2] * 2 + dp[i][1]
        dp[i+1][3] += dp[i][3] * 2 + dp[i][2]

print(dp[-1][3]%mod)


### FIXED CODE ###

s = input()

dp = [[0 for j in range(4)] for i in range(len(s)+1)]
dp[0][0] = 1
mod = 10**9+7
for i in range(len(s)):
    for j in range(4):
        dp[i+1][j] = dp[i][j]
        dp[i+1][j] %= mod
        dp[i][j] %= mod
    if s[i] == "A":
        dp[i+1][1] += dp[i][0]
    elif s[i] == "B":
        dp[i+1][2] += dp[i][1]
    elif s[i] == "C":
        dp[i+1][3] += dp[i][2]
    else:
        dp[i+1][0] += dp[i][0] * 2
        dp[i+1][1] += dp[i][1] * 2 + dp[i][0]
        dp[i+1][2] += dp[i][2] * 2 + dp[i][1]
        dp[i+1][3] += dp[i][3] * 2 + dp[i][2]

print(dp[-1][3]%mod)
### BUGGY CODE ###

import math

X = int(input())

i = 0
while True:
   i += 1
   a = math.pow((X + math.pow(i, 5)), float(1/5))
   if a.is_integer():
      print("%d %d" % (a, i))
      exit()


### FIXED CODE ###

import sys
x = int(input())

for i in range(-1000, 1001):
    for j in range(-1000, 1001):
        if i**5-j**5 == x:
            print(i, j)
            sys.exit()
### BUGGY CODE ###

import bisect
while True:
    N,M=map(int,raw_input().split())
    if N==M==0:break
    L=[input() for i in range(N)]
    L.append(0)
    S=set(i+j for i in L for j in L)
    B=sorted(S)
    maxInt=0
    for i in B:
        if i>M:break
        idx=bisect.bisect(B,M-i)
        if i+B[idx-1]<=M:
            maxInt=max(maxInt,i+B[idx-1])
    print maxInt

### FIXED CODE ###

import bisect
while True:
    N,M=map(int,raw_input().split())
    if N==M==0:break
    L=[input() for i in range(N)]
    L.append(0)
    S=set(i+j for i in L for j in L)
    B=sorted(S)
    t=bisect.bisect(B,M)-1
    maxInt=max(i+B[bisect.bisect(B,M-i)-1] for i in B[:t])
    print maxInt
### BUGGY CODE ###

from collections import Counter

N = int(input())
As = list(map(int, input().split()))
count = sorted(Counter(As).items(), key = lambda x: x[0])

ans = 0
for num, c in count:
  if c > 1:
    continue
  flag = True
  for i, c2 in count:
    if i == num:
      break
    if num % i == 0:
      flag = False
      break
  if flag:
    ans += 1
  
print(ans)

### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
M = max(A_list)+1
cnt = [0 for _ in range(M)]

for i in A_list:
    if cnt[i] != 0:
        cnt[i] = 2
        continue
    for j in range(i, M, i): cnt[j] += 1

ans = 0
for k in A_list:
    if cnt[k] == 1: ans += 1
print(ans)
### BUGGY CODE ###

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

num = Counter(A)

for i in range(Q):
  b,c = map(int,input().split())
  num[c] += num[b]
  num[b] = 0
  ans = 0
  for i in num:
      ans += i * num[i] 
  print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
ans = sum(A)
num = Counter(A)
for i in range(Q):
    b,c = map(int,input().split())

    ans += (c-b)*num[b]
    num[c] += num[b] 
    num[b] = 0
    
    print(ans)
### BUGGY CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    H, W, M = map(int, input().split())
    Hlist = [0] * H
    Wlist = [0] * W
    hwmatrix = [[0 for _ in range(W)] for _ in range(H)]

    for _ in range(M):
        h, w = map(int, input().split())
        Hlist[h-1] += 1
        Wlist[w-1] += 1
        hwmatrix[h-1][w-1] = 1

    hmax = [i for i, x in enumerate(Hlist) if x == max(Hlist)]
    wmax = [i for i, x in enumerate(Wlist) if x == max(Wlist)]

    flag = False
    for h in hmax:
        for w in wmax:
            if hwmatrix[h][w] == 0:
                flag = True
                break

    if flag:
        print(Hlist[h] + Wlist[w])
    else:
        print(Hlist[h] + Wlist[w] - 1)





if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    input = readline
    mod = 10 ** 9 + 7
    H, W, M = map(int, input().split())
    Hlist = collections.defaultdict(int)
    Wlist = collections.defaultdict(int)
    hw = []

    for _ in range(M):
        h, w = map(int, input().split())
        Hlist[h-1] += 1
        Wlist[w-1] += 1
        hw.append([h, w])

    #hmax = [i for i, x in enumerate(Hlist) if x == max(Hlist)]
    #wmax = [i for i, x in enumerate(Wlist) if x == max(Wlist)]

    Hlist = sorted(Hlist.items(), key=lambda x: x[1], reverse=True)
    Wlist = sorted(Wlist.items(), key=lambda x: x[1], reverse=True)

    hmaxset = set()
    wmaxset = set()

    maxH = Hlist[0][1]
    for k, v in Hlist:
        if v != maxH:
            break
        else:
            hmaxset.add(k)

    maxW = Wlist[0][1]
    for k, v in Wlist:
        if v != maxW:
            break
        else:
            wmaxset.add(k)


    flag = False
    count = 0
    for hh in hw:
        h = hh[0] - 1
        w = hh[1] - 1
        if h in hmaxset and w in wmaxset:
            count += 1

    lenhmax = len(hmaxset)
    lenwmax = len(wmaxset)

    if count != lenhmax * lenwmax:
        flag = True

    if flag:
        print(maxH + maxW)
    else:
        print(maxH + maxW - 1)





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

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    s=input()
    len_s=len(s)
    mod=10**9+7
    dp=[[0]*13 for _ in range(len_s+1)] #i(1-)桁目までについて，13で割った余り
    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]%mod
        else:
            c=int(s[i])
            for j in range(13):
                dp[i+1][(10*j+c)%13]=dp[i][j]
        for j in range(13):
            dp[i+1][j]%=mod
    print(dp[len_s][5])

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    s=input()
    len_s=len(s)
    mod=10**9+7
    dp=[[0]*13 for _ in range(len_s+1)] #i(1-)桁目までについて，13で割った余り
    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]%mod
        else:
            c=int(s[i])
            for j in range(13):
                dp[i+1][(10*j+c)%13]=dp[i][j]
        for j in range(13):
            dp[i+1][j]%=mod
    print(dp[len_s][5])

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

# coding: utf-8
N = int(input())
a = list(map(int, input().split()))
num = 1
if num not in a:
    print(-1)
    exit()
else:
    while len(a) >= 1:
        if num in a:
            a = a[a.index(num) +1 :]
            num += 1
    else:
        print(N - num + 1)

### FIXED CODE ###

# coding: utf-8
N = int(input())
a = list(map(int, input().split()))
num = 0
for i in range(N):
    if a[i] == num + 1:
        num += 1
if num == 0:
    print(-1)
else:
    print(N - num)
### BUGGY CODE ###

n, w = list(map(int, input().strip().split()))
data = []
for i in range(n):
    data.append(list(map(int, input().strip().split())))

dp = [None] * n

# i 個までで重さを z 以下にしたときの最大値
def rec(i, z):
    if i < 0:
        return 0
    # i 個目のものを入れられない場合
    if data[i][0] > z:
        return rec(i - 1, z)

    # 入れられる場合、入れるときと入れないときのうち大きい方を返す
    # 入れるとき
    v1 = data[i][1] + rec(i - 1, z - data[i][0])
    # 入れないとき
    v2 = rec(i - 1, z)
    return max(v1, v2)

print(rec(n - 1, w))

### FIXED CODE ###

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

# i番目に重さがj以下となるように選んだときの価値の総和の最大値
dp = [[0] * (w + 1) for _ in range(n)]

for i in range(0, n):
    for j in range(w + 1):
        # i 番目の品物の重さと価値
        wi, vi = data[i]
        if i == 0:
            take = vi if j - wi >= 0 else 0
            miss = 0
            dp[i][j] = max(take, miss)
        else:
            # i番目の品物を入れる場合
            take = dp[i - 1][j - wi] + vi if j - wi >= 0 else 0
            # 入れない場合
            miss = dp[i - 1][j]
            dp[i][j] = max(take, miss)

print(max(dp[n - 1]))