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

n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    g[a-1].append([b-1,c])
    g[b-1].append([a-1,c])
q,k=map(int,input().split())
qu=[[k-1,0]]
v=[0]*n
d=[0]*n
while len(qu)>0:
    s=qu.pop(0)
    v[s[0]]=1
    for j in g[s[0]]:
        if not v[j[0]]:
            v[j[0]]=1
            d[j[0]]=s[1]+j[1]
            qu.append([j[0],d[j[0]]])
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])


### FIXED CODE ###

from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    g[a-1].append([b-1,c])
    g[b-1].append([a-1,c])
q,k=map(int,input().split())
qu=deque([[k-1,0]])
v=[0]*n
d=[0]*n
while len(qu)>0:
    s=qu.popleft()
    v[s[0]]=1
    for j in g[s[0]]:
        if not v[j[0]]:
            v[j[0]]=1
            d[j[0]]=s[1]+j[1]
            qu+=[[j[0],d[j[0]]]]
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])
### BUGGY CODE ###

import sys
from heapq import heappop, heappush

def main():
    input = sys.stdin.readline
    INF = 10**15
    ans = INF
    N, M = map(int, input().split())
    heap = []
    for _ in range(M):
        l, r, c = map(int, input().split())
        heappush(heap, (l-1, r-1, c))
    
    front = []
    heappush(front, (0, 0))
    while heap:
        l, r, c = heappop(heap)

        front_ = []
        while front:
            r_, c_ = heappop(front)
            if r_ < l:
                continue
            
            heappush(front_, (r_, c_))
            heappush(front_, (r, c+c_))
            if r == N-1:
                ans = min(ans, c+c_)
        
        front = front_
            
    if ans == INF:
        return -1
    
    return ans

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import sys
from heapq import heappop, heappush, heapify

def dijkstra(s, t, links):
    """Dijkstra algorism
    s: int, start node.
    t: int, target node.
    links: iterable, link infomation.
           links[i] contains edges from node i: (cost, target_node).

    return int, minimal cost from s node to t node.
    """
    heap = list(links[s])
    heapify(heap)
    visited = set()
    while len(heap) > 0:
        cost, node = heappop(heap)
        if node == t:
            return cost

        if node in visited:
            continue

        visited.add(node)
        for cost2, node2 in links[node]:
            if node2 in visited:
                continue

            heappush(heap, (cost + cost2, node2))

    return -1

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    links = [[] for _ in range(N)]
    for i in range(1, N):
        links[i].append((0, i-1))

    for _ in range(M):
        l, r, c = map(int, input().split())
        links[l-1].append((c, r-1))
    
    return dijkstra(0, N-1, links)
    

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

#

import sys
input=sys.stdin.readline

MOD=10**9+7
            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    kl=set()
    p=[{} for i in range(N)]
    for j in range(N):
        n=A[j]
        ret={}
        for i in range(2,int((n)**0.5)+1):
            if n%i==0:
                cnt=0
                while(n%i==0):
                    n/=i
                    cnt+=1
                ret[i]=cnt
                kl.add(i)
        if n!=1:
            ret[int(n)]=1
            kl.add(int(n))
        p[j]=ret
    lcm=1
    for i in kl:
        maxipow=0
        for j in range(N):
            maxipow=max(maxipow,p[j].get(i,0))
        lcm*=i**maxipow
        lcm%=MOD

    lcm%=MOD
    ans=0
    for i in range(N):
        ans+=lcm*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()


### FIXED CODE ###

#

import sys
from fractions import gcd
input=sys.stdin.readline

def main():
    MOD=10**9+7
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    l=(A[0]*A[1])//gcd(A[0],A[1])
    for i in range(2,N):
        l=(l*A[i])//gcd(A[i],l-A[i])
    l%=MOD
    ans=0
    for i in range(N):
        ans+=l*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

from itertools import permutations,combinations

N, K = map(int, input().split())
L = list(map(int, input().split()))
P = list(combinations(L, K))
maximum = 0
for p in P:
    maximum = max(maximum, sum(p))
print(maximum)


### FIXED CODE ###

n, k = map(int, input().split())
L = list(map(int,input().split()))
print(sum(sorted(L, reverse=True)[:k]))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
r=max(a)
e=len(bin(r))-2
p=[[]for _ in range(n)]
for i in range(e):
	for j in range(n):
		p[j].append(a[j]%2)
		a[j]//=2
ans=0
cnt=[0]*e
j=0
for i in range(n):
	while 2 not in cnt and j<n:
		for k in range(e):
			cnt[k]+=p[j][k]
		j+=1
	if 2 not in cnt:
		ans+=1
	ans+=j-i-1
	for k in range(e):
		cnt[k]-=p[i][k]
print(ans)



### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
r=max(a)
e=len(bin(r))-2
p=[[]for _ in range(n)]
for i in range(e):
	for j in range(n):
		p[j].append(a[j]%2)
		a[j]//=2
ans=0
cnt=[0]*e
j=0
for i in range(n):
	while 2 not in cnt and j<n:
		for k in range(e):
			cnt[k]+=p[j][k]
		j+=1
	if 2 not in cnt:
		ans+=1
	ans+=j-i-1
	for k in range(e):
		cnt[k]-=p[i][k]
print(ans)
### BUGGY CODE ###

import bisect
N,M=[int(i) for i in input().split()]
A = sorted([int(i) for i in input().split()])
for i in range(M):
  A2=A[N-1]//2
  A.pop(N-1)
  A.insert(bisect.bisect_left(A, A2), A2)
print(sum(A))


### FIXED CODE ###

import heapq
N,M=[int(i) for i in input().split()]
A=sorted([-int(i) for i in input().split()])
for i in range(M):heapq.heappush(A,-(-heapq.heappop(A)//2))
print(-sum(A))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
if a[0] != 1:
  a[0] = 1
  ans += 1
b = [[]for i in range(n)]
for i in range(n):
  b[a[i]-1].append(i)
b[0].remove(0)
huka = 0
kyo = [float("inf")] * n
z =[[]for i in range(n)]
def dfs(x,y):
  kyo[x] = y
  z[y].append(x)
  for i in b[x]:
    dfs(i,y+1)
dfs(0,0)
def dfs2(x,y):
  if kyo[x] <=k-y:
    return
  if y == k-1 and x != 0:
    kyo[x] = 0
    global ans
    ans += 1
    return
  kyo[x] = 0
  dfs2(a[x]-1,y+1)
for i in range(n-1,k,-1):
  for j in z[i]:
    dfs2(j,0)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
if a[0] != 1:
  a[0] = 1
  ans += 1
b = [[]for i in range(n)]
for i in range(1,n):
  b[a[i]-1].append(i)
huka = 0
kyo = [float("inf")] * n
z =[[]for i in range(n)]
def dfs(x,y):
  kyo[x] = y
  z[y].append(x)
  for i in b[x]:
    dfs(i,y+1)
dfs(0,0)
def dfs2(x,y):
  if kyo[x] <=k-y:
    return
  if y == k-1 and x != 0:
    kyo[x] = 0
    global ans
    ans += 1
    return
  kyo[x] = 0
  dfs2(a[x]-1,y+1)
for i in range(n-1,k,-1):
  for j in z[i]:
    dfs2(j,0)
print(ans)
### BUGGY CODE ###

# AGC 028 A
N, M = map(int, input().split())
S = input()
T = input()

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
def lcm(a,b):
    return a*b//gcd(a,b)

if S[0] != T[0]:
    print(-1)
    exit(0)
if S == T:
    print(N)
    exit(0)

L = lcm(N,M)
p = L//N
q = L//M
U = ""
k = 0

if gcd(M,N) > 1:
    for k in range(1,L):
        if k%p == 0 and k%q == 0:
            if S[k//p] != T[k//q]:
                print(-1)
                exit(0)
    print(L)
else:
    print(L)


### FIXED CODE ###

# AGC 028 A
N, M = map(int, input().split())
S = input()
T = input()

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
def lcm(a,b):
    return a*b//gcd(a,b)

if S[0] != T[0]:
    print(-1)
    exit(0)
if S == T:
    print(N)
    exit(0)

L = lcm(N,M)
p = L//N
q = L//M
U = ""
k = 0

if gcd(M,N) > 1:
    for k in range(1,L):
        if k%p == 0 and k%q == 0:
            if S[k//p] != T[k//q]:
                print(-1)
                exit(0)
    print(L)
else:
    print(L)
### BUGGY CODE ###

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


def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

# mod=10**9+7
# rstrip().decode('utf-8')

import re

def main():
	n=II()
	s=input()
	ans=0
	for i in range(1000):
		a,b,c=str(i).zfill(3)
		m=re.search(r'%s.*%s.*%s'%(a,b,c),s)
		if m!=None:
			ans+=1
	print(ans)



















if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
#MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
#import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	n=int(input())
	s=input().rstrip().decode('utf-8')
	
	ans=0
	
	for a in range(10):
		a=str(a)
		aidx=s.index(a) if a in s else -1
		if aidx!=-1:
			ss=s[aidx+1:]
			for b in range(10):
				b=str(b)
				bidx = ss.index(b) if b in ss else -1
				if bidx != -1:
					sss=ss[bidx+1:]
					for c in range(10):
						c=str(c)
						if c in sss:
							ans+=1
	
	print(ans)
	
	
if __name__ == "__main__":
		main()
### BUGGY CODE ###

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

sum=0
tmp=0
for i in range(n):
    o = i+1
    tmp = 0
    while (o<n):
        tmp=a[o]+tmp
        o=o+1
    sum=(a[i]*tmp)+sum

print(sum%1000000007)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=1000000007
sum=0
tmp=0
o=0
while(o<n):
    tmp = (a[o]%mod + tmp%mod)%mod
    o += 1

for i in range(n):
    tmp=(tmp%mod-a[i]%mod)%mod
    sum=((a[i]%mod)*tmp)%mod+sum%mod



print(sum%mod)
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for i in range(q)]

if k - q > 0:
  res = ['Yes'] * n
else:
  res = ['No'] * n
  ans = set(a)
  for i in ans:
    if k - q + a.count(i) > 0:
      res[i-1] = 'Yes'
print('\n'.join(map(str, res)))

### FIXED CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for i in range(q)]

if k - q > 0:
  res = ['Yes'] * n
else:
  res = ['No'] * n
  ans = [0] * n
  for i in range(len(a)):
    ans[a[i]-1] += 1
  for i in range(n):
    if k - q + ans[i] > 0:
      res[i] = 'Yes'
print('\n'.join(map(str, res)))
### BUGGY CODE ###

import bisect
import functools
import os
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

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


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        ret = fn(*args, **kwargs)
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        print(ret)
        return ret

    return wrapper


@debug
def calc_bit(k):
    """
    答えの下から k ビット目を返す
    :param int k:
    :return:
    """
    # 答えの k ビット目が偶数なら 0、奇数なら 1

    # これ以上の桁は不要
    mod = 1 << (k + 1)
    amod = [a % mod for a in A]
    bmod = [b % mod for b in B]
    bmod.sort()
    ret = 0
    for a in amod:
        # bmod + a のうち k ビット目が 1 となる数
        # => (1 << k) 以上 (2 << k) 未満または (3 << k) 以上 (4 << k) 未満
        ret += bisect.bisect_left(bmod, (2 << k) - a) - bisect.bisect_left(bmod, (1 << k) - a)
        ret += bisect.bisect_left(bmod, (3 << k) - a) - bisect.bisect_left(bmod, (4 << k) - a)

    return ret % 2


ans = 0
for i in range(30):
    ans += calc_bit(i) * (2 ** i)
print(ans)


### FIXED CODE ###

import bisect
import functools
import os
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

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


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        ret = fn(*args, **kwargs)
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        print(ret)
        return ret

    return wrapper


@debug
def calc_bit(k):
    """
    答えの下から k ビット目を返す
    :param int k:
    :return:
    """
    # 答えの k ビット目が偶数なら 0、奇数なら 1

    # これ以上の桁は不要
    mod = 1 << (k + 1)
    amod = [a & (mod - 1) for a in A]
    bmod = [b & (mod - 1) for b in B]
    amod.sort()
    bmod.sort()
    ret = 0

    # bmod + amod のうち k ビット目が 1 となる数
    # => (1 << k) 以上 (2 << k) 未満または (3 << k) 以上 (4 << k) 未満
    # しゃくとる
    b01 = bisect.bisect_left(bmod, (1 << k) - amod[0])
    b10 = bisect.bisect_left(bmod, (2 << k) - amod[0])
    b11 = bisect.bisect_left(bmod, (3 << k) - amod[0])
    for a in range(len(amod)):
        while b01 - 1 >= 0 and bmod[b01 - 1] >= (1 << k) - amod[a]:
            b01 -= 1
        while b10 - 1 >= 0 and bmod[b10 - 1] >= (2 << k) - amod[a]:
            b10 -= 1
        while b11 - 1 >= 0 and bmod[b11 - 1] >= (3 << k) - amod[a]:
            b11 -= 1
        # (1 << k) 以上 (2 << k) 未満
        ret += b10 - b01
        # (3 << k) 以上 (4 << k) 未満
        ret += len(bmod) - b11

    return ret % 2


ans = 0
for i in range(30):
    ans += calc_bit(i) * (2 ** i)
print(ans)
### BUGGY CODE ###

N, Y = map(int, input().split())
flag = False
for x in range(0, N+1):
    for y in range(0, N+1-x):
        for z in range(0, N+1-x-y):
            if 10000*x + 5000*y + 1000*z == Y and x+y+z==N:
                print(x,y,z)
                flag = True
                break
        if flag:
            break
    if flag:
        break
else:
    print('-1 -1 -1')

### FIXED CODE ###

N,Y=map(int,input().split())
answer=-1,-1,-1
for x in range(N+1):
    for y in range(N-x+1):
        z=N-x-y
        if 0<=z<=2000 and 10000*x+5000*y+1000*z==Y:
            answer=x,y,z
            break
    else:
        continue
    break
print(*answer)
### BUGGY CODE ###

N = int(input())


def rk():
    l0, l1 = 2, 1
    while 1:
        yield l0 + l1
        l0, l1 = l1, l0 + l1


for i, n in enumerate(rk()):
    if i == N - 2:
        print(n)


### FIXED CODE ###

N = int(input())


def lc():
    l0, l1 = 2, 1
    while 1:
        yield l0 + l1
        l0, l1 = l1, l0 + l1


if N > 1:
    for i, n in enumerate(lc()):
        if i == N - 2:
            print(n)
            break
else:
    print(1)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()

def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    l = [0] * N
    ans = 0
    count = 0
    check = [False] * N
    tmpl = []

    while(count < N):
        check = [False] * N
        for i in range(N):
            if l[i] < N - 1:
                to = A[i][l[i]] - 1
                if (not check[to]) and (not check[i]):
                    if A[to][l[to]] - 1 == i:
                        l[i] += 1
                        l[to] += 1
                        check[to] = True
                        check[i] = True
                    if l[i] == N - 1:
                        count += 1
                    if l[to] == N - 1:
                        count += 1
        ans += 1
        if tmpl == l:
            print(-1)
            exit()
        tmpl = l[:]
        # print(l, ans)

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import time
def input():
    return sys.stdin.readline()
 
def main():
    a = time.time()
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    l = [0] * N
    ans = 0
    count = 0
    check = [False] * N
    tmpl = []
    next = False
 
    while(count < N):
        check = [False] * N
        for i in range(N):
            if l[i] < N - 1:
                to = A[i][l[i]] - 1
                if (not check[to]) and (not check[i]):
                    if A[to][l[to]] - 1 == i:
                        l[i] += 1
                        l[to] += 1
                        check[to] = True
                        check[i] = True
                        next = True
                    if l[i] == N - 1:
                        count += 1
                    if l[to] == N - 1:
                        count += 1
        ans += 1
        if not next:
            print(-1)
            exit()
        next = False

        b = time.time()
        if b - a >= 1.7:
            print(N*(N - 1)//2)
            exit()
        # print(l, ans)
 
    print(ans)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# coding: utf-8

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

for (i, x) in enumerate(s):
    if x == "E":
        s[i] = 1
    elif x == "W":
        s[i] = 0

min_changed_num = sum(s[1:n])

for i in range(1, n):
    left = i - sum(s[0:i])
    right = sum(s[i:n])
    changed_num = left + right
    if min_changed_num > changed_num:
        min_changed_num = changed_num

print(min_changed_num)


### FIXED CODE ###

# coding: utf-8

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

for (i, x) in enumerate(s):
    if x == "E":
        s[i] = 1
    elif x == "W":
        s[i] = 0

left = 0
right = sum(s[1:n])
center = s[0]
min_changed_num = right

for i in range(1, n):
    left = left + (1 - center)
    center = s[i]
    right = right - center
    changed_num = left + right
    if min_changed_num > changed_num:
        min_changed_num = changed_num

print(min_changed_num)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
if X>Y and X>Z:
  X,Z=Z,X
  A,C=C,A
elif Y>X and Y>Z:
  Y,Z=Z,Y
  B,C=C,Y
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=sorted(list(map(int,input().split())),reverse=True)
k=min(K,X*Y)
AB=sorted([a+b for a in A for b in B],reverse=True)[:k]
ABC=sorted([ab+c for ab in AB for c in C[:K]],reverse=True)[:K]
for x in ABC:
  print(x)

### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
B=sorted(list(map(int,input().split())),reverse=True)
C=sorted(list(map(int,input().split())),reverse=True)
ans=[]
for i in range(X):
  if i+1>K:
    break
  for j in range(Y):
    if (i+1)*(j+1)>K:
      break
    for k in range(Z):
      if (i+1)*(j+1)*(k+1)>K:
        break
      ans.append(A[i]+B[j]+C[k])
ans=sorted(ans,reverse=True)
for a in ans[:K]:
  print(a)
### BUGGY CODE ###

s,_,*q=open(0)
a=['',s[:-1]]
p=1
for q in q:
  try:
    q,f,c=q.split()
    i=(f<'2')^p
    a[i]=''.join((a[i],c))
  except:p^=1
print(a[p^1][::-1]+a[p])

### FIXED CODE ###

from collections import*
s,_,*q=open(0)
d=deque(s[:-1])
p=1
for q in q:
  try:
    q,f,c=q.split()
    if(f<'2')^p:d+=c,
    else:d.appendleft(c)
  except:p^=1
print(''.join(d)[::p or-1])
### BUGGY CODE ###

def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    dp = [0 for _ in range(1 << N)]
    dp[0] = 1
    for s in range(1, 1 << N):
        man = sum(map(int, '{:b}'.format(s))) - 1  # count bits
        val = 0
        for woman in range(len('{:b}'.format(s))):
            if (s >> woman) & 1 == 0:
                continue
            if A[man][woman] == 1:
                val += dp[s - (1 << woman)]
                val %= MOD
        dp[s] += val
    print(dp[(1 << N) - 1])


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    dp = [0 for _ in range(1 << N)]
    dp[0] = 1
    for s in range(1, 1 << N):
        women_list = [w for w in range(N) if (s >> w) & 1 == 1]
        man = len(women_list) - 1
        val = 0
        for woman in women_list:
            val += A[man][woman] * dp[s - (1 << woman)]
        val %= MOD
        dp[s] += val
    print(dp[(1 << N) - 1])


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

import sys

N = int(sys.stdin.readline())

S = sys.stdin.readline()

set = [0]*N
for i in range(N):
    counter = 0
    counter = S[0:i].count("W") + S[i:N].count("E")
    set[i] = counter

print(min(set))

### FIXED CODE ###

import sys

N = int(sys.stdin.readline())
S = sys.stdin.readline()

right = S[1:].count("E")
left = 0
ans = [0]*N
ans[0] = right + left
for i in range(1, N):
    if S[i] == "E":
        right = right - 1
    if S[i-1] == "W":
        left = left + 1
    ans[i] = right+left

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

import sys, math, fractions, itertools, collections


def solve(N: int, s: "List[str]"):
    S = []
    for ss in s:
        ss = sorted(ss)
        S.append(''.join(ss))
    c = collections.Counter(S).values()
    s = 0
    for cc in c:
        s += len(list(itertools.combinations(range(cc), 2)))
    print(s)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [ next(tokens) for _ in range(N) ]  # type: "List[str]"
    solve(N, s)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, fractions, itertools, collections


def solve(N: int, s: "List[str]"):
    S = []
    for ss in s:
        ss = sorted(ss)
        S.append(''.join(ss))
    c = list(collections.Counter(S).values())
    s = 0
    for cc in c:
        s += cc*(cc-1)//2
    print(s)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [ next(tokens) for _ in range(N) ]  # type: "List[str]"
    solve(N, s)

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

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
H = list(map(int,readline().split()))

INF = 10 ** 10
dp = [INF] * N
dp[0] = 0

for i in range(N - 1):
  for j in range(1, K + 1):
    if i + j >= N:
      break
    if dp[i + j] > dp[i] + abs(H[i + j] - H[i]):
      dp[i + j] = dp[i] + abs(H[i + j] - H[i])
      
print(dp[N - 1])

### FIXED CODE ###

N,K = map(int, input().split())
H = list(map(int, input().split()))
 
inf = 10**4*N
dp = [inf]*N
dp[0] = 0
for i,h in enumerate(H):
    if i == 0:
        continue
    m = max(0, i-K)
    dp[i] = min([dpj + abs(h - hj) for dpj, hj in zip(dp[m:i], H[m:i])])
print(dp[N-1])
### BUGGY CODE ###

N, Q = [int(x) for x in input().split()]
S = input()

for q in range(Q):
    l, r = [int(x) for x in input().split()]
    str = S[l - 1: r]
    # print(str)
    print(str.count('AC'))


### FIXED CODE ###

N, Q = [int(x) for x in input().split()]
S = input()

t = [0] * N
a = [0] * N

for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        t[i] = 1

a[0] = 0
for i in range(N - 1):
    a[i + 1] = a[i] + t[i]

for q in range(Q):
    l, r = [int(x) for x in input().split()]
    print(a[r - 1] - a[l - 1])
### BUGGY CODE ###

A,B,C,X,Y = map(int, input().split())
ans = X*A + Y*B
for i in range(10**5):
    C = 2*C*i + max(0,X-i)*A + max(0,Y-i)*B
    ans = min(ans, C)
print(ans)  

### FIXED CODE ###

a, b, c, x, y = map(int, input().split())

res = a*x + b*y
for i in range(1, max(x, y)+1):
    ab = i*2
    cand = ab*c + a*max(0, x-i) + b*max(0, y-i)

    res = min(res, cand)

print(res)