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

N, W = map(int, input().split())
w = [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

for i in range(N):
    for j in range(W + 1):
        if j - w[i][0] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i][0]] + w[i][1])

        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
w = [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

for i in range(N):
    for j in range(W + 1):
        if j - w[i][0] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i][0]] + w[i][1])

        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

print(dp[N][W])
### BUGGY CODE ###

def main():
    n = int(input())
    x = list(map(int, input().split()))


    for i in range(0, n):
        sort_list = x[:]
        sort_list.pop(i)
        sort_list.sort()
        print(sort_list[n//2-1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    x = list(map(int, input().split()))

    sort_list = x[:]
    sort_list.sort()

    for i in range(0, n):
        if x[i] < sort_list[n//2]:
            print(sort_list[n//2])
        else:
            print(sort_list[n//2 - 1])

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

n=int(input())
s=input()
a=[]
for i in range(n-2):
  p=s[i]
  #q
  for j in range(i+1,n-1):
    r=p
    r+=s[j]
    for k in range(j+1,n):
      t=r
      t+=s[k]
      a.append(t)
#print(a)
a=list(set(a))
#print(a)
print(len(a))

### FIXED CODE ###

n=int(input())
s=input()
list=["" for _ in range(1000)]
ans=0
for i in range(1000):
  t=str(i)
  u="0"*(3-len(t))+t
  j=0
  exi=0
  p=u[0]
  for x in s:
    if x==p:
      j+=1
      if j==3:
        ans+=1
        break
      p=u[j]
    

  









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

import numpy as np
from numba import njit

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
a = np.array(A, dtype=int)


fin = [N] * N

def calc_b(a):
    b = np.zeros(N, dtype=np.int64)
    for i, _a in enumerate(a):
        l = max(0, i - _a)
        r = min(N - 1, i + _a)

        # imos hou
        b[l] += 1
        if r + 1 < N:
            b[r + 1] -= 1

    b = np.cumsum(b)
    # print('b_sum', b)
    return b


for k in range(min(K,100)):
    # print('a', a)
    a = calc_b(a)
    if all(a == fin):
        break

a = [str(_) for _ in a]
print(' '.join(a))
# print('step=', k)

### FIXED CODE ###

import numpy as np
from numba import njit

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
a = np.array(A, dtype=int)


fin = [N] * N

@njit(cache=True)
def calc_b(a):
    b = np.zeros(N, dtype=np.int64)
    for i, _a in enumerate(a):
        l = max(0, i - _a)
        r = min(N - 1, i + _a)

        # imos hou
        b[l] += 1
        if r + 1 < N:
            b[r + 1] -= 1

    b = np.cumsum(b)
    # print('b_sum', b)
    return b


for k in range(min(K,100)):
    # print('a', a)
    a = calc_b(a)
    # if all(a == fin):
    #     break

a = [str(_) for _ in a]
print(' '.join(a))
# print('step=', k)
### BUGGY CODE ###

import bisect
N,M,Q=map(int,input().split())
LR = []
for _ in range(M):
    LR.append(list(map(int,input().split())))
LR.sort()
L = [x for x,_ in LR]
R = [x for _,x in LR]

#事前に配列化 ans[i][j] i以降にスタート、j以前に完了の個数
ans = [[0]*510 for _ in range(510)]
for i in range(1,501):
    idx_L = bisect.bisect_left(L,i)
    arr=R[idx_L:]
    for ar in arr:
        ans[i][ar]+=1
    for j in range(1,501):
        ans[i][j]=ans[i][j-1]+ans[i][j]
    
for _ in range(Q):
    l,r = map(int,input().split())
    print(ans[l][r])


### FIXED CODE ###

import bisect
N,M,Q=map(int,input().split())
LR = []
for _ in range(M):
    LR.append(list(map(int,input().split())))
LR.sort()
L = [x for x,_ in LR]
R = [x for _,x in LR]

#事前に配列化 ans[i][j] i以降にスタート、j以前に完了の個数
ans = [[0]*510 for _ in range(510)]
for i in range(1,501):
    idx_L = bisect.bisect_left(L,i)
    arr=R[idx_L:]
    for ar in arr:
        ans[i][ar]+=1
    for j in range(1,501):
        ans[i][j]=ans[i][j-1]+ans[i][j]
    
for _ in range(Q):
    l,r = map(int,input().split())
    print(ans[l][r])
### BUGGY CODE ###

n = input()
elem = list(map(int, input().split()))
elem.sort()
ans = 0
while len(elem) > 0:
    elem.pop(0)
    ans = ans + elem.pop(-2)
    elem.pop(-1)
print(ans)

### FIXED CODE ###

n = int(input())
elem = list(map(int, input().split()))
elem.sort()
ans = sum(elem[n::2])
print(ans)
### BUGGY CODE ###

def solve():
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j] = min(d[i][j],d[i][k] + d[k][j])

n,m = map(int,raw_input().split())
d = [[1e10]*n for i in range(n)]
for i in range(m):
	a,b,c = map(int,raw_input().split())
	d[a][b] = -c
solve()
print abs(d[0][n-1])

### FIXED CODE ###

inf = 1e9
n,m = map(int,raw_input().split())
edge = [map(int,raw_input().split()) for i in range(m)]
d = [inf]*n
d[0] = 0
while 1:
	update = 0
	for i in range(m):
		a,b,c = edge[i]
		if d[a] != inf and d[b] > d[a] - c:
			d[b] = d[a] - c
			update = 1
	if update == 0: break
print abs(d[n-1])
### BUGGY CODE ###

H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))
#print(hsummation)
ans = float('inf')
anskouho = 0
h = -1
for j in range(2**(H-1)):
  h += 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  hlist=[]
  for k in range(H-1):
    if binh[-k-1] == '1':
      hlist.append(k)
  hlist.append(-1)
  #print(hlist)
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      for l in range(len(hlist)):
        if l == 0:
          counter[l] += hsummation[now][int(hlist[l])]
          continue
        else:
          counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
      if max(counter) > K:
        anskouho += 1
        break
      else:
        now += 1
    if anskouho > ans:
      break
  else:
    ans = min(ans, anskouho)

      #print(counter)
#print(anskouho)
print(ans)

### FIXED CODE ###

H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))
#print(hsummation)
ans = float('inf')
anskouho = 0
h = 2**(H-1)
for j in range(2**(H-1)):
  h -= 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  hlist=[]
  for k in range(H-1):
    if binh[-k-1] == '1':
      hlist.append(k)
  hlist.append(-1)
  #print(hlist)
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      for l in range(len(hlist)):
        if l == 0:
          counter[l] += hsummation[now][int(hlist[l])]
          continue
        else:
          counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
      if max(counter) > K:
        anskouho += 1
        break
      else:
        now += 1
    if anskouho > ans:
      break
  else:
    ans = min(ans, anskouho)
 
      #print(counter)
#print(anskouho)
print(ans)
### BUGGY CODE ###

from bisect import bisect

n, m = map(int, input().split())
*a, = map(int, input().split())
a.sort()
BC = []
num = 0
for _ in range(m):
    b, c = map(int, input().split())
    BC.append((b, c))
BC = sorted(BC, key=lambda x: x[1], reverse=True)
for b, c in BC:
    idx = bisect(a, c)
    p = min(idx, b)
    for i in range(p):
        a.pop(0)
        a.append(c)
print(sum(a[num:]))


### FIXED CODE ###

n, m = map(int, input().split())
a = [(1, int(i)) for i in input().split()]
for _ in range(m):
    b, c = map(int, input().split())
    a.append((b, c))
a = sorted(a, key=lambda x: x[1])
ans = 0
t = 0
while t < n:
    b, c = a.pop()
    p = min(b, n-t)
    ans += p * c
    t += p
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
dp = [False] * (K + 1)
for i in range(1, K + 1):
    for j in range(N):
        if i - a[j] >= 0:
            dp[i] |= not dp[i - a[j]]

if dp[K]:
    print('First')
else:
    print('Second')

### FIXED CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
dp = [False] * (K + 1)
for i in range(1, K + 1):
    for j in range(N):
        if i - a[j] >= 0:
            dp[i] |= not dp[i - a[j]]

if dp[K]:
    print('First')
else:
    print('Second')
### BUGGY CODE ###

K, S = map(int, input().split())
print(sum(X + Y + Z == S for X in range(K + 1) for Y in range(K + 1) for Z in range(K + 1)))

### FIXED CODE ###

K, S = map(int, input().split())
print(sum(S - K <= X + Y <= S for X in range(K + 1) for Y in range(K + 1)))
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
count = 0
minnum = 0
num = 1
while num <= max(P):
        minnum = P.index(min(P))
        del P[minnum+1:]
        count = count + 1
        num = minnum
print(count) 

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
count = 0
minP = P[0]
for i in range(N):
    if P[i] <= minP:
        count += 1
        minP = P[i] 

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

n = int(input())
a_inputs = [int(i) for i in input().split()]

ai_li = [a_inputs[i]+(i+1) for i in range(n)]
aj_li = [(j+1)-a_inputs[j] for j in range(n)]

ans=0
for a in ai_li:
    if a in aj_li:
        ans+=aj_li.count(a)
print(ans)

### FIXED CODE ###

n = int(input())
a_inputs = [int(i) for i in input().split()]

dic_l={}
dic_r={}
for i in range(n):
    a = a_inputs[i]+(i+1)
    b = (i+1)-a_inputs[i]
    dic_l[a]=dic_l.get(a,0)+1
    dic_r[b]=dic_r.get(b,0)+1

ans=0
for key in dic_l.keys():
    ans+=dic_l[key]*dic_r.get(key,0)
    
print(ans)
### BUGGY CODE ###

import collections
N=int(input())
S = [input() for i in range(N)]
A=[]

P=collections.Counter(S)

A = [k for k, v in P.items() if v == max(P.values())]

A0=set(A)
A1=list(A0)
A1.sort()

for List in A1:
    print(List)

### FIXED CODE ###

import collections
N=int(input())
S = [input() for i in range(N)]
A=[]

P=collections.Counter(S)

y=max(P.values())
A = [k for k, v in P.items() if v == y]

A.sort()

for List in A:
    print(List)
### BUGGY CODE ###

import sys
from bisect import bisect_right
input = sys.stdin.readline

N, C, K = map(int, input().split())
T = [int(input()) for i in range(N)]
T.sort()
answer = 0

while T:
    n = min(C, bisect_right(T, T[0] + K))
    T = T[n:]
    answer += 1

print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, C, K = map(int, input().split())
T = [int(input()) for i in range(N)]
T.sort()
answer = 1
limit = T[0] + K
n = 0

for i in T:
    if i <= limit and n < C:
        n += 1
    else:
        answer += 1
        n = 1
        limit = i + K

print(answer)
### BUGGY CODE ###

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

calRes = 0
calIndex = 0
expectedList = []

for i in range(N):
    cal = list(range(1, p[i] + 1))
    expectedList.append(sum(cal) * (1 / len(cal)))

for o in range(N - (K - 1)):
    calTemp = sum(expectedList[o:o + K])
    if calRes < calTemp:
       calRes = calTemp
       calIndex = o

expectedCorrect = sum(expectedList[calIndex : calIndex + K])

print(expectedCorrect)

### FIXED CODE ###

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

expectedList = [(1 + s) /  2 for s in p]
cumsum = sum(expectedList[:K])
confirm_cumsum = cumsum

for i in range(K, N):
    cumsum += expectedList[i]
    cumsum -= expectedList[i - K]
    if cumsum > confirm_cumsum:
        confirm_cumsum = cumsum

print(confirm_cumsum)
### BUGGY CODE ###

H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(Magic[i][0]-1):
            DP[i][j] = DP[i-1][j]
        DP[i][Magic[i][0]] = min(DP[i-1][Magic[i][0]],Magic[i][1])
        for j in range(Magic[i][0]+1,(MAX_A+1)):
            DP[i][j]=min(DP[i-1][j],DP[i-1][j-Magic[i][0]]+Magic[i][1],DP[i][j-Magic[i][0]]+Magic[i][1])
            if j % Magic[i][0] == 0:
                DP[i][j]=min(DP[i][j],((j//Magic[i][0]) * Magic[i][1]))
print(min(DP[N-1][H:MAX_A]))

### FIXED CODE ###

H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(Magic[i][0]-1):
            DP[i][j] = DP[i-1][j]
        DP[i][Magic[i][0]] = min(DP[i-1][Magic[i][0]],Magic[i][1])
        for j in range(Magic[i][0]+1,(MAX_A+1)):
            DP[i][j]=min(DP[i-1][j],DP[i-1][j-Magic[i][0]]+Magic[i][1],DP[i][j-Magic[i][0]]+Magic[i][1])
            if j % Magic[i][0] == 0:
                DP[i][j]=min(DP[i][j],((j//Magic[i][0]) * Magic[i][1]))
print(min(DP[N-1][H:MAX_A]))
### BUGGY CODE ###

a,aa=map(int,input().split())
b=list(map(int,input().split()))
c=[0 for i in range(a)]
for i in range(1,a):
  for j in range(1,aa+1):
    if i-j<0:
      break
    elif j==1:
      c[i]=c[i-j]+abs(b[i]-b[i-j])
    else:
      c[i]=min(c[i-j]+abs(b[i]-b[i-j]),c[i])
  
print(c[-1])

### FIXED CODE ###

def solve():
  a,aa=map(int,input().split())
  b=list(map(int,input().split()))
  c=[0]*a
  c[0]=0
  for i in range(1,a):
    c[i] = min(c[j] + abs(b[i] - b[j]) for j in range(max(0,i-aa),i))
  print(c[-1])
  
solve()
### BUGGY CODE ###

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

paths = set()
for _ in range(M):
    a, b = map(int, input().split())
    paths.add((a-1, b-1))

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    kick_list = []
    next_key_rooms = []
    for key_room in key_rooms[-1]:
        for path in paths:
            if key_room in path:
                else_room = path[0]
                if else_room == key_room:
                    else_room = path[1]
                kick_list.append(path)
                if rooms[else_room] == -1:
                    rooms[else_room] = step
                    next_key_rooms.append(else_room)
                    marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)
    for kick in kick_list:
        if kick in paths:
            paths.remove(kick)

flag = True
for room in rooms[1:]:
    if room == -1:
        flag = False
        print('No')
        break

if flag:
    print('Yes')
    for i in marks:
        print(i+1)


### FIXED CODE ###

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

paths = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    paths[a].add(b)
    paths[b].add(a)

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    next_key_rooms = set()
    for key_room in key_rooms[-1]:
        for else_room in paths[key_room]:
            if rooms[else_room] == -1:
                rooms[else_room] = step
                next_key_rooms.add(else_room)
                marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)

print('Yes')
for i in marks:
    print(i+1)
### BUGGY CODE ###

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

def search(n):
    if n == 0:
        return False
    for i in range(N):
        for j in range(i+n, N):
            if j+n <= N:
                if S[i:i+n] == S[j:j+n]:
                    return True
    return False

l = 1
r = N//2+1

while l<r:
    mid = (l+r)//2
    if search(mid):
        l = mid+1
    else:
        r = mid

print(l-1)


### FIXED CODE ###

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

maxL = 0

for i in range(1, N-1):
    cnt = 0
    left = 0
    for j in range(0, N-i):
        if S[j]==S[j+i]:
            cnt+=1
            if maxL < cnt:
                maxL = cnt
            if cnt == i:
                break
        else:
            cnt = 0
            left = j + 1

print(maxL)
### BUGGY CODE ###

from sys import stdin
data = stdin.readlines()

a = int(data[0])
b = [int(s) for s in data[1].split()]

i = 0
ans = 1
while i <= a-1:
    ans = ans * b[i]
    i += 1
if ans > 10 ** 18:
    ans = -1

print(ans)

### FIXED CODE ###

from sys import stdin
data = stdin.readlines()

a = int(data[0])
b = [int(s) for s in data[1].split()]

if 0 in b:
    print(0)
else:
    ans = 1
    for i in range(0,a):
        ans = ans * b[i]
        if ans > 10**18:
            print(-1)
            break
        else:
            continue
    else:
        print(ans)
### BUGGY CODE ###

from collections import deque

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

es_lang = [[] for _ in range(M+1)] # 各言語の番号がidxで、それを話せる人が中身
es_p = [[] for _ in range(N+1)] # 各人の番号がidxで、その人の話せる言語が中身
for i in range(N):
    KL = list(map(int, input().split()))
    es_p[i+1].extend(KL[1:])
    for j in KL[1:]:
        es_lang[j].append(i+1)

checked_lang = [False] * (M+1)
checked_p = [False] * (N+1)

#人１からスタートする
stack_p = deque([1])
checked_p[1] = True
while stack_p:
    p = stack_p.pop() # 調べる人を取り出す
    #checked_p[p] = True
    stack_lang = []
    for lang in es_p[p]: #人ｐが話せる言語について調べる
        if checked_lang[lang] == False: # まだその言語を調査してないとき
            stack_lang.append(lang)
            checked_lang[lang] = True
    #print(p, "lll", stack_lang)
    # 人pの持つ言語をだれが話せるか調べる
    new_stack_p = []
    for lang in stack_lang:
        for pp in es_lang[lang]:
            if checked_p[pp] == False:
                new_stack_p.append(pp)
                checked_p[pp] = True
    #print("--", checked_p, checked_lang)
    #print("^^^", new_stack_p)
    if all(checked_p[1:]):
        print("YES")
        """
        print(checked_p)
        print(checked_lang)
        print(es_p)
        """
        exit()
    for i in new_stack_p:
        stack_p.append(i)

print("NO")
"""
print(checked_p)
print(checked_lang)
print(es_p)
"""

### FIXED CODE ###

from collections import deque

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

es_lang = [[] for _ in range(M+1)] # 各言語の番号がidxで、それを話せる人が中身
es_p = [[] for _ in range(N+1)] # 各人の番号がidxで、その人の話せる言語が中身
for i in range(N):
    KL = list(map(int, input().split()))
    es_p[i+1].extend(KL[1:])
    for j in KL[1:]:
        es_lang[j].append(i+1)

checked_lang = [False] * (M+1)
checked_p = [False] * (N+1)

#人１からスタートする
stack_p = [1]
checked_p[1] = True
while len(stack_p) > 0:
    new_stack_p = [] # この次のループで調べる人の集合
    for p in stack_p:
        checked_p[p] = True
        stack_lang = []
        for lang in es_p[p]: #人ｐが話せる言語について調べる
            if checked_lang[lang] == False: # まだその言語を調査してないとき
                stack_lang.append(lang)
                checked_lang[lang] = True

        # 人pの持つ言語をだれが話せるか調べる
        for lang in stack_lang:
            for pp in es_lang[lang]: # 人ｐの話せる言語を話せる人について調べる
                if checked_p[pp] == False: # まだその人を調べてないなら次のループで調べる人に入れる
                    new_stack_p.append(pp)
                    checked_p[pp] = True

    if all(checked_p[1:]):
        print("YES")
        exit()
    if len(new_stack_p) > 0:
        stack_p = new_stack_p
    else:
        break



print("NO")
### BUGGY CODE ###

from collections import deque
import copy
def solve(maze, start):
  memo = deque()
  q = deque()
  q.append([start,0])
  ans = 0
  while q:
    cur, cnt = q.popleft()
    ans = max(ans, cnt)
    memo.append(cur)
    for y, x in zip((0,0,1,-1),(1,-1,0,0)):
      if maze[cur[0]+y][cur[1]+x] == "." and not [cur[0]+y,cur[1]+x] in memo:
        q.append([[cur[0]+y,cur[1]+x],cnt+1])
  return ans


H, W = map(int, input().split())
Maze = [["#"]*(W+2)]+[["#"]+list(input())+["#"] for _ in range(H)] + [["#"]*(W+2)]
Ans = 0
for sy in range(1, H+1):
  for sx in range(1, W+1):
    if Maze[sy][sx] == "#":
      continue
    else:
      Ans = max(Ans, solve(Maze, [sy, sx]))
print(Ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]


def f(i, j):
    t = [[-1] * W for _ in range(H)]
    t[i][j] = 0
    q = [(i, j)]
    while q:
        y, x = q.pop(0)
        if y - 1 >= 0 and S[y - 1][x] != '#' and t[y - 1][x] == -1:
            t[y - 1][x] = t[y][x] + 1
            q.append((y - 1, x))
        if y + 1 < H and S[y + 1][x] != '#' and t[y + 1][x] == -1:
            t[y + 1][x] = t[y][x] + 1
            q.append((y + 1, x))
        if x - 1 >= 0 and S[y][x - 1] != '#' and t[y][x - 1] == -1:
            t[y][x - 1] = t[y][x] + 1
            q.append((y, x - 1))
        if x + 1 < W and S[y][x + 1] != '#' and t[y][x + 1] == -1:
            t[y][x + 1] = t[y][x] + 1
            q.append((y, x + 1))
    return max(max(tt) for tt in t)


result = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            result = max(result, f(i, j))
print(result)
### BUGGY CODE ###

def main():
    k = int(input())
    a = 7
    c = 1
    b = 7
    if k == 2 or k == 5:
        print(-1)
        exit()
    while True:
        if a%k== 0:
            print(c)
            break
        else:
            b = (b*10)%k
            a = b+a
            a = a %k
            c += 1

main()

### FIXED CODE ###

def main():
    k = int(input())
    a = 7
    c = 1
    b = 7
    if k == 2 or k == 5:
        print(-1)
        exit()
    while True:
        if a%k== 0:
            print(c)
            break
        else:
            b = (b*10)%k
            a = b+a
            a = a %k
            c += 1
            if c > k:
                print(-1)
                exit()

main()
### BUGGY CODE ###

# coding: utf-8
# Your code here!
# -*- coding:utf-8 -*-

if __name__ == "__main__":
    N = int(input())
    S = input()
    dp = [[0 for i in range(N+1)] for j in range(N+1)]
    # dp[left][right] := 正しい方向の数
    # まずはdp[0][N]を考える
    for s in S:
        if s == "W":
            dp[0][N] += 1
    maxv = dp[0][N]
    # dpを埋める
    # dp[1][N-1], dp[2][N-2], ...
    for i in range(1, N+1):
        if S[i-1] == "E":
            diff = 1
        else:
            diff = -1
        dp[i][N-i] = dp[i-1][N-i+1] + diff
        if dp[i][N-i] >= maxv:
            maxv = dp[i][N-i]
    print(N - maxv)



### FIXED CODE ###

# -*- coding:utf-8 -*-

def solve(N, S):
    dp = [[0 for i in range(N+1)] for j in range(N+1)]
    # dp[left][right] := 正しい方向の数
    # まずはdp[0][N]を考える
    for s in S:
        if s == "W":
            dp[0][N] += 1
    maxv = dp[0][N]
    # dpを埋める
    # dp[1][N-1], dp[2][N-2], ...
    for i in range(1, N+1):
        if S[i-1] == "E":
            diff = 1
        else:
            diff = -1
        dp[i][N-i] = dp[i-1][N-i+1] + diff
        if dp[i][N-i] >= maxv:
            maxv = dp[i][N-i]
    print(N - maxv)

def solve2(N, S):
    good = 0
    for s in S:
        if s == "W":
            good += 1
    maxv = good

    nowv = maxv
    for i in range(1, N+1):
        if S[i-1] == "E":
            diff = 1
        else:
            diff = -1
        nowv = nowv + diff
        if nowv >= maxv:
            maxv = nowv
    print(N - maxv)

if __name__ == "__main__":
    N = int(input())
    S = input()
    solve2(N, S)