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

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(3*n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[3*u].append(3*v+1)
        E[3*u+1].append(3*v+2)
        E[3*u+2].append(3*v)
    s,t=map(int,input().split())
    s-=1; t-=1

    # DFS
    from collections import deque
    d=[INF]*(3*n)
    d[3*s]=0
    stack=[]
    stack.append(3*s)
    while(stack):
        v=stack.pop()
        for nv in E[v]:
            if(d[nv]>d[v]+1):
                d[nv]=d[v]+1
                stack.append(nv)
    ans=d[3*t]
    print(ans//3 if(ans!=INF) else -1)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(3*n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[3*u].append(3*v+1)
        E[3*u+1].append(3*v+2)
        E[3*u+2].append(3*v)
    s,t=map(int,input().split())
    s-=1; t-=1

    # BFS (startは0、goalは3n-3)
    from collections import deque
    d=[-1]*(3*n)
    d[3*s]=0
    Q=deque()
    Q.append(3*s)
    while(Q):
        v=Q.popleft()
        for nv in E[v]:
            if(d[nv]!=-1): continue
            d[nv]=d[v]+1
            Q.append(nv)
    ans=d[3*t]
    print(ans//3 if(ans!=-1) else -1)
resolve()
### BUGGY CODE ###

n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]
co=[]
def dfs(d,s):
    global n,co,m
    if d==n-1:
        co.append(s)
    else:
        l=int(s[-1])
        for i in range(l,m+1):
            dfs(d+1,s+str(i))
for i in range(1,m+1):
    dfs(0,str(i))
ans=0
for i in co:
    ans_=0
    for k in range(q):
        a,b,c,d=Q[k]
        if int(i[b-1])-int(i[a-1])==c:
            ans_+=d
    ans=max(ans,ans_)
print(ans)

### FIXED CODE ###

n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]
ans=0
#めっちゃfor分あるならdfs
R=[range(i,m) for i in range(m)]
def dfs(d,s):
    global n,m,Q,ans
    if d==n:
        ans_=0
        for k in Q:
            a,b,c,e=k
            if int(s[b-1])-int(s[a-1])==c:
                ans_+=e
        ans=max(ans,ans_)
    else:
        l=int(s[-1])
        for i in R[l]:
            dfs(d+1,s+str(i))
for i in R[0]:
    dfs(1,str(i))

print(ans)
### 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]:
        try:
            tenbou.remove(hasi2)
        except:
            pass
        #print(tenbou)
    if HEIGHT[hasi1-1] < HEIGHT[hasi2-1]:
        try:
            tenbou.remove(hasi1)
        except:
            pass
       #print(tenbou)
    if 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 ###

def main():
    N = int(input())
    ans = 1
    for a in [int(x) for x in input().split()]:
        ans *= a
    if ans > 10**18:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    if 0 in A:
        print(0)
        return
    ans = 1
    for a in A:
        ans *= a
        if ans > 10**18:
            print(-1)
            return
    print(ans)

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

from bisect import insort

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

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

a.sort()

for _ in range(m):
    max_product = a.pop(-1)
    max_product //= 2
    insort(a,  max_product)
print(sum(a))

### FIXED CODE ###

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

t = list(map(int,input().split()))

for i in range(n):
    t[i] = -t[i]

t.sort()

for i in range(m):
    x=heapq.heappop(t)
    x = -x
    x = int(x/2)
    heapq.heappush(t,-x)
    #print(t)
print(-sum(t))
### BUGGY CODE ###

from collections import defaultdict
n,p = [int(x) for x in input().split()]
s = input()
if p!=2 and p!=5:
  r = defaultdict(int)
  a = int(s)
  r[a%p]+=1
  for i in range(n):
    a = a-int(s[i])*pow(10,(n-1-i))
    r[a%p]+=1
  #print(r)
  ans = 0
  cnt=1
  for i in r.values():
    ans+=i*(i-1)//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)

### FIXED CODE ###

from collections import defaultdict,deque
import itertools
n,p = [int(x) for x in input().split()]
s = list(input())
if p!=2 and p!=5:
  r = defaultdict(int)
  a =[]
  s1 = s[::-1]
  for i in range(n):
    a.append((int(s1[i])%p*pow(10,i,p))%p)
  a = [0]+a[::-1]
  b = list(itertools.accumulate(a))
  for i in b:
    r[i%p]+=1
  ans = 0
  for i in r.values():
    ans+=(i*(i-1))//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    X = list(map(int, input().split()))
    X_s = sorted(X)
    for i in range(n):
        idx = X_s.index(X[i])
        if idx <= n // 2 - 1:
            print(X_s[n // 2])
        else:
            print(X_s[n // 2 - 1])


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
xs = sorted(x)
for i in range(n):
    if x[i] <= xs[n // 2 - 1]:
        res = xs[n // 2]
    else:
        res = xs[n // 2 - 1]
    print(res)
### BUGGY CODE ###

string = input()
kai = int(input())
data = [input().split(' ') for i in range(kai)]
key = 0  #0 start

for i in range(kai):
    if(data[i][0] == '1'):
        key = (key + 1) % 2
    elif((int(data[i][1]) + key) % 2 == 1):
        string = data[i][2] + string
    else:
        string = string + data[i][2]

if(key == 0):
    print(string)
else:
    print(string[::-1])


### FIXED CODE ###

string = input()
kai = int(input())
data = [input().split(' ') for i in range(kai)]
key = 0  #0 start
former = []
latter = []

for i in range(kai):
    if(data[i][0] == '1'):
        key = (key + 1) % 2
    elif((int(data[i][1]) + key) % 2 == 1):
        former.append(data[i][2])
    else:
        latter.append(data[i][2])

string = ''.join(former[::-1]) + string + ''.join(latter)
if(key == 0):
    print(string)
else:
    print(string[::-1])
### BUGGY CODE ###

s = input()
nq = int(input())

jun = True
for i in range(nq):
  query = input().split()
  if query[0] == '1':
    jun = not jun
    continue
  if jun:
    if query[1] == '1':
      s = query[2] + s
    else:
      s = s + query[2]
  else:
    if query[1] == '1':
      s = s + query[2]
    else:
      s = query[2] + s
if jun:
  print(s)
else:
  print(s[::-1])

### FIXED CODE ###

from collections import deque as dq
s = input()
nq = int(input())

s = dq(s)

jun = True
for i in range(nq):
  query = input().split()
  if query[0] == '1':
    jun = not jun
    continue
  if jun:
    if query[1] == '1':
      s.appendleft(query[2])
    else:
      s.append(query[2])
  else:
    if query[1] == '1':
      s.append(query[2])
    else:
      s.appendleft(query[2])
if jun:
  print(''.join(s))
else:
  print(''.join(list(s)[::-1]))
### BUGGY CODE ###

def main():
    import itertools
    n,k=map(int,input().split())
    xy=[list(map(int,input().split())) for i in range(n)]
    t=[i for i in range(n)]
    s=list(itertools.permutations(t,k))
    #print(s)
    l=len(s)
    inf=10000000000
    x_min=inf
    y_min=inf
    x_max=-inf
    y_max=-inf
    for i in range(n):
        x,y=xy[i]
        if x<x_min:x_min=x
        if y<y_min:y_min=y
        if x>x_max:x_max=x
        if y>y_max:y_max=y
    area=(x_max-x_min)*(y_max-y_min)
    #print(area)
    for i in range(l):
        x_min=inf
        y_min=inf
        x_max=-inf
        y_max=-inf
        for j in range(k):
            x,y=xy[s[i][j]]
            if x<x_min:x_min=x
            if y<y_min:y_min=y
            if x>x_max:x_max=x
            if y>y_max:y_max=y
        #print(area)
        area=min((x_max-x_min)*(y_max-y_min),area)
    print(area)
main()


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
l=[]
r=[]
for i in range(n):
  l.append(i+a[i]+1)
  r.append(i-a[i]+1)
ans=0
for x in l:
  ans=ans+r.count(x)
print(ans)

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
l=[]
r=[]
for i in range(n):
  l.append(i+a[i]+1)
  r.append(i-a[i]+1)
cl=collections.Counter(l)
cr=collections.Counter(r)
ans=0
for k,v in cl.items():
  ans+=v*cr[k]
print(ans)
### BUGGY CODE ###

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

prev = sum(p[1:k])
ind = 0


for i in range(n - k + 1):
    nex = sum(p[i:i + k])

    if prev < nex:
        prev = nex
        ind = i

total = 0
for i in range(ind, ind + k):
    total += (1 + p[i]) * (p[i] / 2) / p[i]

print(total)

### FIXED CODE ###

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

prev = sum(p[1:k])
current = sum(p[1:k])
ind = 0

for i in range(1, n - k + 1):
    current = current - p[i - 1] + p[i + k - 1]

    if prev < current:
        prev = current
        ind = i

total = 0
for i in range(ind, ind + k):
    total += p[i] / 2 + 0.5

print(total)
### BUGGY CODE ###

#"""
import sys
input = sys.stdin.readline
#"""

N=int(input())
A = [list(map(int,input().split())) for _ in [0]*N]

V = {(i,j):0 for i in range(N) for j in range(i+1,N)}
Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
for i,B in enumerate(A):
    a0 = B[0]-1
    k1 = (i,a0) if i<a0 else (a0,i)
    for j in range(N-2):
        a1 = B[j+1]-1
        k0 = k1
        k1 = (i,a1) if i<a1 else (a1,i)
        Ef[k0].append(k1)
        V[k1] += 1

q = [k for k in V if V[k] == 0]
ans = 0
rmv = 0
while q:
    qq = []
    for k in q:
        for k2 in Ef[k]:
            V[k2] -= 1
            rmv += 1
            if V[k2] == 0 : qq.append(k2)
    ans += 1
    q = qq
if rmv != N*(N-2) : ans = -1
print(ans)

### FIXED CODE ###

#"""
import sys
input = sys.stdin.readline
#"""
def main():
    def get_key(i,j):
        if i<j: i,j = j,i
        return i*N+j
    N=int(input())
    A = [list(map(int,input().split())) for _ in [0]*N]
    V = [-1]*(N*N)
    for i in range(N):
        for j in range(i+1,N):
            V[get_key(i,j)] = 0
    Ef = [[] for _ in V]

    for i,B in enumerate(A):
        a0 = B[0]-1
        k1 = (i,a0)
        for a1 in B[1:]:
            a1 -= 1
            k0 = k1
            k1 = (i,a1)
            Ef[get_key(*k0)].append(get_key(*k1))
            V[get_key(*k1)] += 1

    q = [i for i,v in enumerate(V) if v == 0]
    ans = 0
    rmv = 0
    while q:
        qq = []
        for i in q:
            for j in Ef[i]:
                V[j] -= 1
                rmv += 1
                if V[j] == 0 : qq.append(j)
        ans += 1
        q = qq
    if rmv != N*(N-2) : ans = -1
    print(ans)
main()
### BUGGY CODE ###

'''
https://atcoder.jp/contests/abc084/tasks/abc084_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    def prime_decomp(n):
        i = 2
        res = []
        while i ** 2 <= n:
            while n % i==0:
                n //= i
                res.append(i)
            i += 1
        if n > 1:
            res.append(n)
        return res
    
    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        res = 0
        for i in range(l, r+1, 2):
            if len(prime_decomp(i))==1:
                if len(prime_decomp((i+1)//2))==1:
                    res += 1
        print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

'''
https://atcoder.jp/contests/abc084/tasks/abc084_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    def primecheck(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if p[i]:
                for j in range(i * i, n + 1, i):
                    p[j] = False
        return p
    
    p = primecheck(10**5)
    cnt = 0
    res = [0]*(10**5)
    for i in range(10**5):
        if p[i]==p[(i+1)//2]==1:
            cnt += 1
        res[i] = cnt


    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        print(res[r]-res[l-1])

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

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

ans = 0

for i in range(n):
    sums = 0
    for j in range(n - i):
        new_sum = sums + a[i + j]
        if new_sum == 0:
            ans += 1
        sums = new_sum
        
print(ans)

### FIXED CODE ###

from collections import Counter

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

ans = 0

b = [0]
for i in range(n):
	b.append(b[i] + a[i])

c = Counter(b)

for value in c.values():
	ans += value * (value - 1) // 2
    
print(ans)
### BUGGY CODE ###

N=int(input())
alphabet=list('abcdefghijklmnopqrstuvwxyz')
result = []
while N >= 0:
  num, N = N%26, N//26
  result.append(alphabet[num-1])
print(''.join(result)[::-1])

### FIXED CODE ###

N=int(input())
alphabet=list('zabcdefghijklmnopqrstuvwxyz')
result = ''
while N > 0:
  result = alphabet[N%26]+result
  if N%26==0:
    N-=1
  N//=26
print(result)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()

total = 0
flag = 0

for i in range(n):
  if i != n-1:
    if a[i] == a[i + 1]:
      continue
  for j in range(i):
    if i == j:
      continue
    
    if int(a[i]/a[j]) == a[i]/a[j]:
      flag = 1
      break
    
  if flag == 0:
    total += 1
  else:
    flag = 0
    
print(total)

### FIXED CODE ###

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

max_a = max(a)
l = [0] * max_a

for i in range(n):
  j = 1
  while a[i] * j - 1 < max_a:
    l[a[i] * j - 1] += 1
    j += 1

count = 0

for i in range(n):
  if l[a[i] - 1] == 1:
    count += 1

print(count)
### BUGGY CODE ###

from fractions import gcd


MOD = 10**9+7

N = int(input())
A = list(map(int,input().split()))
#%%
def modinv(x,mod):
    return pow(x,mod-2,mod)

B = []
for a in A:
    b = modinv(a,MOD)
    B.append(b)

def lcm(a,b):
    return a//gcd(a,b)*b

ans = 0

cur = 1
for a in A:
    cur =  lcm(cur,a)
for b in B:
    ans += cur*b
    ans %= MOD
print(ans)



### FIXED CODE ###


from fractions import gcd


MOD = 10**9+7

N = int(input())
A = list(map(int,input().split()))
#%%
def modinv(x,mod):
    return pow(x,mod-2,mod)

B = []
for a in A:
    b = modinv(a,MOD)
    B.append(b)

def lcm(a,b):
    return a//gcd(a,b)*b

ans = 0

cur = 1
for a in A:
    cur =  lcm(cur,a)
for b in B:
    ans += cur*b
ans %= MOD
print(ans)
### BUGGY CODE ###

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

am = [[0]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        am[i][j] = a[i]*a[j] % 1000000007

for i in range(n-1):
    if a[i] == 0:
        continue
    for j in range(i+1, n):
        ans += am[i][j]
ans %= 1000000007
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
b = 0
c = 0
for i in range(n):
    b += a[i]
    c += a[i] * a[i]
ans = (b * b - c) // 2
ans %= 1000000007
print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

room_connection = [[] for n in range(N)]

for a, b in zip(A, B):
    room_connection[a - 1].append(b - 1)
    room_connection[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]
visited = []
queue = deque()
queue.append(0)
# pprint(room_connection)

while stack:
    now =queue.popleft()
    # now = stack.pop()
    next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for r in next_room:
        if r not in visited:
            queue.append(r)
            # stack.append(r)

        if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            room_depth[r] = room_depth[now] + 1
            room_sign[r] = now + 1

    visited.append(now)

    if set(visited) == set(range(N)):
        break


    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)

### FIXED CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)
### BUGGY CODE ###

k, s = list(map(int, input().split()))
ct = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                ct += 1
                break;
print(ct)

### FIXED CODE ###

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

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 22:28:26 2020

@author: Kanaru Sato
"""

s = input()
n = len(s)
s = int(s)
dic = {}
mod = 2019
count = 0

for i in range(1,n+1):
    num = (s%(10**(i)))%mod
    if num in dic:
        count += 1
    if num not in dic:
        dic[num] = 1

if 0 in dic:
    count += 1

print(count)

### FIXED CODE ###

s = list(map(int, list(input())))
n = len(s)

countdic = {}
mod = 2019

num = 0
d = 1
for i in range(1,n+1):
    num += s[n-i]*d
    num %= mod
    if num in countdic:
        countdic[num] += 1
    if num not in countdic:
        countdic[num] = 1
    d = (10*d)%mod

ans = 0
for key in countdic:
    ans += countdic[key]*(countdic[key]-1)//2

if 0 in countdic:
    ans += countdic[0]

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

N = int(input())
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x: x[0]+x[1])
#dp[i][j] -> i人目まで見る。j人積むときの、座布団の枚数の最小値
dp = [[float("INF")]*(N+1) for _ in range(N+1)]
ans = 0
for i in range(N+1):
    dp[i][0] = 0
for i in range(1,N+1):
    h,p = HP[i-1]
    for j in range(1,N+1):
        if dp[i-1][j-1]<=h:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
            ans = max(ans,j)
        else:
            dp[i][j] = dp[i-1][j]

print(ans)

### FIXED CODE ###

N = int(input())
men = []
for _ in range(N):
    H,P = map(int,input().split())
    men.append((H,P,H+P))
men.sort(key=lambda x: x[2])

maxH = max(men)[0]
inf = maxH+1
#dp[i][j] -> i人目までみたとき、j人が座布団を積む場合の最小枚数
dp = [[-1]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    h,p,a = men[i-1]
    for j in range(1,N+1):
        if 0 <= dp[i-1][j-1] <= h:
            if dp[i-1][j] == -1:
                dp[i][j] = dp[i-1][j-1]+p
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
        else:
            dp[i][j] = dp[i-1][j]

for j in range(N,-1,-1):
    if dp[-1][j] != -1:
        print(j)
        break
### BUGGY CODE ###

N = int(input())
S = input()
ans = N+1
for i in range(1, N):
    pre = S[0:i-1]
    back = S[i:N]
    #print(pre,back)
    #print(list(pre_and_back))
    ans = min(ans,(pre.count('W') + back.count('E')))

print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = N+1
W_cnt = S.count('W')
left_W_cnt = 0
right_W_cnt = W_cnt
E_cnt = S.count('E')
left_E_cnt = 0
right_E_cnt = E_cnt

for i in range(0, N):
    if S[i] == 'W':
        left_W_cnt += 1
        ans = min(ans,(left_W_cnt-1 + right_E_cnt))
    else:
        right_E_cnt -= 1
        ans = min(ans,(left_W_cnt + right_E_cnt))
    #print(left_W_cnt,right_E_cnt)
print(ans)