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

N,K=map(int,input().split())
A=list(map(int,input().split()))
F=list(map(int,input().split()))
A.sort()
F.sort(reverse=True)

def judge(x):
    res=K
    for n in range(N):
        over=max(A[n]*F[n]-x,0)
        res-=-(-over//F[n])
    return res>=0

def bin_search(left,right):
    if left+1==right:
        return right
    else:
        mid=(left+right)//2
        if judge(mid):
            return bin_search(left,mid)
        else:
            return bin_search(mid,right)
print(bin_search(-1,10**12+1))

### FIXED CODE ###

import numpy as np

N,K=map(int,input().split())
A=list(map(int,input().split()))
F=list(map(int,input().split()))
A.sort()
F.sort(reverse=True)

A=np.array(A)
F=np.array(F)

def judge(x):
    over=np.maximum(A*F-x,0)
    shug=-(-over//F).sum()
    return shug<=K

left=-1
right=10**12*+1
while left+1<right:
    mid=(left+right)//2
    if judge(mid):
        right=mid
    else:
        left=mid
print(right)
### BUGGY CODE ###

from operator import itemgetter

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

A = []
for i in P:
    A.append(1/2*i*(i+1)/i)

ans = 0
for i in range(len(A)):
    ans = max(ans,sum(A[i:i+K]))

print(ans)

### FIXED CODE ###

from itertools import accumulate

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

A = []
for i in P:
    A.append(1/2*(i+1))
    #A.append(1/2*i*(i+1)/i)

ans = 0
'''
for i in range(len(A)):
    ans = max(ans,sum(A[i:i+K]))
'''
    
accum = [0] + list(accumulate(A))
for i in range(len(accum)):
    ans = max(ans,accum[i] - accum[i-K])
print(ans)
### BUGGY CODE ###

MOD=10**9+7
N, M = map(int, input().split())

FCT = [1]
for i in range(1, M+1):
    FCT.append((FCT[-1] * i)%MOD)

def pmu(n, r, mod=MOD):
    return (FCT[n] * pow(FCT[n-r], mod-2, mod)) % mod

def cmb(n, r, mod=MOD):
    return (pmu(n, r) * pow(FCT[r], mod-2, mod)) % mod

def solve():
    # {the num of case B when A=range(1,N+1)} x {permutation of A}
    # use inclusion-exclusion principle against former
    ans = 0
    for i in range(N+1):
        cp = (cmb(N, i) * pmu(M-i, N-i))%MOD
        ans = (ans + (1 if i%2==0 else -1) * cp) % MOD
    return (ans * pmu(M, N)) % MOD

if __name__ == "__main__":
    print(solve())


### FIXED CODE ###

MOD=10**9+7
N, M = map(int, input().split())

FCT = [1]
for i in range(1, M+1):
    FCT.append((FCT[-1] * i)%MOD)

def pmu(n, r, mod=MOD):
    return (FCT[n] * pow(FCT[n-r], mod-2, mod)) % mod

def cmb(n, r, mod=MOD):
    return (pmu(n, r) * pow(FCT[r], mod-2, mod)) % mod

def solve():
    # {the num of case B when A=range(1,N+1)} x {permutation of A}
    # use inclusion-exclusion principle against former
    ans = 0
    for i in range(N+1):
        cp = (cmb(N, i) * pmu(M-i, N-i))%MOD
        ans = (ans + (1 if i%2==0 else -1) * cp) % MOD
    return (ans * pmu(M, N)) % MOD

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

def main():
    inp1=list(map(lambda x:int(x),input().split()))
    cards=list(map(lambda x:int(x),input().split()))
    N=inp1[0]
    M=inp1[1]
    B=[]
    C=[]
    for i in range(M):
        changes=list(map(lambda x:int(x),input().split()))
        B.append(changes[0])
        C.append(changes[1])

    bc_zip=zip(C,B)
    bc_zip=sorted(bc_zip,reverse=True)
    C,B=zip(*bc_zip)

    cards.sort(reverse=True)
    
    for i in range(M):
        for j in range(B[i]):
            cards.append(C[i])

    cards.sort(reverse=True)
    cards=cards[:N]
    print(sum(cards))

if __name__=="__main__":
    main()

### FIXED CODE ###

from heapq import heappush,heappop

def main():
    inp1=list(map(lambda x:int(x),input().split()))
    cards=list(map(lambda x:int(x),input().split()))
    cards_heap=[]
    for i in cards:
        heappush(cards_heap,i)

    N=inp1[0]
    M=inp1[1]
    B=[]
    C=[]
    for i in range(M):
        changes=list(map(lambda x:int(x),input().split()))
        B.append(changes[0])
        C.append(changes[1])

    cb=zip(C,B)
    cb=sorted(cb,reverse=True)


    for C,B in cb:
        for _ in range(B):
            a=heappop(cards_heap)
            if C>a:
                heappush(cards_heap,C)
            else:
                heappush(cards_heap,a)
                break

    print(sum(cards_heap))

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

from collections import deque
H,W = map(int, input().split())
A = [input() for _ in range(H)]

inf = 10**6
d = [[inf]*W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == ".":
            continue
        q = deque()
        q.append((i, j, 0))
        d[i][j] = 0
        while q:
            temp = q.popleft()
            x = temp[0]
            y = temp[1]
            r = temp[2]
            if x > 0 and d[x-1][y] > r+1:
                d[x-1][y] = r+1
                q.append((x-1, y, r+1))
            if y > 0 and d[x][y-1] > r+1:
                d[x][y-1] = r+1
                q.append((x, y-1, r+1))
            if x < H-1 and d[x+1][y] > r+1:
                d[x+1][y] = r+1
                q.append((x+1, y, r+1))
            if y < W-1 and d[x][y+1] > r+1:
                d[x][y+1] = r+1
                q.append((x, y+1, r+1))

ans = 0
for i in range(H):
    ans = max(ans, max(d[i]))
print(ans)

### FIXED CODE ###

from collections import deque

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

d = [[10**6]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            d[i][j] = 0
            q.append((i, j, 0))
            
while q:
    temp = q.popleft()
    y = temp[0]
    x = temp[1]
    r = temp[2]
    if y != 0:
        if d[y-1][x] > r+1 and A[y-1][x] == ".":
            d[y-1][x] = r+1
            q.append((y-1, x, r+1))
    if y != H-1:
        if d[y+1][x] > r+1 and A[y+1][x] == ".":
            d[y+1][x] = r+1
            q.append((y+1, x, r+1))
    if x != 0:
        if d[y][x-1] > r+1 and A[y][x-1] == ".":
            d[y][x-1] = r+1
            q.append((y, x-1, r+1))
    if x != W-1:
        if d[y][x+1] > r+1 and A[y][x+1] == ".":
            d[y][x+1] = r+1
            q.append((y, x+1, r+1))
                        
ans = 0
for i in range(H):
    ans = max(ans, max(d[i]))
    
print(ans)
### BUGGY CODE ###

from collections import Counter
N=int(input())
A=[int(x) for x in input().rstrip().split()]
A_s=list(set(A))
A_count=[]
cnt=0

for x in range(len(A_s)):
  i=A.count(A_s[x])
  A_count.append(i)

  if 2<=i:
    cnt+=(i*(i-1))//2


for i in range(N):
  if A_count[A_s.index(A[i])]==1:
    print(cnt)
  else:
    print(cnt-A_count[A_s.index(A[i])]+1)

### FIXED CODE ###

import collections
N=int(input())
A=[int(x) for x in input().rstrip().split()]
A_c=collections.Counter(A)
cnt=0

for i in A_c.values():
  cnt+=(i*(i-1))//2


for i in A:
  x=A_c[i]
  if x==1:
    print(cnt)
  else:
    print(cnt-x+1)
### BUGGY CODE ###

import bisect
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
ans = 0
for a in range(N):
    for b in range(a+1,N):
        for c in range(a):
            if arr[a] < arr[b] + arr[c] and arr[b] < arr[c] + arr[a] and arr[c] < arr[a] + arr[b]:
                ans += 1
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(N):
    for k in range(i+1,N):
        tmp = bisect.bisect_left(a,a[i]+a[k])
        ans += tmp - k - 1
print(ans)
### BUGGY CODE ###

n = input()
m = []
for i in range(n):
    m.append(input())

interest = [m[1]-m[0]]
for i in range(n):
    for j in range(i+1,n):
        if interest[-1] < m[j]-m[i]:
            interest.append(m[j]-m[i])
print(interest[-1])
 

### FIXED CODE ###

n = int(input())
a = [0 for i in range(n)]
for i in range(n):
    a[i] = int(input())
minimum = a[0]
profit = a[1]-a[0]

for i in range(1,n):
    if profit < a[i]- minimum:
        profit = a[i] - minimum
    if minimum > a[i]:
        minimum = a[i]
        
print(profit)
### BUGGY CODE ###

N, K = map(int, input().split())
P = dict()
C = dict()

for i, p in enumerate(map(int, input().split())):
    P[i+1] = p
for i, c in enumerate(map(int, input().split())):
    C[i+1] = c

ans = -float("inf")
for pos in range(1, N+1):
    i = pos
    score = 0
    for k in range(1, K+1):
        i = P[i]
        score += C[i]
        ans = max(ans, score)
        if i == pos:
            if score > 0:
                lastAns = score * (K//k)
                NumberOfCycle = K%k
                lastScore = lastAns
                j = i
                for _ in range(NumberOfCycle):
                    j = P[j]
                    lastScore += C[j]
                    lastAns = max(lastAns, lastScore)
                ans = max(ans, lastAns)
                break
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
P = dict()
C = dict()

for i, p in enumerate(map(int, input().split())):
    P[i+1] = p
for i, c in enumerate(map(int, input().split())):
    C[i+1] = c

ans = -float("inf")
for pos in range(1, N+1):
    i = pos
    score = 0
    for k in range(1, K+1):
        i = P[i]
        score += C[i]
        ans = max(ans, score)
        if i == pos:
            if score > 0:
                lastAns = score * ((K//k)-1)
                NumberOfCycle = (K%k) + k
                lastScore = lastAns
                j = i
                for _ in range(NumberOfCycle):
                    j = P[j]
                    lastScore += C[j]
                    lastAns = max(lastAns, lastScore)
                ans = max(ans, lastAns)
            break
print(ans)
### BUGGY CODE ###

import numpy as np
s = input()
# s = "RRLLLLRLRRLL"

n = len(s)

pop = [0]*n
for i in range(n):
    if s[i] == "L":
        # iより左でもっとも右のRをみつける
        idx = i-1 - s[:i][::-1].index('R')
#         print(idx)
#         print("amari", (idx - i)%2)
        if (idx - i)%2 == 1:
            pop[idx+1] += 1
        else:
            pop[idx] += 1
    else:
        # iより右でもっとも左のLをみつける
        idx = i+1 + s[i+1:].index('L')
#         print(idx)
#         print((idx - i)%2)
        if (idx - i)%2 == 1:
            pop[idx-1] += 1
        else:
            pop[idx] += 1
print(" ".join(map(str, pop)))   

### FIXED CODE ###

import numpy as np
s = input()
n = len(s)

pop = [0]*n

lastR = 0
for i in range(n):
    if s[i] == "L":
        if (lastR - i)%2 == 1:
            pop[lastR+1] += 1
        else:
            pop[lastR] += 1
    else:
        lastR = i
            
lastL = n
for i in range(n-1, -1, -1):  
    if s[i] == "R":
        if (lastL - i)%2 == 1:
            pop[lastL-1] += 1
        else:
            pop[lastL] += 1
    else:
        lastL = i
        
print(" ".join(map(str, pop)))
### BUGGY CODE ###

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

import numpy as np

N = int(input())

mat = np.zeros(N)
alphabet = "abcdefghijklmnopqrstuvwxyz"

for i in range(N):
    word = input()
    for s in word:
        mat[i] += 2**alphabet.index(s)
# print(mat)
ans = 0
for i in range(N):
    for j in range(i+1, N):
        # print(mat[i])
        # print(mat[j])
        # print("{}, {}".format(i,j))
        # print(mat[i] - mat[j])
        if mat[i] - mat[j] == 0:
            # print(i)
            # print(j)
            # print()
            ans += 1

print(ans)


### FIXED CODE ###

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

N = int(input())

alphabet = "abcdefghijklmnopqrstuvwxyz"

ans_dic = {}

for i in range(N):
    word = input()
    tmp = 0
    for s in word:
        tmp += 10**alphabet.index(s)

    if tmp in ans_dic:
        ans_dic[tmp] += 1
    else:
        ans_dic[tmp] = 1
ans = 0
for k, v in ans_dic.items():
    ans += v * (v-1) // 2
print(ans)
### BUGGY CODE ###

from itertools import product
H, W, N = list(map(int, input().split()))
A = [tuple(map(int, input().split())) for _ in range(N)]
count = {}
for x, y in A:
    for xx, yy in product(range(x-1, x+2), range(y-1, y+2)):
        if not(2 <= xx <= H-1 and 2 <= yy <= W-1):
            continue
        count[(xx, yy)] = count.get((xx, yy), 0) + 1
ans = [0] * 10
for k, v in count.items():
    ans[v] += 1
ans[0] = (H - 2) * (W - 2) - sum(ans)
print(*ans, sep="\n")


### FIXED CODE ###

from itertools import product
H, W, N = list(map(int, input().split()))
A = [tuple(map(int, input().split())) for _ in range(N)]
count = {}
for x, y in A:
    for xx, yy in product(range(x-1, x+2), range(y-1, y+2)):
        if not(2 <= xx <= H-1 and 2 <= yy <= W-1):
            continue
        count[(xx, yy)] = count.get((xx, yy), 0) + 1
ans = [0] * 10
for k, v in count.items():
    ans[v] += 1
ans[0] = (H - 2) * (W - 2) - sum(ans)
print(*ans, sep="\n")
### BUGGY CODE ###

def solve():
  R, C, K = map(int, input().split())
  item = [[0]*C for _ in range(R)]
  for i in range(K):
    r,c,v = map(int, input().split())
    item[r-1][c-1] = v
  dp = [[[0]*5 for _ in range(C+1)] for _ in range(R+1)]
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4): #横から取らない
        dp[i][j][k] = dp[i][j-1][k]
      #上から取らない
      dp[i][j][0] = max(dp[i][j][0],dp[i-1][j][-1])
      if item[i-1][j-1]>0:
        #上からとる
        dp[i][j][1] = max(dp[i][j][1],dp[i-1][j][-1]+item[i-1][j-1])
        for k in range(1,4): #横から取る
          dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1]+item[i-1][j-1])
      dp[i][j][4] = max(dp[i][j][:4])
  ans = max(dp[-1][-1])
  return ans
print(solve())

### FIXED CODE ###

import sys
input = sys.stdin.readline
def solve():
  R, C, K = map(int, input().split())
  item = [[0]*C for _ in range(R)]
  for i in range(K):
    r,c,v = map(int, input().split())
    item[r-1][c-1] = v
  dp = [[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4): #横から取らない
        dp[k][i][j] = dp[k][i][j-1]
      #上から取らない
      dp[0][i][j] = max(dp[0][i][j],dp[-1][i-1][j])
      if item[i-1][j-1]>0:
        #上からとる
        dp[1][i][j] = max(dp[1][i][j],dp[-1][i-1][j]+item[i-1][j-1])
        for k in range(1,4): #横から取る
          dp[k][i][j] = max(dp[k][i][j],dp[k-1][i][j-1]+item[i-1][j-1])
      for k in range(1,4):
        dp[k][i][j] = max(dp[k-1][i][j],dp[k][i][j])
  ans = 0
  for k in range(4):
    ans = max(ans,dp[k][-1][-1])
  return ans
print(solve())
### BUGGY CODE ###

N = int(input())
x = list(int(i) for i in input().split())
for i in range(N):
    a = x.pop(i)
    print(sorted(x)[int(N/2-1)])
    x.insert(i,a)
    

### FIXED CODE ###

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

X = []
for i, a in enumerate(A):
    X.append([a, i])

X.sort()

# Biになり得るのはX[m-1] or X[m] (m=N//2)
m = N//2
itoj = {}
for j in range(N):
    x, i = X[j]
    itoj[i] = j
for i in range(N):
    j = itoj[i]
    if j < m:
        print(X[m][0])
    else:
        print(X[m-1][0])
### BUGGY CODE ###

def warshall_floyd(d):
    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])
    return d
n = int(input())
d = [[float("inf") for i in range(n)] for i in range(n)] 
l=[]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n):
    s=input()
    for j in range(n):
        if s[j]=="1":
            d[i][j] = 1
            l.append([i,j])
for i in range(n):
    d[i][i] = 0
wf=warshall_floyd(d)
visited = [1]+[0 for i in range(n-1)]
while 0 in visited:
    for i in l:
        if visited[i[0]]!=0:
            if visited[i[0]]==1:
                if visited[i[1]]==1:
                    print(-1)
                    exit()
                elif visited[i[1]]==0:
                    visited[i[1]]=-1
            else:
                if visited[i[1]]==-1:
                    print(-1)
                    exit()
                elif visited[i[1]]==0:
                    visited[i[1]]=1
ans=0
for i in wf:
    ans=max(ans,max(i)+1)
print(ans)

### FIXED CODE ###

#warshall_floyd法
def warshall_floyd(d):
    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])
    return d
n = int(input())
d = [[float("inf") for i in range(n)] for i in range(n)] 
l=[]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n):
    s=input()
    for j in range(n):
        if s[j]=="1":
            d[i][j] = 1
            l.append([i,j])
for i in range(n):
    d[i][i] = 0
wf=warshall_floyd(d)
visited = [1]+[0 for i in range(n-1)]
for _ in range(1000):
    for i in l:
        if visited[i[0]]!=0:
            if visited[i[0]]==1:
                if visited[i[1]]==1:
                    print(-1)
                    exit()
                elif visited[i[1]]==0:
                    visited[i[1]]=-1
            else:
                if visited[i[1]]==-1:
                    print(-1)
                    exit()
                elif visited[i[1]]==0:
                    visited[i[1]]=1
ans=0
for i in wf:
    ans=max(ans,max(i)+1)
print(ans)
### BUGGY CODE ###

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

LIM = int(N ** 0.5) * 2 + 1
dp = [[0] * LIM for i in range(K - 1)]

ts = set()
num = {}
for i in range(1, int(N ** 0.5) + 1):
    x = N // i
    y = N // (N // i)
    ts.add(x)
    ts.add(y)
    if x not in num:
        num[x] = 0
    if y not in num:
        num[y] = 0

    # dp[0][idx[(N // ] += (N // i)
ts = sorted(ts, reverse=True)
idx = {k: i for i, k in enumerate(ts)}
for j, t in enumerate(ts):
    num[t] = (N // t - N // ts[j-1]) if j > 0 else 1
    # print(t, num[t])
    dp[0][idx[t]] = num[t] * t


for i in range(1, K - 1):
    pref = 0
    for j in reversed(range(len(ts))):
        R = idx[N // ts[j]]
        pref += dp[i-1][R]
        dp[i][j] = pref * num[ts[j]]
        # pref += dp[i-1][R] * num[ts[j]]

        # print(f"0 - {R}")
        # dp[i][j] = sum(dp[i-1][k] * num[ts[j]] for k in range(R + 1))
        # print(pref, dp[i][j])


# for x in dp:
    # print(x)
ans = sum(dp[-1])
print(ans % 1000000007)


### FIXED CODE ###

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

LIM = int(N ** 0.5) * 2 + 1
dp = [[0] * LIM for i in range(K - 1)]

ts = set()
tsl = []
tsr = []
num = {}
for i in range(1, int(N ** 0.5) + 1):
    x = N // i
    y = N // (N // i)
    if not tsl or tsl[-1] > x:
        tsl.append(x)
    if x != y and (not tsr or tsr[-1] < y):
        tsr.append(y)
    if x not in num:
        num[x] = 0
    if y not in num:
        num[y] = 0
ts = tsl + tsr[::-1]

idx = {k: i for i, k in enumerate(ts)}
for j, t in enumerate(ts):
    num[t] = (N // t - N // ts[j-1]) if j > 0 else 1
    # print(t, num[t])
    dp[0][idx[t]] = num[t] * t


MOD = 1000000007
for i in range(1, K - 1):
    pref = 0
    for j in reversed(range(len(ts))):
        # R = idx[N // ts[j]]
        R = len(ts) - j - 1
        pref += dp[i-1][R]
        dp[i][j] = pref * num[ts[j]] % MOD
        # pref += dp[i-1][R] * num[ts[j]]

        # print(f"0 - {R}")
        # dp[i][j] = sum(dp[i-1][k] * num[ts[j]] for k in range(R + 1))
        # print(pref, dp[i][j])


# for x in dp:
    # print(x)
ans = sum(dp[-1])
print(ans % 1000000007)
### BUGGY CODE ###

r,g,b,n = map(int, input().split())
ans = 0
for i in range((n+1)//r+1):
    for j in range((n+1)//g+1):
        k = n - (i*r + j*g)
        if k < 0:
            break
        elif k >= 0 and k%b == 0:
            ans += 1
print(ans)


### FIXED CODE ###

r,g,b,n = map(int, input().split())
ans = 0
for i in range(n+1):
    for j in range(n+1):
        k = n - (i*r + j*g)
        if k < 0:
            break
        elif k >= 0 and k%b == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
 
if k==1 :
  ln=0
elif k==0 :
  ln=n
else:
  while 1:
    ln = n
    n = abs(n-k)
    if ln<=n:
      break
print(ln)

### FIXED CODE ###

n,k = map(int,input().split())
 
if k==1 :
  ln=0
elif k==0 :
  ln=n
elif n>=k:
  a = n%k
  n=a
  while 1:
    ln = n
    n = abs(a-k)
    if ln<=n:
      break
else:
  while 1:
    ln = n
    n = abs(n-k)
    if ln<=n:
      break
print(ln)
### BUGGY CODE ###

if __name__ == '__main__':
    a, b,x = map(int, input().split())
    y = [i for i in range(a,b+1)]
    set1=set(y[:x])
    set2=set(y[len(y)-x:])
    sumSet = set1 | set2
    list = list(sumSet)
    list.sort()

    for i in list:
        print(i)


### FIXED CODE ###

if __name__ == '__main__':
    a, b,x = map(int, input().split())
    set1=set([i for i in range(a,min(a+x,b))])
    set2=set([i for i in range(max(a,b-x+1),b+1)])
    sumSet = set1 | set2
    list = list(sumSet)
    list.sort()

    for i in list:
        print(i)
### BUGGY CODE ###

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
      
uf = UnionFind(n+1)
for i in range(m):
  uf.union(ab[i][0], ab[i][1])
ans=0
for i in range(uf.group_count()):
  if ans < len(uf.members(i)):
    ans = len(uf.members(i))
print(ans)


### FIXED CODE ###

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
      
uf = UnionFind(n+1)
for i in range(m):
  if uf.same(ab[i][0], ab[i][1]) == False:
    uf.union(ab[i][0], ab[i][1])
ans=0
for i in range(1,n+1):
  if ans <uf.size(i):
    ans=uf.size(i)
print(ans)
### BUGGY CODE ###

N = int(raw_input())
S = str(raw_input())
opt_cnt = N
for i in range(N):
    first = S[:i]
    second = S[i+1:]
    cnt = 0
    for f in first:
        if f is not 'E':
            cnt = cnt + 1
        if cnt >= opt_cnt:
            break
    for s in second:
        if s is not 'W':
            cnt = cnt + 1
        if cnt >= opt_cnt:
            break
    if opt_cnt > cnt:
        opt_cnt = cnt
print(opt_cnt)


### FIXED CODE ###

def opt(N, S):
    if N == 1:
        return 0
    else:
        split = int(N/2)
        return min(opt(split,S[:split])+S[split:].count('E'),S[:split].count('W')+opt(N - split,S[split:]))

Num = int(raw_input())
Str = str(raw_input())
print(opt(Num, Str))