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

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    jobs = {}
    for _ in range(N):
        A, B = map(int, input().split())
        if A in jobs.keys():
            jobs[A] = jobs[A] + [B]
        else:
            jobs[A] = [B]

    profit = 0
    days = jobs.keys()
    potential_jobs = []

    # M-1日後から今日まで遡る
    for elappsed_day in range(1, M+1):
        if elappsed_day in days:
            potential_jobs += jobs[elappsed_day]
        if len(potential_jobs) > 0:
            profit += potential_jobs.pop(potential_jobs.index(max(potential_jobs)))
            
    print(profit)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    jobs = {}
    for _ in range(N):
        A, B = map(int, input().split())
        if A > M:
            continue
        if A in jobs.keys():
            jobs[A] += [-B]
        else:
            jobs[A] = [-B]

    profit = 0
    days = jobs.keys()
    potential_jobs = []
    
    # M-1日後から今日まで遡る
    for elappsed_day in range(1, M+1):
        if elappsed_day in days:
            for job in jobs[elappsed_day]:
                heappush(potential_jobs, job)
        if len(potential_jobs) > 0:
            profit += heappop(potential_jobs)
            
    print(-profit)

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

import sys
sys.setrecursionlimit(10000)

def rec(i, j):
    flag = False
    flag_ = False
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - i)
    if tmp > dp[i+1][j]:
        dp[i+1][j] = tmp
        flag = True
    tmp_ = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - N + j + 1)
    if tmp_ > dp[i][j+1]:
        dp[i][j+1] = tmp_ if tmp_ > dp[i][j+1] else dp[i][j+1]
        flag_ = True
    if i + j == N - 1:
        return
    if flag:
        rec(i + 1, j)
    if flag_:
        rec(i, j + 1)
    
N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]

dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
rec(0, 0)
ans = -1
for i in range(N):
    for j in range(N):
        if dp[i][j] > ans:
            ans = dp[i][j]
print(ans)

### FIXED CODE ###

from collections import deque

N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]
d = deque([(0,0)])
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
while(len(d)>0):
    i, j = d.pop()
    if i + j > N - 1:
        continue
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - i)
    if tmp > dp[i+1][j]:
        if dp[i+1][j] == 0:
            d.appendleft((i+1,j))
        dp[i+1][j] = tmp
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - N + j + 1)
    if tmp > dp[i][j+1]:
        if dp[i][j+1] == 0:
            d.appendleft((i,j+1))
        dp[i][j+1] = tmp
        
ans = -1
for i in range(N):
    for j in range(N):
        if dp[i][j] > ans:
            ans = dp[i][j]
print(ans)
### BUGGY CODE ###

import sys
import itertools
N = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))
for k in range(0, len(A)):
    B = [a for i,a in enumerate(A) if k != i]
    count = 0
    for i in itertools.combinations(B, 2):
        if i[0] == i[1]:
            count += 1
    print(count)


### FIXED CODE ###

import sys
from collections import Counter

def choose(k, r):
    return k*(k-1) // r*(r-1)

N = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))

C = Counter(A)

ANS = sum([choose(v, 2) for v in C.values()])

for k in A:
    v = C[k]
    print(ANS
          - choose(v, 2)
          + choose(v-1, 2)
         )
### BUGGY CODE ###

S = str(input())


count = 0
for i in range(len(S)):
    for j in range(i+4, len(S)+1):
        if(int(S[i:j]) % 2019 == 0):
            count += 1

print(count)

### FIXED CODE ###

from collections import Counter

S = str(input())

memo = [0]
d = 0
mod = 2019


for s in S[::-1]:
    tmp = int(s) * pow(10, d, mod) % mod
    tmp = memo[-1] + tmp
    memo.append(tmp%mod)
    d += 1

c = Counter(memo)
ans = sum(v * (v-1)/2 for v in c.values())
print(int(ans))
### BUGGY CODE ###

N = map(int, input().split())
l = list(map(int, input().split()))
from collections import deque


l = deque(l)

count=0
for i in range(len(l)-1):
    while l[i] >l[i+1]:
        l[i+1]+=1
        count+=1
print(count)

### FIXED CODE ###

N = map(int, input().split())
l = list(map(int, input().split()))
from collections import deque


l = deque(l)

count=0
for i in range(len(l)-1):
    if l[i] >l[i+1]:
        c=l[i] -l[i+1]
        l[i+1]+=c
        count+=c

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

import fractions
from functools import reduce

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

p = 10**9+7

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

lcm = lcm(*A)

B = [lcm//i for i in A]

print(sum(B)%p)

### FIXED CODE ###

import fractions
from functools import reduce

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

p = 10**9+7

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

lcm = lcm_list(A)

B = [lcm//i for i in A]

print(sum(B)%p)
### BUGGY CODE ###

#!/usr/bin/python3
n = int(input())
inf = 100 * 100000

M = [[inf for i in range(n)] for j in range(n)]

for i in range(n):
    L = list(map(int, input().split()))
    u = L[0]
    k = L[1]
    v = L[2::2]
    c = L[3::2]
    for j in range(k):
        M[u][v[j]] = c[j]

S = set()
V = set(range(n))
S.add(0)
d = [inf for i in range(n)]
d[0] = 0
count = 0
while len(V - S) != 0:
    T = V - S
    nd = [inf for i in range(n)]
    for s in S:
        for m, c in enumerate(M[s]):
            if d[s] + c < nd[m] and m in T:
                nd[m] = d[s] + c

    min_nd = min(nd)
    u = nd.index(min_nd)
    S.add(u)
    d[u] = min_nd


for i, v in enumerate(d):
    print(i, v)

### FIXED CODE ###

#!/usr/bin/python3
from heapq import heappop, heappush
n = int(input())
inf = 100 * 100000

M = [[] for i in range(n)]

for i in range(n):
    L = list(map(int, input().split()))
    u = L[0]
    k = L[1]
    v = L[2::2]
    c = L[3::2]
    for j in range(k):
        M[u].append((v[j], c[j]))
result = [0] * n
S = set()
V = set(range(n))
S.add(0)
d = []
for m in M[0]:
    heappush(d, (m[1], m[0]))
T = V - S

while len(T) != 0:
    c, v = heappop(d)
    while v in S:
        c, v = heappop(d)
    result[v] = c
    S.add(v)
    T.remove(v)
    for m in M[v]:
        if m[0] in T:
            heappush(d, (result[v] + m[1], m[0]))

for i, v in enumerate(result):
    print(i, v)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
price = [0] * m
can_opens = [0] * m
for i in range(m):
    a,b = list(map(int,input().split()))
    price[i]=a
    c = ["0"] * n
    ci = list(map(int,input().split()))
    for j in ci:
        c[n- j]="1"
    can_opens[i]=int("".join(c),2)
inf=float("inf")
dp = [inf] * 2**n
dp[0]=0
#dp[i]は、iを取るために必要な最小費用
for i,(pi,coi) in enumerate(zip(price,can_opens)):
    for j in range(2**n):
        dp[j|coi]=min(dp[j|coi],dp[j]+pi)
from math import isinf
if isinf(dp[-1]):
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
price = [0] * m
can_opens = [0] * m
for i in range(m):
    a,b = list(map(int,input().split()))
    price[i]=a
    c = ["0"] * n
    ci = list(map(int,input().split()))
    for j in ci:
        c[n- j]="1"
    can_opens[i]=int("".join(c),2)
inf=float("inf")
dp = [inf] * 2**n
dp[0]=0
#dp[i]は、iを取るために必要な最小費用
for i,(pi,coi) in enumerate(zip(price,can_opens)):
    for j in range(2**n):
        dp[j|coi]=min(dp[j|coi],dp[j]+pi)
from math import isinf
if isinf(dp[-1]):
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

H,W = map(int, input().split())
A = 0
dp = []
mat = []
for h in range(H):
    dpr = [-1] * W
    for w, x in zip(range(W), input()):
        if x == "#":
            dpr[w] = 0
            mat += [(h, w, 0)]
    dp += [dpr]

def search(dp, mat, conf, nH, nW, cnt):
    if not conf:
        return
    if dp[nH][nW] < 0 or cnt+1<dp[nH][nW]:
        dp[nH][nW] = cnt+1
        mat += [(nH, nW, cnt+1)]

i = 0
while len(mat) > 0:
    h, w, cnt = mat.pop()

    i+=1
    search(dp, mat, h > 0, h - 1, w, cnt)
    search(dp, mat, h < H-1, h + 1, w, cnt)
    search(dp, mat, w > 0, h , w - 1, cnt)
    search(dp, mat, w < W-1, h , w + 1, cnt)

import numpy as np
print(np.max(dp))

### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000) 
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappop, heappush
H,W = map(int,input().split())
C = list(map(int,input().split()))
C[0] -= 1; C[1] -= 1
D = list(map(int,input().split()))
D[0] -= 1; D[1] -= 1
S = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp =list(temp)
  S.append(temp)
#print(S)
reach = [[INF]*W for _ in range(H)]
reach[C[0]][C[1]] = 0
visit = [[False]*W for _ in range(H)]
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = []
Q.append([0,C])
while Q:
  score,z = heappop(Q)
  x = z[0];y=z[1]
  if visit[x][y]:
    continue
  visit[x][y] = True
 
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    #print(nx,ny)
    if 0<=nx<H and 0<=ny<W and S[nx][ny] == "." and reach[nx][ny] > score:
      reach[nx][ny] = min(score,reach[nx][ny])
      u = [nx,ny]
      heappush(Q,[score,u])
  #print(reach)
 
  for i in range(5): #0~4
    for j in range(5):
      mx = x-2 + i
      my = y-2 + j
      if i == 2 and j == 2:
        continue
      if mx < 0 or mx >= H or my < 0 or my >= W or S[mx][my] == "#":
        continue
      if reach[mx][my] <= score+1: #すでにこのスコア以下でいける。
        continue
      reach[mx][my] = min(score+1,reach[mx][my])
      p = [mx,my]
      #print(v,p,"X")
      heappush(Q,[score+1,p])
#dfs(C,0)
#print(reach)
#print(reach[D[0]][D[1]])
if reach[D[0]][D[1]] == INF:
  print(-1)
else:
  print(reach[D[0]][D[1]])

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000) 
input = sys.stdin.readline
from collections import deque
H,W = map(int,input().split())
C = list(map(int,input().split()))
C[0] -= 1; C[1] -= 1
D = list(map(int,input().split()))
D[0] -= 1; D[1] -= 1
S = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp =list(temp)
  S.append(temp)
#print(S)
reach = [[INF]*W for _ in range(H)]
reach[C[0]][C[1]] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([])
Q.append([C,0])
while Q:
  z, score = Q.popleft()
  x = z[0];y=z[1]
 
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    #print(nx,ny)
    if 0<=nx<H and 0<=ny<W and S[nx][ny] == "." and reach[nx][ny] > score:
      reach[nx][ny] = min(score,reach[nx][ny])
      u = [nx,ny]
      Q.appendleft([u,score])
  #print(reach)
 
  for i in range(5): #0~4
    for j in range(5):
      mx = x-2 + i
      my = y-2 + j
      if i == 2 and j == 2:
        continue
      if mx < 0 or mx >= H or my < 0 or my >= W or S[mx][my] == "#":
        continue
      if reach[mx][my] <= score+1: #すでにこのスコア以下でいける。
        continue
      reach[mx][my] = min(score+1,reach[mx][my])
      p = [mx,my]
      #print(v,p,"X")
      Q.append([p,score+1])
#dfs(C,0)
#print(reach)
#print(reach[D[0]][D[1]])
if reach[D[0]][D[1]] == INF:
  print(-1)
else:
  print(reach[D[0]][D[1]])
### BUGGY CODE ###

from itertools import product as prod

n, m = [int(x) for x in input().split()]

gr = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    gr[a].append((b, c))
    gr[b].append((a, c))

def dist(i, j, gr=gr):
    tmp_d = float("inf")
    if i == j:
        return 0
    for (n, d) in gr[i]:
        if n == j:
            tmp_d = d
    gr_cp = [[(n, d) for (n, d) in g if n != i] for g in gr]
    routes = [d + dist(n, j, gr=gr_cp) for (n, d) in gr_cp[i]]

    return min(routes + [tmp_d])

ans = 0
for i, j in prod(range(1, m), range(1, m)):
    for (n, d) in gr[i]:
        if n == j and d > dist(i, j):
            ans += 1
print(ans // 2)


### FIXED CODE ###

import copy
from itertools import product as prod

n, m = [int(x) for x in input().split()]

wait = [[float("inf") for _ in range(n)] for _ in range(n)]
for i in range(n):
    wait[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    wait[a-1][b-1] = c
    wait[b-1][a-1] = c

dist = copy.deepcopy(wait)
for k, i, j in prod(range(n), range(n), range(n)):
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    dist[j][i] = min(dist[j][i], dist[j][k] + dist[k][i])

ans = 0
for i, j in prod(range(n), range(n)):
    if not wait[i][j] == float("inf") and dist[i][j] < wait[i][j]:
        ans += 1

print(ans // 2)
### BUGGY CODE ###

from math import hypot,atan2,pi,cos
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]

K = 300000
ans = 0
for i in range(K+1):
    t1 = 2*pi*i/K - pi
    r = 0
    for x,y in XY:
        t2 = atan2(y,x)
        a,b = (t1,t2) if t1<t2 else (t2,t1)
        if b-a > 3*pi/2:
            a += 2*pi
            a,b = b,a
        d = hypot(x,y) * cos(b-a)
        if d > 0:
            r += d
    ans = max(ans, r)
print(ans)

### FIXED CODE ###

from math import hypot,atan2
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]
xy = sorted(XY, key=lambda x:atan2(x[1],x[0]))
xy += xy

ans = 0
for i in range(N):
    sx = sy = 0
    for j in range(N):
        x,y = xy[i+j]
        sx += x
        sy += y
        d = hypot(sx,sy)
        if d > ans:
            ans = d
print(ans)
### BUGGY CODE ###


def main():
    import numpy as np
    n = int(input())
    s = input()
    dic = {'R':np.array([]),'G':np.array([]),'B':np.array([])}
    for i in range(n):
        if s[i]== 'R':
            dic['R'] = np.append(dic['R'],i)
        elif s[i]== 'G':
            dic['G'] = np.append(dic['G'],i)
        else:
            dic['B'] = np.append(dic['B'],i)
    cnt = len(dic['R'])*len(dic['G'])*len(dic['B'])
    for i in dic['R']:
        for j in dic['G']:
            if abs(j-i)%2==0:
                no = np.array([(j+i)//2,2*j-i,2*i-j])
            else:
                no = np.array([2*j-i,2*i-j])
            cnt -= len(np.intersect1d(no,dic['B']))
    print(cnt)
     
            
if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    n = int(input())
    s = input()
    dic = {'R':[],'G':[],'B':[]}
    for i in range(n):
        if s[i]== 'R':
            dic['R'].append(i)
        elif s[i]== 'G':
            dic['G'].append(i)
        else:
            dic['B'].append(i)
    cnt = len(dic['R'])*len(dic['G'])*len(dic['B'])
    for i in range(1,n//2+1):
        for j in range(n-2*i):
            if s[j]!=s[j+i] and s[j+i] != s[j+i+i] and s[j]!=s[j+i+i]:
                cnt -=1
    print(cnt)
     
            
if __name__ == "__main__":
    main()
### BUGGY CODE ###

s = input()
q = int(input())

rev = True

for i in range(q):
    q = list(input().split())
    if(int(q[0]) == 1):
        rev = rev ^ True
    else:
        txt = ''.join(q[2:])
        if((int(q[1]) == 1 and rev == True) or (int(q[1]) == 2 and rev == False)):
            s = txt + s
        else:
            s += txt

if rev:
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###

from collections import deque

s = deque(list(input()))
q = int(input())

rev = True

for i in range(q):
    q = list(input().split())
    if(int(q[0]) == 1):
        rev = rev ^ True
    else:
        n = int(q[1])
        if((n == 1 and rev) or (n == 2 and not rev)):
            s.appendleft(q[2])
        else:
            s.append(q[2])


txt = ''
if rev:
    txt = ''.join(s)
else:
    while not(not s):
        txt += s.pop()

print(txt)
### BUGGY CODE ###

from collections import deque

def count_pair(k):
    cnt = 0
    for i in range(1, N+1):
        visited = [-1]*(N+1)
        visited[i] = 0
        s = 0
        q = deque([[i]])
        while s != k:
            p = []
            A = q.popleft()
            for a in A:
                if a == X and visited[Y] == -1:
                    p.append(Y)
                    visited[Y] = 0
                if a == Y and visited[X] == -1:
                    p.append(X)
                    visited[X] = 0
                if a+1 <=N and visited[a+1] == -1:
                    p.append(a+1)
                    visited[a+1] = 0
                if a-1 >= 1 and visited[a-1] == -1:
                    p.append(a-1)
                    visited[a-1] = 0
            q.append(p)
            s += 1
        r = q[0]
        t = 0
        for j in range(len(r)):
            if r[j] > i:
                t += 1
        cnt += t
    return cnt

N, X, Y = map(int, input().split())
for k in range(1, N):
    print (count_pair(k))

### FIXED CODE ###

N, X, Y = map(int, input().split())
t = [0]*N
for i in range(1, N):
    for j in range(i+1, N+1):
        t[min(j-i, abs(X-i)+1+abs(j-Y))] += 1
for k in range(1, N):
    print (t[k])
### BUGGY CODE ###

import numpy as np
A, B, Q = list(map(int, input().split()))
s = []
t = []
s.append(-100000000000)
s.append(100000000000)
t.append(-100000000000)
t.append(100000000000)
for i in range(A):
    s.append(int(input()))
s = sorted(s, reverse=False)
sn = np.array(s)
for i in range(B):
    t.append(int(input()))
t = sorted(t, reverse=False)
tn = np.array(t)
for i in range(Q):
    xi = int(input())

    stot = min(abs(xi - sn[sn.searchsorted(xi)])
               + abs(sn[sn.searchsorted(xi)] - tn[tn.searchsorted(sn[sn.searchsorted(xi)])]),
               abs(xi - sn[sn.searchsorted(xi)])
               + abs(sn[sn.searchsorted(xi)] - tn[tn.searchsorted(sn[sn.searchsorted(xi)]) - 1]),
               abs(xi - sn[sn.searchsorted(xi) - 1])
               + abs(sn[sn.searchsorted(xi) - 1] - tn[tn.searchsorted(sn[sn.searchsorted(xi) - 1])]),
               abs(xi - sn[sn.searchsorted(xi) - 1])
               + abs(sn[sn.searchsorted(xi) - 1] - tn[tn.searchsorted(sn[sn.searchsorted(xi) - 1]) - 1])
               )
    ttos = min(abs(xi - tn[tn.searchsorted(xi)])
               + abs(tn[tn.searchsorted(xi)] - sn[sn.searchsorted(tn[tn.searchsorted(xi)])]),
               abs(xi - tn[tn.searchsorted(xi)])
               + abs(tn[tn.searchsorted(xi)] - sn[sn.searchsorted(tn[tn.searchsorted(xi)]) - 1]),
               abs(xi - tn[tn.searchsorted(xi) - 1])
               + abs(tn[tn.searchsorted(xi) - 1] - sn[sn.searchsorted(tn[tn.searchsorted(xi) - 1])]),
               abs(xi - tn[tn.searchsorted(xi) - 1])
               + abs(tn[tn.searchsorted(xi) - 1] - sn[sn.searchsorted(tn[tn.searchsorted(xi) - 1]) - 1])
               )
    print(min(stot, ttos))


### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
A, B, Q = list(map(int, input().split()))
s = [int(input()) for i in range(A)]
t = [int(input()) for i in range(B)]
s.append(-100000000000);s.append(100000000000)
t.append(-100000000000);t.append(100000000000)
s = sorted(s, reverse=False)
t = sorted(t, reverse=False)

for i in range(Q):
    xi = int(input())
    sr = s[bisect.bisect_left(s, xi)]
    sl = s[bisect.bisect_left(s, xi) - 1]
    tr = t[bisect.bisect_left(t, xi)]
    tl = t[bisect.bisect_left(t, xi) - 1]

    ans = min(max(sr, tr) - xi, xi - min(sl, tl),
              tr - sl + min(tr - xi, xi - sl), sr - tl + min(sr - xi, xi - tl))
    print(ans)
### BUGGY CODE ###

from bisect import bisect_left
x,y,z,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=sorted([int(i) for i in input().split()],reverse=True)
ab_max=[]
for i in range(x):
    for j in range(y):
        ab_max.append(a[i]+b[j])
ab_max.sort()
def unti(t_sub):
    ret=0
    for i in range(x*y):
        h=z-bisect_left(c,t_sub-ab_max[i])
        if h!=0:
            ret+=h
        else:
            return ret
    return ret
l,r=0,ab_max[0]+max(c)
while r>l+1:
    t=(l+r)//2
    if unti(t)>=k:
        r=t
    else:
        l=t
ans=[]
for i in range(x*y):
    for j in range(z):
        u=ab_max[i]+c[j]
        if u>=r:
            ans.append(u)
        else:
            break
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])


### FIXED CODE ###

import heapq
x,y,z,k=map(int,input().split())
#heapqは小さい順にしか並べられないので、-をつければ大きい順になる
a=sorted([-int(i) for i in input().split()])
b=sorted([-int(i) for i in input().split()])
c=sorted([-int(i) for i in input().split()])
check=set()
ans=[]
heapq.heappush(ans,(a[0]+b[0]+c[0],0,0,0))
check.add((0,0,0))
for i in range(k):
    h=heapq.heappop(ans)
    print(-h[0])
    if h[1]+1<x:
        if (h[1]+1,h[2],h[3]) not in check:
            heapq.heappush(ans,(a[h[1]+1]+b[h[2]]+c[h[3]],h[1]+1,h[2],h[3]))
            check.add((h[1]+1,h[2],h[3]))
    if h[2]+1<y:
        if (h[1],h[2]+1,h[3]) not in check:
            heapq.heappush(ans,(a[h[1]]+b[h[2]+1]+c[h[3]],h[1],h[2]+1,h[3]))
            check.add((h[1],h[2]+1,h[3]))
    if h[3]+1<z:
        if (h[1],h[2],h[3]+1) not in check:
            heapq.heappush(ans,(a[h[1]]+b[h[2]]+c[h[3]+1],h[1],h[2],h[3]+1))
            check.add((h[1],h[2],h[3]+1))
'''
while len(ans)!=0:
    print(heapq.heappop(ans)[0])
'''
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 9)
M = 10 ** 9 + 7


cache = {}

# Combination under a prime modulo: nCk % p
def combmod(n, k, p=M):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    if (n, k) in cache:
        return cache[n, k]
    num, den = 1, 1
    for i in range(k):
        num = num * (n - i) % p
        den = den * (i + 1) % p
    # By Fermat's little theorem,
    # a^(p-1) ≡ 1 mod p
    # i.e. a^(p-2) ≡ a^(-1) mod p
    inv_dev = pow(den, p - 2, p)
    res = num * inv_dev % p
    cache[n, k] = res
    return res


n = int(input())
a = list(map(int, input().split()))
assert len(a) == n + 1

b = [None] * (n + 1)
d1, d2 = -1, -1
for i in range(n + 1):
    if b[a[i]] is None:
        b[a[i]] = i
    else:
        d1 = b[a[i]]
        d2 = i
        break
assert d1 >= 0 and d2 >= 0 and a[d1] == a[d2]


def comb(n, k):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    if k == 0:
        return 1
    if k == 1:
        return n
    if (n, k) in cache:
        return cache[n, k]
    res = combmod(n - 1, k) + combmod(n - 1, k - 1)
    cache[n, k] = res
    return res


for k in range(1, n + 2):
    ans = comb(n + 1, k) - comb(n - d2 + d1, k - 1)
    print(ans % M)


### FIXED CODE ###

import sys

input = sys.stdin.readline
M = 10 ** 9 + 7

n = int(input())
a = list(map(int, input().split()))
assert len(a) == n + 1

b = [None] * (n + 1)
d1, d2 = -1, -1
for i in range(n + 1):
    if b[a[i]] is None:
        b[a[i]] = i
    else:
        d1 = b[a[i]]
        d2 = i
        break
assert d1 >= 0 and d2 >= 0 and a[d1] == a[d2]


a, b, ik = n + 1, 1, 1
for k in range(1, n + 2):
    ans = (a - b) % M
    print(ans)
    b = b * (n + 1 - d2 + d1 - k) * ik % M
    ik = pow(k + 1, M - 2, M)
    a = a * (n + 1 - k) * ik % M
### BUGGY CODE ###

n = int(input())
s = "a" + input() + "a"
ma = n

for i in range(1,n+1):
  c = s[:i].count("W") + s[i+1:].count("E")
  ma = min(c,ma)
  if ma == 0:
    print(0)
    exit()
    
print(ma)

### FIXED CODE ###

n = int(input())
s = input()
ma = s[1:].count("E")
maa = ma

for i in range(n-1):
  if s[i] == "W" and s[i+1] == "W":
    ma += 1
  elif s[i] == "E" and s[i+1] == "E":
    ma -= 1
    
  maa = min(maa,ma)
  
print(maa)