Harryxun/stf_run huggingface dataset:
N = int(input())
A = list(map(int, input().split()))

ans = 0
i = 0
while i < N-3:
  tmp = i
  while (A[tmp+1]-A[tmp])*(A[tmp+2]-A[tmp+1])>=0:
    tmp += 1
    if tmp == N-3:
      break
  ans += 1 
  i = tmp+2
else:
  if (A[N-2]-A[N-3])*(A[N-1]-A[N-3])>=0:
    ans += 1
  else:
    ans += 2
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    i = 0
    while 1:
        if i == N:
            break
        # 単調非減少と単調非増加の列の長い方を採用Greedy
        a = i
        while a < N-1 and A[a] <= A[a+1]:
            a += 1
        b = i
        while b < N-1 and A[b] >= A[b+1]:
            b += 1
        i = max(a,b) + 1
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()
b=input()
if b='A':
    print('T')
elif b='T':
    print('A')
elif b='G':
    print('C')
else:
    print('G')

### FIXED CODE ###

b=input()
if b=='A':
    print('T')
elif b=='T':
    print('A')
elif b=='G':
    print('C')
else:
    print('G')
sum=0
for i in range(5):
  y=int(input())
  x=y%10
  if x==0:
    sum+=y
  else:
    min=min(x, 9)
    if x==min:
      sum+=y

### FIXED CODE ###

X=[int(input()) for i in range(5)]
Y=[]
for x in X:
  Y.append(-(-x//10)*10-x)
print(sum(X)+sum(Y)-(max(Y)))
if D==23:
    print "Christmas Eve Eve"

if D==24:
    print "Christmas Eve"

if D==23:
    print "Christmas "


### FIXED CODE ###

D = int(input())

if D==22:
    print ("Christmas Eve Eve Eve")

if D==23:
    print ("Christmas Eve Eve")

if D==24:
    print ("Christmas Eve")

if D==25:
    print ("Christmas ")
from bisect import bisect
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans = 0
b_c= [0]*n
for i  in range(n-2):
    a = l[i]
    pre_k = 2
    for j in range(i+1,n-1):
        b = l[j]
        max_c = a+b-1
        k = bisect(l[j+pre_k-1:],max_c)
        ans += (pre_k-2 + )
print(ans)

### FIXED CODE ###

from bisect import bisect_left
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans = 0
for i  in range(n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        k = bisect_left(l,a+b)
        ans += k-j-1
print(ans)
x=int(input())

for i in range(1,120):
    for j in range(-120,120):
        if ((i**5)-(j**5))==x:
            print(i, j)
            exit()


### FIXED CODE ###

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

x=min(N,B-1)

ans=((A*x)//B)-(A*(x//B))
print(ans)
s = input()
c1 = 1 if s[0] == '0' else 0
a = []
a.append('1')
for i in range(1,len(s)):
  if s[i] == a[len(a)-1]:
    c1+=1
    a.append('0' if s[i]=='1' else '1')
  else:
    a.append(s[i])
    
a = []
c2 = 1 if s[0]=='1' else 0
for i in range(1,len(s)):
  if s[i] == a[len(a)-1]:
    c2+=1
    a.append('0' if s[i]=='1' else '1')
  else:
    a.append(s[i])
    
    
print(min(c1,c2))
  

    
    



### FIXED CODE ###

s = input()
c1 = 1 if s[0] == '0' else 0
a = []
a.append('1')
for i in range(1,len(s)):
  if s[i] == a[len(a)-1]:
    c1+=1
    a.append('0' if s[i]=='1' else '1')
  else:
    a.append(s[i])
    
a = []
a.append('0')
c2 = 1 if s[0]=='1' else 0
for i in range(1,len(s)):
  if s[i] == a[len(a)-1]:
    c2+=1
    a.append('0' if s[i]=='1' else '1')
  else:
    a.append(s[i])
    
    
print(min(c1,c2))
n,k = map(int,input().split())
s = input()
print(s[:k-1]+s[k-1].lower+s[k:])

### FIXED CODE ###

n,k = map(int,input().split())
s = input()
print(s[:k-1]+s[k-1].lower()+s[k:])
A, B, C, D, E, F = map(int, input().split())

water = []
for i in range(F//(A*100) + 1):
    for j in range(F//(B*100) + 1):
        n = (i*A + j*B)*100
        if n <= F:
            water.append(n)
water = sorted(list(set(water)))

result = {}
noud = []
for i in water:
    suger_limit = E*(i//100)
    for j in range(suger_limit//C + 1):
        for k in range(suger_limit//D + 1):
            n = j*C + k*D
            if n <= suger_limit and i + n <= F and n != 0:
                noudo = 100*n/(i+n)
                noud.append(noudo)
                
                result[str(noudo)] = [i+n,n]


print(result[str(max(noud))])


### FIXED CODE ###

A, B, C, D, E, F = map(int, input().split())

water = []
for i in range(F//(A*100) + 1):
    for j in range(F//(B*100) + 1):
        n = (i*A + j*B)*100
        if n <= F:
            water.append(n)
water = sorted(list(set(water)))

density_d = {}
density = []

for i in water:
    suger_limit = E*(i//100)

    suger = []

    for j in range(suger_limit//C + 1):
        for k in range(suger_limit//D + 1):
            n = j*C + k*D
            if n <= suger_limit and n + i <= F:
                suger.append(n)
    suger = max(suger)
    if i+suger == 0:
        continue
    else:
        density.append(100*suger/(i+suger))
        density_d[100*suger/(i+suger)] = [i + suger, suger]
density = list(set(density))
a, b = map(int, density_d[max(density)])
print(a,b)
n = int(input())
s = input()

before = [[-1] * 10]

for i in range(n):
  c = s[i]
  num = int(c)
  hoge = before[-1][::]
  hoge[num] = i
  before.append(hoge)

for i in range(10):
  now = before[-1][i]
  if now == -1:
    continue
  for j in range(10):
    now2 = before[now][j]
    if now2 == -1:
      continue
    for k in range(10):
      now3 = before[now2][k]
      if now3 == -1:
        continue
      ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

before = [[-1] * 10]

for i in range(n):
  c = s[i]
  num = int(c)
  hoge = before[-1][::]
  hoge[num] = i
  before.append(hoge)
ans = 0
for i in range(10):
  now = before[-1][i]
  if now == -1:
    continue
  for j in range(10):
    now2 = before[now][j]
    if now2 == -1:
      continue
    for k in range(10):
      now3 = before[now2][k]
      if now3 == -1:
        continue
      ans += 1
print(ans)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors

ans=[0]*n
count=[0]*n
n=int(input())
a=list(map(int,input().split()))
for i in range(n,0,-1):
    if count[i-1]%2!=a[i-1]:
        ans[i-1]=1
        b=make_divisors(i)
        for j in b:
            count[b-1]+=1
print(sum(ans))
kai=[]
for i in range(n):
    if ans[i]==1:
        kai.append(i+1)
print(*kai)

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors
n=int(input())
ans=[0]*n
count=[0]*n

a=list(map(int,input().split()))
for i in range(n,0,-1):
    if count[i-1]%2!=a[i-1]:
        ans[i-1]=1
        b=make_divisors(i)
        for j in b:
            count[j-1]+=1
print(sum(ans))
kai=[]
for i in range(n):
    if ans[i]==1:
        kai.append(i+1)
print(*kai)
n = int(input())
iro = [-1 for i in range(n+1)]
dp = [1 for i in range(n+1)]
mod = 10**9 + 7
for i in range(1,n+1):
    dp[i] = dp[i-1]
    now = int(input())
    if iro[now] == -1:
        iro[now] = i
    elif iro[now] != i-1:
        dp[i] += dp[iro[now]]
    iro[now] = i
    dp[i] %= mod
print(dp)

### FIXED CODE ###

n = int(input())
iro = [-1 for i in range(2*(10**5)+1)]
dp = [1 for i in range(n+1)]
mod = 10**9 + 7
for i in range(1,n+1):
    dp[i] = dp[i-1]
    now = int(input())
    if iro[now] != -1 and iro[now] != i-1:
        dp[i] += dp[iro[now]]
    iro[now] = i
    dp[i] %= mod
print(dp[n])
A,B=map(int,input().split())
if (A*B)%2==1:
  print(IMPOSSIBLE)
  else
  	print((A+B)/2)


### FIXED CODE ###

A,B=map(int,input().split())
if (A-B)%2==1:
    print("IMPOSSIBLE")
else:
  	print(int((A+B)/2))
n = int(input())
num = [111,222,333,444,555,666,777,888,999]
for i in range(len(num) - 1):
    if num[i] == n:
        x = num[i]
        break
    if num[i] < n and n < num[i+1]:
        mn = min(abs(n - num[i]),abs(n - num[i+1]))
        if mn == abs(n - num[i]):
            x = num[i]
        else:
            x = num[i+1]
        break
print(x)

### FIXED CODE ###

n = int(input())
if n % 111 == 0:
    x = n
else:
    x = ((n // 111) + 1) * 111
print(x)
n = int(input())
s = [int(input()) for _ in range(n)]
m = int(input())
t = [int(input()) for _ in range(m)]

pointList = dict();

for temp in s:
  pointList[temp] = 0
for temp in t:
  pointList[temp] = 0
  
for temp in s:
  pointList[temp] += 1
for temp in t:
  pointList[temp] -= 1
  
ans = max(0, max(pointList.values()))

print(ans)

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
m = int(input())
t = [input() for _ in range(m)]

pointList = dict();

for temp in s:
  pointList[temp] = 0
for temp in t:
  pointList[temp] = 0
  
for temp in s:
  pointList[temp] += 1
for temp in t:
  pointList[temp] -= 1
  
ans = max(0, max(pointList.values()))

print(ans)
n=int(input())
A=sorted(list(map(int,input().split())))
print(sum(A[n//2:])-sum(A[:n//2]))

  
while len(A)>3:  
  a=min(A)
  b=max(A)
  print("{} {}".format(b,a))
  A.remove(a)
  A.remove(b)
  
  A.append(b-a)
A.sort()
print("{} {}".format(A[0],A[1]))
print("{} {}".format(A[2],A[0]-A[1]))
    
    


### FIXED CODE ###

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

if n==2:
    print(abs(A[0]-A[1]))
    print(*A)
    exit()
A.sort()
menos=[] ; plus=[]
for i in range(len(A)):
    if A[i]<0:
        menos.append(A[i])
    else:
        plus.append(A[i])
if menos==[]:
    print(sum(plus)-plus[0]*2)
    res=plus[0]
    for i in range(n-2):
        print(res, A[i+1])
        res=res-A[i+1]
    print(A[n-1], res);exit()
        
elif plus==[]:
    print(-sum(menos)+ menos[-1]*2)
    res=menos[-1]
    for i in range(n-1):
        print(res,menos[i])
        res=res-menos[i]
    exit()
    

print(sum(plus)-sum(menos))
m=len(menos); p=len(plus)
if p==1:
    res=plus[-1]
    for i in range(n-1):
        print(res,menos[i])
        res=res-menos[i]
    exit()
if m==1:
    res=menos[0]
    for i in range(n-2):
        print(res, plus[i])
        res=res-plus[i]
    print(plus[-1], res);exit()

Q= plus[1:]+ [menos[0]]
W= menos[1:]+[plus[0]] ;#print(Q,W)

res=W[-1]
for i in range(len(W)-1):
    print(res,W[i])
    res=res-W[i]
rec=Q[-1]
for i in range(len(Q)-1):
    print(rec, Q[i])
    rec=rec-Q[i]
print(res,rec)
from collections import deque
import sys
sys.setrecursionlimit(10000)
n,m =map(int,input().split())
pas = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    pas[a].append(b)
    pas[b].append(a)

seen = [False for i in range(n)]
que = deque()
def bfn(i,j):
    if seen[i-1]==False:
        seen[i-1]=j
    for x in pas[i]:
        if seen[x-1]!=False:
            continue
        que.append([x,i])
    if que:
        now,pre =que.popleft()
        bfn(now,pre)
    else:
        return

bfn(1,1)

if False in seen:
    print("No")
else:
    print("Yes")
    for i in range(n-1):
        print(seen[i+1])


### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(1000000)
n,m =map(int,input().split())
pas = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    pas[a].append(b)
    pas[b].append(a)

seen = [False for i in range(n)]
que = deque()
def bfn(i,j):
    for x in pas[i]:
        if seen[x-1]!=False:
            continue
        seen[x-1]=i
        que.append([x,i])
    if que:
        now,pre =que.popleft()
        bfn(now,pre)
    else:
        return

bfn(1,1)

if False in seen:
    print("No")
else:
    print("Yes")
    for i in range(n-1):
        print(seen[i+1])
n,k=map(int,input().split())
#####segfunc######
def segfunc(x,y):
    return max(x,y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num


for i in range(n):
  x=int(input())-1
  update(x,query(max(0,x-k),min(n,x+k+1))+1)
print(seg[0])

### FIXED CODE ###

N,k=map(int,input().split())
n=3*10**5+10
#####segfunc######
def segfunc(x,y):
    return max(x,y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num


for i in range(N):
  x=int(input())
  update(x,query(max(0,x-k),min(n,x+k+1))+1)
print(seg[0])
import functools
import operator
n = int(input())
number = map(int,input().split())
X = functools.partial(functools.reduce, operator.mul)
s=X(number)
if s>=pow(10,18):
    print(-1)
else:
    print(s)

### FIXED CODE ###

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

print(a*b)
a,b=map(int, input().split())
print(sum([1:b])-(b-a))

### FIXED CODE ###

a,b=map(int, input().split())
print(int((b-a)*(b-a+1)/2-b))
#54 A - Airport Bus
N,C,K = map(int,input().split())
T = [int(input()) for _ in range(N)]
T = sorted(T,reverse = False)

ans = 0
bus = 1
first = T[0]
for i in range(1,N+1):
    # T[i] がバスに乗ることができるとき
    if (bus < C) and (T[i] <= first + K):
        bus += 1
    # T[i] がバスに乗ることができないとき
    else:
        # 新しいバスの first になる
        ans += 1
        bus = 1
        first = T[i]
        
print(ans+1)

### FIXED CODE ###

#54 A - Airport Bus
N,C,K = map(int,input().split())
T = [int(input()) for _ in range(N)]
T = sorted(T,reverse = False)

ans = 0
bus = 1
first = T[0]
for i in range(1,N):
    # T[i] がバスに乗ることができるとき
    if (bus < C) and (T[i] <= first + K):
        bus += 1
    # T[i] がバスに乗ることができないとき
    else:
        # 新しいバスの first になる
        ans += 1
        bus = 1
        first = T[i]
        
print(ans+1)
w=input()
s=list(set(list(w)))

if len(s) = 2 and w.count(s[0]) = 2:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

w=input()
s=list(set(list(w)))

if len(s) == 2 and w.count(s[0]) == 2:
  print("Yes")
else:
  print("No")
import math
a,b = map(int, input().split())
print(math.ceil((a+b) / 2)

### FIXED CODE ###

import math
a,b = map(int, input().split())
print(math.ceil((a+b) / 2))
import collections
N,K = map(int,input().split())
dic = {}
A = []
for _ in range(N):
    t,d = map(int,input().split())
    A.append([t,d])
A.sort(key = lambda x:x[1],reverse = True)
val = 0
set_= set()
D = collections.deque([])
for t,d in A[:K]:
    val += d
    if t in set_:
        D.append(d)
    else:
        set_.add(t)
now = val + len(set_)**2
nx = collections.deque(A[K:])
ans = now
c = len(set_)
while len(set_)<K and nx:
    i,j = nx.popleft()
    if i in set_:
        continue
    d = D.pop()
    diff = j-d+2*c+1
    set_.add(j)
    now += diff
    ans = max(ans,now)
    c +=1
print(ans)

### FIXED CODE ###

import collections
N,K = map(int,input().split())
dic = {}
A = []
for _ in range(N):
    t,d = map(int,input().split())
    A.append([t,d])
A.sort(key = lambda x:x[1], reverse = True)
val = 0
set_ = set()
duplicated = collections.deque([])
for t,d in A[:K]:
    val += d
    if t in set_:
        duplicated.append(d)
    else:
        set_.add(t)
now = val + len(set_)**2

nx = collections.deque(A[K:])
ans = now
c = len(set_)
while len(set_) < K and nx:
    i,j = nx.popleft()
    if i in set_:
        continue
    d = duplicated.pop()
    diff = j-d + 2*c+1
    set_.add(i)
    now += diff
    ans =max(ans,now)
    c += 1
print(ans)
s = input()
t = ''
while i <= len(s):
  t += s[i]
  i += 2
print(t)

### FIXED CODE ###

s = input()
t = ''
i = 0
while i <= len(s)-1:
  t += s[i]
  i += 2
print(t)
N = int(input())
List = [] * N
List = input().split(" ")
List.sort()
for i in range(N-1):
    List[i+1] = (int(List[i]) + int(List[i+1]) / 2
print(List[N])

### FIXED CODE ###

N = int(input())
List = [] * N
List = input().split(" ")
for i in range(N):
    List[i] = float(List[i]) 
List.sort()
for i in range(N-1):
    List[i+1] = ( List[i] + List[i+1] ) / 2
print(List[N-1])
K, X = input(), input()

if 500*K >= X:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

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

if 500*K >= X:
  print("Yes")
else:
  print("No")
h,w = map(int,input().split())
hw = []
for i in range(h):
    hw.append(input())

todo = [(0,0)]
seen = [[200 for j in range(w)] for i in range(h)]
sx = 0
sy = 0
if hw[0][0] == '.':
    seen[0][0] = 0
else:
    seen[0][0] = 1




while len(todo)>0:
    sx,sy = todo.pop(0)
    if sx + 1 < w and hw[sx+1][sy] == '.' and seen[sx+1][sy] > seen[sx][sy]:
        seen[sx+1][sy] = seen[sx][sy]
        todo.append((sx+1,sy))
    if sx + 1 < w and hw[sx+1][sy] == '#' and seen[sx+1][sy] > seen[sx][sy]+1:
        seen[sx+1][sy] = seen[sx][sy]+1
        todo.append((sx+1,sy))
    if sy + 1 < h and hw[sx][sy+1] == '.' and seen[sx][sy+1] > seen[sx][sy]:
        seen[sx][sy+1] = seen[sx][sy]
        todo.append((sx,sy+1))
    if sy + 1 < h and hw[sx][sy+1] == '#' and seen[sx][sy+1] > seen[sx][sy]+1:
        seen[sx][sy+1] = seen[sx][sy]+1
        todo.append((sx,sy+1))



print(seen[h-1][w-1])

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
hw = []
for i in range(h):
    hw.append(input())

todo = deque([(0,0)])
seen = [[200 for j in range(w)] for i in range(h)]
sx = 0
sy = 0
if hw[0][0] == '.':
    seen[0][0] = 0
else:
    seen[0][0] = 1




while todo:
    sx,sy = todo.popleft()
    if sx + 1 < h and seen[sx+1][sy] == 200:
        todo.append((sx+1,sy))
    if sx + 1 < h and hw[sx+1][sy] == '.' and seen[sx+1][sy] > seen[sx][sy]:
        seen[sx+1][sy] = seen[sx][sy]
    if sx + 1 < h and hw[sx+1][sy] == '#' and seen[sx+1][sy] > seen[sx][sy]+1 and hw[sx][sy] == '.':
        seen[sx+1][sy] = seen[sx][sy]+1
    if sx + 1 < h and hw[sx+1][sy] == '#' and seen[sx+1][sy] > seen[sx][sy] and hw[sx][sy] == '#':
        seen[sx+1][sy] = seen[sx][sy]
    if sy+1 < w and seen[sx][sy+1] == 200:
        todo.append((sx,sy+1))
    if sy + 1 < w and hw[sx][sy+1] == '.' and seen[sx][sy+1] > seen[sx][sy]:
        seen[sx][sy+1] = seen[sx][sy]
    if sy + 1 < w and hw[sx][sy+1] == '#' and seen[sx][sy+1] > seen[sx][sy]+1 and hw[sx][sy] == '.':
        seen[sx][sy+1] = seen[sx][sy]+1
    if sy + 1 < w and hw[sx][sy+1] == '#' and seen[sx][sy+1] > seen[sx][sy] and hw[sx][sy] == '#':
        seen[sx][sy+1] = seen[sx][sy]



print(seen[h-1][w-1])
N, M =map(int,input().split())
ans=1
for i in range (1,M//N):
    if M%i==0:
        if M//i>=N:
            ans=i
print(ans)

### FIXED CODE ###

N=int(input())
if N == 1:
    print ('Hello World')
else:
    A =int(input())
    B =int(input())
    print(A+B)
s = input()
N = len(s)
s_trim = ''.join([c for c in s if c != 'x'])
N_trim = len(s_trim)

def check_anagram():
    for i in range(N_trim):
        j = N_trim - 1 - i
        if s_trim[i] != s_trim[j]:
            return False
    return True

def solve():
    if not check_anagram():
        return -1

    # Center of anagram
    pr = N_trim // 2
    pl = pr
    if N_trim % 2 == 0:
        pl -= 1

    xl = 0
    tl = 0
    while xl < N:
        if s[xl] != 'x':
            assert s[xl] == s_trim[tl]
            if tl == pl:
                break
            tl += 1
        xl += 1

    if N_trim % 2 == 1:
        xr = xl
    else:
        xr = xl + 1
        while s[xr] == 'x':
            xr += 1

    cost = 0
    while True:
        # assert s[xl] == s_trim[pl]
        if s[xl] != s_trim[pl]:
            while True: pass
        assert s[xr] == s_trim[pr]
        assert s[xl] == s[xr]
        assert s_trim[pl] == s_trim[pr]
        pl -= 1; pr += 1
        while True:
            xl -= 1; xr += 1
            if not (xl >= 0 and xr < N and s[xl] == 'x' and s[xr] == 'x'):
                break
        while xl >= 0 and s[xl] == 'x':
            cost += 1
            xl -= 1
        while xr < N and s[xr] == 'x':
            cost += 1
            xr += 1
        if pl < 0 and pr >= N_trim and xl < 0 and xr >= N:
            return cost

print(solve())


### FIXED CODE ###

s = input()
N = len(s)
s_trim = ''.join([c for c in s if c != 'x'])
N_trim = len(s_trim)

def check_anagram():
    for i in range(N_trim):
        j = N_trim - 1 - i
        if s_trim[i] != s_trim[j]:
            return False
    return True

def solve():
    if not check_anagram():
        return -1
    if N_trim == 0:
        return 0
    # Center of anagram
    pr = N_trim // 2
    pl = pr
    if N_trim % 2 == 0:
        pl -= 1

    xl = 0
    tl = 0
    while xl < N:
        if s[xl] != 'x':
            # assert s[xl] == s_trim[tl]
            if tl == pl:
                break
            tl += 1
        xl += 1

    if N_trim % 2 == 1:
        xr = xl
    else:
        xr = xl + 1
        while s[xr] == 'x':
            xr += 1

    cost = 0
    while True:
        # assert s[xl] == s_trim[pl]
        # assert s[xr] == s_trim[pr]
        # assert s[xl] == s[xr]
        # assert s_trim[pl] == s_trim[pr]
        pl -= 1; pr += 1
        while True:
            xl -= 1; xr += 1
            if not (xl >= 0 and xr < N and s[xl] == 'x' and s[xr] == 'x'):
                break
        while xl >= 0 and s[xl] == 'x':
            cost += 1
            xl -= 1
        while xr < N and s[xr] == 'x':
            cost += 1
            xr += 1
        if pl < 0 and pr >= N_trim and xl < 0 and xr >= N:
            return cost

print(solve())
N = int(input())
dp = [[0]*(N + 1)*100 for i in range(N + 1)]
for i in range(1,N+1):
    cs = int(input())
    dp[i][cs] = cs
    U_List = [k for k, x in enumerate(dp[i-1]) if x != 0]
    for j in U_List:
        dp[i][j+cs] = j + cs
print(max([k for k, x in enumerate(dp[-1]) if x % 10 != 0]))

### FIXED CODE ###

N = int(input())
dp = [0]
for i in range(N):
    P = int(input())
    dp_p = list(map(lambda x:x + P,dp))
    dp = list(set(dp + dp_p))

P_List = [0] + [i for i in dp if i % 10 != 0]
print(max(P_List))
import sys
input = sys.stdin.readline

def main3():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = [0]*(W+1)

    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for w, v in wv:
        for i in range(W, w-1, -1):
            tmp = dp[i-w] + v
            if dp[i] < tmp:
                dp[i] = tmp
        #print(dp,sep="\n")

    #4:出力
    print(max(dp))

if __name__ == '__main__':
    main3()

### FIXED CODE ###

def main():
    #1:初期化
    N,W = map(int,input().split())
    dp = [W+1]*(N*10**3+1)

    #2:初期値
    dp[0] = 0

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = map(int,input().split())
        for i in range(N*10**3, v-1, -1):
            tmp = dp[i-v] + w
            if dp[i] > tmp:
                dp[i] = tmp
        #print(dp,sep="\n")

    #4:出力
    output = 0
    for i in range(N*10**3+1):
        if dp[i] <= W:
            output = i
    print(output)

if __name__ == '__main__':
    main()
import heapq

N, M = map(int, input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(A)

for _ in range(M):
    tmp = heapq.heappop(A)
    heapq.heappush(A, tmp/2)

A = map(lambda x: int(x)*(-1), A)

print(sum(A))

### FIXED CODE ###

S = input()

if S == "Sunny":
    print("Cloudy")
elif S == "Cloudy":
    print("Rainy")
else:
    print("Sunny")