The Rumbling is a hypothetical cataclysmic event involving Karl Fritz's Wall Titans marching across the Earth, destroying all life upon it. Eren Yeager who possesses the Founding Titan has decided to begin The Rumbling to show the true power of the Eldians to the rest of the world.

There are N Titans standing in a line from west to east. Each of the Titans is facing one of the four directions i.e., North, South, East, or West, represented by uppercase English letters 'N', 'S', 'E', and 'W' respectively.

A Titan can rotate on the spot where it is standing. It requires X units of energy to rotate 90 degrees clockwise, and  Y units of energy to rotate 90 degrees anti-clockwise.

For the activation of The Rumbling, all the Titans must face Eren Yeager.

So, Eren wants to position himself on the West-East line (on which other Titans are standing). He can either stand to the left of all Titans, in between two consecutive Titans, or to the right of all Titans. He wants to choose a position that minimizes the units of energy required by all the Titans to rotate and face him. Find the minimum units of energy required by all the Titans for the Activation of the Rumbling in the optimal configuration.

------ Input Format ------ 

- The first line consists of T, the number of test cases. Description of the test cases follow.
- The first line of each test case will contain N, the number of Titans.
- The second line of each test case will contain a string S of length N, where the i^{th} character represents the directions faced by the i^{th} Titan.
- The third line of each test case will contain two space-separated integers, the values of X and Y.

------ Output Format ------ 

For each test case, output a single line containing one integer, the answer to that test case.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 2 * 10^{5}$
$1 ≤ X, Y ≤ 10^{9}$
$S$ contains characters from {'N', 'S', 'E', 'W'} only.
- Sum of $N$ over all test cases doesn't exceed $10^{6}$

----- Sample Input 1 ------ 
1
5
SENWS
2 1
----- Sample Output 1 ------ 
4
----- explanation 1 ------ 
- One valid configuration would be as follows: $EE \cdot WWW$, where $\cdot$ represents the position of Eren Yeager. 
- The first and the second Titans will face Eren at East from the left while the third, fourth, and the fifth Titans will face Eren at West from the right. 
- It takes $1$ unit of energy for the first Titan to move towards East by rotating $90$ degrees anticlockwise. 
- The second Titan is already facing East, so it costs him $0$ units of energy to stay that way.
- It takes $1$ unit of energy for the third Titan to move towards West by rotating $90$ degrees anticlockwise.
- The fourth Titan is already facing West, so it costs him $0$ units of energy to stay that way.
- It takes $2$ units of energy for the fifth Titan to move towards West by rotating $90$ degrees clockwise.
- So, it takes the Titans $4$ units of energy overall to face Eren Yeager, and activate The Rumbling!

Difficulty: HARD
Tags: Range queries
Skill types: Range queries

Starter code:

Solutions:
for _ in range(int(input())):
	N = int(input())
	S = input()
	(R, L) = list(map(int, input().split()))
	energy = []
	east_vals = {'N': min(R, 3 * L), 'S': min(L, 3 * R), 'E': 0, 'W': min(2 * L, 2 * R)}
	west_vals = {'N': min(L, 3 * R), 'S': min(R, 3 * L), 'W': 0, 'E': min(2 * L, 2 * R)}
	sm1 = 0
	sm2 = 0
	for i in range(N):
		sm1 += east_vals[S[i]]
	ans = sm1
	for i in range(N - 1, -1, -1):
		ans = min(ans, sm1 + sm2)
		sm1 -= east_vals[S[i]]
		sm2 += west_vals[S[i]]
	ans = min(ans, sm1 + sm2)
	print(ans)


T = int(input(''))
for _ in range(T):
	N = int(input(''))
	line = input('')
	(X, Y) = map(int, input('').rstrip().split(' '))
	costs = {}
	DIRECTIONS = {'N': 0, 'E': 1, 'S': 2, 'W': 3}
	for direction_val in DIRECTIONS.values():
		for dest_direction in ('E', 'W'):
			dest_direction_val = DIRECTIONS[dest_direction]
			costs[direction_val, dest_direction_val] = min(X * ((dest_direction_val - direction_val) % 4), Y * ((direction_val - dest_direction_val) % 4))
	min_sum = 0
	for i in range(N):
		min_sum += costs[DIRECTIONS[line[i]], DIRECTIONS['W']]
	curr_sum = min_sum
	for i in range(N):
		curr_sum = curr_sum - costs[DIRECTIONS[line[i]], DIRECTIONS['W']] + costs[DIRECTIONS[line[i]], DIRECTIONS['E']]
		if min_sum > curr_sum:
			min_sum = curr_sum
	print(min_sum)


for t in range(int(input())):
	l = int(input())
	p = input()
	(x, y) = map(int, input().split())
	n = [0] * l
	s = [0] * l
	e = [0] * l
	w = [0] * l
	a = 0
	b = 0
	c = 0
	d = 0
	for i in range(l):
		if p[i] == 'N':
			a += 1
		elif p[i] == 'S':
			b += 1
		elif p[i] == 'E':
			c += 1
		elif p[i] == 'W':
			d += 1
		n[i] = a
		s[i] = b
		e[i] = c
		w[i] = d
	m = min(n[-1] * min(x, 3 * y) + w[-1] * min(2 * x, 2 * y) + s[-1] * min(3 * x, y), n[-1] * min(3 * x, y) + s[-1] * min(x, 3 * y) + e[-1] * min(2 * x, 2 * y))
	for i in range(l):
		u = n[i] * min(x, 3 * y) + w[i] * min(2 * x, 2 * y) + s[i] * min(3 * x, y)
		v = (n[-1] - n[i]) * min(3 * x, y) + (s[-1] - s[i]) * min(x, 3 * y) + (e[-1] - e[i]) * min(2 * x, 2 * y)
		m = min(m, u + v)
	print(m)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(x, y) = map(int, input().split())
	m = 0
	z = list(s)
	me = 0
	mw = 0
	a = min(x, y) * 2
	b = min(3 * x, y)
	c = min(x, 3 * y)
	d = b - c
	mw += z.count('E') * a
	me += z.count('W') * a
	mw += z.count('N') * b
	me += z.count('N') * c
	me += z.count('S') * b
	mw += z.count('S') * c
	ans = min(me, mw)
	k = mw
	for i in range(0, n):
		if z[i] == 'E':
			k -= a
		elif z[i] == 'W':
			k += a
		elif z[i] == 'N':
			k -= d
		else:
			k += d
		ans = min(ans, k)
		ans = min(ans, me + mw)
	print(ans)


t = int(input())
for i in range(t):
	N = int(input())
	s = str(input())
	(x, y) = map(int, input().split())
	a = min(x, 3 * y)
	b = min(y, 3 * x)
	c = min(x, y)
	east = list()
	west = list()
	min_ene = 0
	for i in range(len(s)):
		if s[i] == 'N':
			east.append(a)
			west.append(b)
		elif s[i] == 'S':
			east.append(b)
			west.append(a)
		elif s[i] == 'E':
			east.append(0)
			west.append(2 * c)
		elif s[i] == 'W':
			east.append(2 * c)
			west.append(0)
	f = sum(west)
	k = [f]
	minimum = f
	for i in range(N):
		f = f - west[i] + east[i]
		k.append(f)
		if f < minimum:
			minimum = f
	print(minimum)


def cost(val, x, y, desired):
	if val == 'N':
		if desired == 'W':
			return min(y, x * 3)
		else:
			return min(x, y * 3)
	elif val == 'S':
		if desired == 'W':
			return min(x, y * 3)
		else:
			return min(y, x * 3)
	elif val == 'E':
		if desired == 'W':
			return 2 * min(x, y)
		else:
			return 0
	elif desired == 'W':
		return 0
	else:
		return 2 * min(x, y)
t = int(input())
for xyz in range(t):
	n = int(input())
	s = input()
	(x, y) = list(map(int, input().split()))
	alle = 0
	allw = 0
	for i in s:
		alle += cost(i, x, y, 'E')
		allw += cost(i, x, y, 'W')
	mincost = min(alle, allw)
	allee = alle
	for i in range(n - 1, 0, -1):
		allee = allee - cost(s[i], x, y, 'E') + cost(s[i], x, y, 'W')
		mincost = min(mincost, allee)
	allww = allw
	for i in range(0, n - 1):
		allww = allww - cost(s[i], x, y, 'W') + cost(s[i], x, y, 'E')
		mincost = min(mincost, allww)
	print(mincost)


T = int(input())
for t in range(T):
	n = int(input())
	directions = input()
	(cost_turn_cw, cost_turn_ccw) = [int(x) for x in input().split()]
	cost_to_face_left = []
	cost_to_face_right = []
	for direction in directions:
		if direction == 'E':
			cost_to_face_right += [0]
			cost_to_face_left += [2 * min(cost_turn_ccw, cost_turn_cw)]
		elif direction == 'N':
			cost_to_face_right += [min(cost_turn_cw, 3 * cost_turn_ccw)]
			cost_to_face_left += [min(cost_turn_ccw, 3 * cost_turn_cw)]
		elif direction == 'W':
			cost_to_face_right += [2 * min(cost_turn_cw, cost_turn_ccw)]
			cost_to_face_left += [0]
		else:
			cost_to_face_left += [min(cost_turn_cw, 3 * cost_turn_ccw)]
			cost_to_face_right += [min(cost_turn_ccw, 3 * cost_turn_cw)]
	cost = sum(cost_to_face_left)
	ans = cost
	for i in range(n):
		cost += cost_to_face_right[i] - cost_to_face_left[i]
		ans = min(ans, cost)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	(x, y) = map(int, input().split())
	arr = [0]
	sum = 0
	for i in range(n):
		if s[i] == 'N':
			sum += min(x, 3 * y)
			arr.append(sum)
		elif s[i] == 'W':
			sum += min(2 * x, 2 * y)
			arr.append(sum)
		elif s[i] == 'S':
			sum += min(3 * x, y)
			arr.append(sum)
		elif s[i] == 'E':
			arr.append(sum)
	sum = 0
	for i in range(n - 1, -1, -1):
		if s[i] == 'N':
			sum += min(3 * x, y)
			arr[i] += sum
		elif s[i] == 'W':
			arr[i] += sum
		elif s[i] == 'S':
			sum += min(x, 3 * y)
			arr[i] += sum
		elif s[i] == 'E':
			sum += min(x * 2, y * 2)
			arr[i] += sum
	print(min(arr))


def cost_E_W(current, x, y):
	dist = {'NE': 1, 'NW': 3, 'EE': 0, 'EW': 2, 'SE': 3, 'SW': 1, 'WW': 0, 'WE': 2}
	ef = dist[current + 'E']
	face_east = min(x * ef, y * (4 - ef))
	wf = dist[current + 'W']
	face_west = min(x * wf, y * (4 - wf))
	return [face_east, face_west]
for _ in range(int(input())):
	n = int(input())
	titans = [i for i in input()]
	(x, y) = map(int, input().split(' '))
	east = [0] * n
	west = [0] * n
	(east[0], west[0]) = cost_E_W(titans[0], x, y)
	for (k, i) in enumerate(titans[1:]):
		(e, w) = cost_E_W(i, x, y)
		east[k + 1] = east[k] + e
		west[k + 1] = west[k] + w
	west_max = west[-1]
	ans = 10 ** 12
	ans = min(east[-1], west[-1])
	for i in range(n):
		ans = min(ans, east[i] + west_max - west[i])
	print(ans)


from sys import stdin, stdout
from os import path

def debug(x):
	pass

def cost_E_W(current, x, y):
	dist = {'NE': 1, 'NW': 3, 'EE': 0, 'EW': 2, 'SE': 3, 'SW': 1, 'WW': 0, 'WE': 2}
	ef = dist[current + 'E']
	face_east = min(x * ef, y * (4 - ef))
	wf = dist[current + 'W']
	face_west = min(x * wf, y * (4 - wf))
	return [face_east, face_west]

def solve():
	for _ in range(int(input())):
		n = int(input())
		titans = [i for i in input()]
		(x, y) = map(int, input().split(' '))
		east = [0] * n
		west = [0] * n
		(east[0], west[0]) = cost_E_W(titans[0], x, y)
		for (k, i) in enumerate(titans[1:]):
			(e, w) = cost_E_W(i, x, y)
			east[k + 1] = east[k] + e
			west[k + 1] = west[k] + w
		west_max = west[-1]
		ans = 10 ** 12
		ans = min(east[-1], west[-1])
		for i in range(n):
			ans = min(ans, east[i] + west_max - west[i])
		print(ans)

def main():
	solve()
main()


def check(n, string, a, b):
	arr = [0]
	add = 0
	for i in range(n):
		if string[i] is 'N':
			add += min(a, 3 * b)
			arr.append(add)
		elif string[i] is 'W':
			add += min(2 * a, 2 * b)
			arr.append(add)
		elif string[i] is 'S':
			add += min(3 * a, b)
			arr.append(add)
		elif string[i] is 'E':
			arr.append(add)
	add = 0
	for i in range(n - 1, -1, -1):
		if string[i] is 'N':
			add += min(3 * a, b)
			arr[i] += add
		elif string[i] is 'E':
			add += min(2 * a, 2 * b)
			arr[i] += add
		elif string[i] is 'S':
			add += min(a, 3 * b)
			arr[i] += add
		elif string[i] is 'W':
			arr[i] += add
	return min(arr)
for _ in range(int(input())):
	n = int(input())
	string = input()
	(a, b) = map(int, input().split())
	ans = check(n, string, a, b)
	print(ans)


for i in range(int(input())):
	n = int(input())
	direction = input()[:n]
	(x, y) = map(int, input().split())
	energy = 0
	for item in direction:
		if item == 'E':
			energy += min(x * 2, y * 2)
		elif item == 'W':
			energy += 0
		elif item == 'N':
			energy += min(y, 3 * x)
		elif item == 'S':
			energy += min(3 * y, x)
	ans = energy
	for item in direction:
		if item == 'E':
			energy = energy - min(x * 2, y * 2) + 0
		elif item == 'W':
			energy = energy - 0 + min(2 * y, 2 * x)
		elif item == 'N':
			energy = energy - min(y, 3 * x) + min(x, 3 * y)
		elif item == 'S':
			energy = energy - min(3 * y, x) + min(3 * x, y)
		ans = min(ans, energy)
	print(ans)


import math
for m in range(int(input())):
	n = int(input())
	s = input()
	(x, y) = list(map(int, input().split()))
	east = []
	west = []
	esum = 0
	wsum = 0

	def app(num1, num2, east):
		ceast = x * num1
		aeast = num2 * y
		eastmin = min(ceast, aeast)
		east.append(eastmin)
	for i in range(n):
		if s[i] == 'N':
			app(1, 3, east)
			app(3, 1, west)
		elif s[i] == 'S':
			app(3, 1, east)
			app(1, 3, west)
		elif s[i] == 'W':
			app(2, 2, east)
			app(0, 0, west)
		elif s[i] == 'E':
			app(0, 0, east)
			app(2, 2, west)
		esum += east[i]
		wsum += west[i]
	wone = wsum
	eone = 0
	ans = wsum
	for i in range(n):
		eone += east[i]
		wone -= west[i]
		total = eone + wone
		ans = min(ans, total)
	print(min(wsum, esum, ans))


for _ in range(int(input())):
	n = int(input())
	s = input()
	(x, y) = map(int, input().split())
	total = 0
	a = [0]
	for i in range(n):
		if s[i] == 'N':
			total += min(x, 3 * y)
			a.append(total)
		elif s[i] == 'S':
			total += min(3 * x, y)
			a.append(total)
		elif s[i] == 'E':
			a.append(total)
		elif s[i] == 'W':
			total += min(2 * x, 2 * y)
			a.append(total)
	total = 0
	for i in reversed(range(n)):
		if s[i] == 'S':
			total += min(x, 3 * y)
			a[i] += total
		elif s[i] == 'N':
			total += min(3 * x, y)
			a[i] += total
		elif s[i] == 'W':
			a[i] += total
		elif s[i] == 'E':
			total += min(2 * x, 2 * y)
			a[i] += total
	print(min(a))


def theRumbling(N, D, X, Y):
	E = []
	W = []
	for i in range(N):
		if D[i] == 'S':
			W.append(min(X, 3 * Y))
			E.append(min(Y, 3 * X))
		elif D[i] == 'N':
			W.append(min(Y, 3 * X))
			E.append(min(X, 3 * Y))
		elif D[i] == 'W':
			W.append(0)
			E.append(min(2 * X, 2 * Y))
		else:
			E.append(0)
			W.append(min(2 * X, 2 * Y))
	ans = sum(W)
	m = sum(W)
	for i in range(1, N + 1):
		m += E[i - 1] - W[i - 1]
		ans = min(ans, m)
	return ans
for _ in range(int(input())):
	N = int(input())
	D = input()
	(X, Y) = map(int, input().split())
	print(theRumbling(N, D, X, Y))


def distance(ch, x, y):
	if ch == 'E':
		east = 0
		west = min(2 * x, 2 * y)
	elif ch == 'W':
		east = min(2 * x, 2 * y)
		west = 0
	elif ch == 'N':
		east = min(x, 3 * y)
		west = min(y, 3 * x)
	else:
		east = min(y, 3 * x)
		west = min(x, 3 * y)
	return (east, west)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(input())
	(x, y) = map(int, input().split())
	dist = [distance(arr[i], x, y) for i in range(n)]
	prefix_east = [0]
	prefix_west = [0]
	for i in range(n):
		prefix_east.append(prefix_east[-1] + dist[i][0])
		prefix_west.append(prefix_west[-1] + dist[n - 1 - i][1])
	prefix_west = prefix_west[::-1]
	print(min((prefix_west[i] + prefix_east[i] for i in range(n + 1))))


for i in range(int(input())):
	n = int(input())
	s = input()
	(x, y) = map(int, input().split())

	def turne(s, x, y):
		if s == 'E':
			return 0
		if s == 'N':
			return min(x, 3 * y)
		if s == 'S':
			return min(y, 3 * x)
		else:
			return min(2 * y, 2 * x)

	def turnw(s, x, y):
		if s == 'W':
			return 0
		if s == 'N':
			return min(y, 3 * x)
		if s == 'S':
			return min(x, 3 * y)
		else:
			return min(2 * y, 2 * x)
	lis = [0]
	su = 0
	for i in range(len(s)):
		su += turne(s[i], x, y)
		lis.append(su)
	su = 0
	for i in range(len(s), 0, -1):
		su += turnw(s[i - 1], x, y)
		lis[i - 1] += su
	print(min(lis))


from itertools import combinations
for _ in range(int(input())):
	n = int(input())
	soldger = list(input())
	(clock, anitClock) = list(map(int, input().split()))
	east = []
	west = []
	for i in soldger:
		if i == 'N':
			west.append(min(anitClock, 3 * clock))
			east.append(min(clock, 3 * anitClock))
		elif i == 'S':
			east.append(min(anitClock, 3 * clock))
			west.append(min(clock, 3 * anitClock))
		elif i == 'E':
			east.append(0)
			west.append(2 * min(clock, anitClock))
		elif i == 'W':
			west.append(0)
			east.append(2 * min(clock, anitClock))
	x = 0
	y = 0
	LtoR_east = [0]
	RtoL_west = []
	for idx in range(n):
		x += east[idx]
		y += west[n - idx - 1]
		LtoR_east.append(x)
		RtoL_west.append(y)
	RtoL_west = RtoL_west[::-1]
	RtoL_west.append(0)
	ans = float('inf')
	for i in range(n + 1):
		ans = min(ans, LtoR_east[i] + RtoL_west[i])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	(x, y) = map(int, input().split())
	left = [0] * n
	right = [0] * n
	for i in range(n):
		if s[i] == 'N':
			left[i] = min(x * 3, y)
			right[i] = min(x, y * 3)
		elif s[i] == 'S':
			left[i] = min(x, y * 3)
			right[i] = min(x * 3, y)
		elif s[i] == 'E':
			left[i] = min(x * 2, y * 2)
		else:
			right[i] = min(x * 2, y * 2)
	for i in range(1, n):
		right[i] += right[i - 1]
	for i in range(n - 2, -1, -1):
		left[i] += left[i + 1]
	ans = float('inf')
	ans = min(right[-1], left[0])
	for i in range(n - 1):
		ans = min(ans, right[i] + left[i + 1])
	print(ans)


k = int(input())
for x in range(0, k):
	n = input()
	string = str(input())
	a1 = input().split()
	clock = int(a1[0])
	anticlock = int(a1[1])
	toeast = []
	towest = []
	for i in string:
		if i == 'E':
			toeast.append(0)
		elif i == 'S':
			toeast.append(min(anticlock, 3 * clock))
		elif i == 'N':
			toeast.append(min(clock, 3 * anticlock))
		elif i == 'W':
			toeast.append(min(clock * 2, anticlock * 2))
	for i in string:
		if i == 'W':
			towest.append(0)
		elif i == 'S':
			towest.append(min(clock, 3 * anticlock))
		elif i == 'N':
			towest.append(min(anticlock, 3 * clock))
		elif i == 'E':
			towest.append(min(2 * anticlock, 2 * clock))
	minn = sum(towest)
	sumk = sum(towest)
	for (i, j) in enumerate(toeast):
		sumk += toeast[i] - towest[i]
		minn = min(sumk, minn)
	print(minn)


t = int(input())
for ii in range(t):
	n = int(input())
	s = input().rstrip()
	(x, y) = list(map(int, input().rstrip().split()))
	west = [0] * n
	east = [0] * n
	for i in range(n):
		if s[i] == 'W':
			east[i] = min(2 * x, 2 * y)
		if s[i] == 'E':
			west[i] = min(2 * x, 2 * y)
		if s[i] == 'S':
			east[i] = min(3 * x, y)
			west[i] = min(x, 3 * y)
		if s[i] == 'N':
			east[i] = min(x, 3 * y)
			west[i] = min(3 * x, y)
	for i in range(1, n):
		east[i] += east[i - 1]
	for i in range(n - 2, -1, -1):
		west[i] += west[i + 1]
	final = float('inf')
	final = min(east[-1], west[0])
	for i in range(n - 1):
		final = min(final, east[i] + west[i + 1])
	print(final)


def calc(ini, fin, x, y):
	if ini == fin:
		return 0
	if ini == 'W' and fin == 'E' or (ini == 'E' and fin == 'W'):
		return min(2 * x, 2 * y)
	if ini == 'N' and fin == 'E' or (ini == 'S' and fin == 'W'):
		return min(x, 3 * y)
	return min(3 * x, y)
for _ in range(int(input())):
	n = int(input())
	titans = input()
	(x, y) = map(int, input().split())
	leftTurn = [calc(titans[0], 'W', x, y)]
	for i in range(1, n):
		leftTurn.append(leftTurn[-1] + calc(titans[i], 'W', x, y))
	rightTurn = [calc(titans[0], 'E', x, y)]
	for i in range(1, n):
		rightTurn.append(rightTurn[-1] + calc(titans[i], 'E', x, y))
	eren = 0
	m = leftTurn[-1]
	while eren < n:
		energy = leftTurn[n - 1] - leftTurn[eren] + rightTurn[eren]
		m = min(m, energy)
		eren += 1
	print(m)


def get_min(n, s, x, y):
	l = []
	r = []
	for i in s:
		if i == 'N':
			l.append(min(y, 3 * x))
			r.append(min(x, 3 * y))
		elif i == 'S':
			l.append(min(x, 3 * y))
			r.append(min(y, 3 * x))
		elif i == 'E':
			l.append(min(2 * x, 2 * y))
			r.append(0)
		else:
			l.append(0)
			r.append(min(2 * x, 2 * y))
	lp = [0]
	rp = [0]
	ls = 0
	rs = 0
	for i in l[::-1]:
		ls += i
		lp.append(ls)
	for i in r:
		rs += i
		rp.append(rs)
	lp = lp[::-1]
	ans = float('inf')
	for i in range(len(lp)):
		ans = min(ans, lp[i] + rp[i])
	print(ans)
for i in range(int(input())):
	n = int(input())
	s = input()
	(x, y) = map(int, input().split())
	get_min(n, s, x, y)


for i in range(int(input())):
	ui = int(input())
	s = str(input())
	(x, y) = map(int, input().split())
	ans = []
	dire = {'N': 0, 'S': 0, 'E': 0, 'W': 0}
	for j in s:
		dire[j] += 1
	t = min(x, y)
	if x > 3 * y:
		a = 3 * y
	else:
		a = x
	if y > 3 * x:
		b = 3 * x
	else:
		b = y
	dire2 = {'N': 0, 'S': 0, 'E': 0, 'W': 0}
	for k in s:
		ans.append(dire2['N'] * a + dire2['S'] * b + dire2['W'] * 2 * t + dire['N'] * b + dire['S'] * a + dire['E'] * 2 * t)
		dire2[k] += 1
		dire[k] -= 1
	ans.append(dire2['N'] * a + dire2['S'] * b + dire2['W'] * 2 * t + dire['N'] * b + dire['S'] * a + dire['E'] * 2 * t)
	print(min(ans))


test = int(input())
for i in range(0, test):
	n = int(input())
	s = input()
	(x, y) = map(int, input().split())
	west = []
	east = []
	for i in s:
		if i == 'E':
			west.append(2 * min(x, y))
			east.append(0)
		elif i == 'N':
			west.append(min(y, 3 * x))
			east.append(min(x, 3 * y))
		elif i == 'S':
			west.append(min(x, 3 * y))
			east.append(min(y, 3 * x))
		else:
			west.append(0)
			east.append(2 * min(x, y))
	find = []
	g = sum(west)
	mini = g
	k = [g]
	for i in range(0, n):
		g = g - west[i] + east[i]
		k.append(g)
		if g < mini:
			mini = g
	print(mini)


import sys
for tc in range(int(input())):
	n = int(input())
	ls = list(input())
	lk = list(map(int, input().split()))
	x = lk[0]
	y = lk[1]
	nums = []
	pre = []
	dis = {'E': 0, 'W': 1, 'N': 2, 'S': 3}
	lp = []
	lp.append('#')
	te = tw = tn = ts = 0
	for g in ls:
		lp.append(g)
		lp.append('#')
		if g == 'S':
			ts += 1
		if g == 'N':
			tn += 1
		if g == 'E':
			te += 1
		if g == 'W':
			tw += 1
	ce = cw = cn = cs = 0
	mincost = sys.maxsize
	for g in range(len(lp)):
		if lp[g] == 'S':
			cs += 1
		if lp[g] == 'N':
			cn += 1
		if lp[g] == 'E':
			ce += 1
		if lp[g] == 'W':
			cw += 1
		if lp[g] == '#':
			if g == 0:
				coste = min(te * x * 2, te * y * 2)
				costn = min(tn * x * 3, tn * y)
				costs = min(ts * x, ts * y * 3)
				mincost = min(mincost, coste + costn + costs)
			elif g == len(lp) - 1:
				costw = min(cw * x * 2, cw * y * 2)
				costn = min(cn * x, cn * y * 3)
				costs = min(cs * x * 3, cs * y)
				mincost = min(mincost, costw + costn + costs)
			else:
				cost0e = min((te - ce) * x * 2, (te - ce) * y * 2)
				cost0n = min((tn - cn) * x * 3, (tn - cn) * y)
				cost0s = min((ts - cs) * x, (ts - cs) * y * 3)
				cost1w = min(cw * x * 2, cw * y * 2)
				cost1n = min(cn * x, cn * y * 3)
				cost1s = min(cs * x * 3, cs * y)
				mincost = min(mincost, cost1w + cost1n + cost1s + cost0e + cost0n + cost0s)
	print(mincost)


for _ in range(int(input())):
	n = int(input())
	a = input()
	(x, y) = list(map(int, input().split(' ')))
	(r, l) = ([0], [0])
	for i in a:
		if i == 'N':
			r.append(min(x, y * 3))
			l.append(min(y, x * 3))
		if i == 'S':
			r.append(min(y, x * 3))
			l.append(min(x, y * 3))
		if i == 'E':
			r.append(0)
			l.append(min(x * 2, y * 2))
		if i == 'W':
			r.append(min(2 * x, 2 * y))
			l.append(0)
	for i in range(1, n + 1):
		l[i] = l[i] + l[i - 1]
		r[i] = r[i] + r[i - 1]
	zzans = 1e+18 + 7
	for i in range(n + 1):
		lans = l[n] - l[i]
		rans = r[i]
		zzans = min(zzans, lans + rans)
	print(zzans)


def solve(N, S, X, Y):
	(east_align, west_align) = ([0] * N, [0] * N)
	cost = {'EE': 0, 'WW': 0, 'NE': min(X, 3 * Y), 'NW': min(Y, 3 * X), 'SE': min(Y, 3 * X), 'SW': min(X, 3 * Y), 'WE': 2 * min(X, Y), 'EW': 2 * min(X, Y)}
	for i in range(N):
		east_align[i] = cost[S[i] + 'E']
		west_align[i] = cost[S[i] + 'W']
	cost = sum(west_align)
	min_cost = cost
	for i in range(N):
		cost = cost + east_align[i] - west_align[i]
		if cost < min_cost:
			min_cost = cost
	return min_cost
T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	(X, Y) = list(map(int, input().split()))
	print(solve(N, S, X, Y))


def cost(a, b):
	if a == 'W':
		if b == 'W':
			return 0
		elif b == 'N':
			return 1
		elif b == 'E':
			return 2
		elif b == 'S':
			return 3
	if a == 'E':
		if b == 'E':
			return 0
		elif b == 'N':
			return 3
		elif b == 'W':
			return 2
		elif b == 'S':
			return 1
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	ip = input().split()
	(x, y) = [int(i) for i in ip]
	en = 0
	for i in s:
		en += min(cost('W', i) * y, (4 - cost('W', i)) * x)
	newen = en + 0
	for i in s:
		newen -= min(cost('W', i) * y, (4 - cost('W', i)) * x)
		newen += min(cost('E', i) * y, (4 - cost('E', i)) * x)
		if newen < en:
			en = newen
	print(en)


def calcmin(n, e, w, s):
	ans = 0
	ans += min(n * x, n * y * 3)
	ans += min(w * 2 * x, w * y * 2)
	ans += min(s * x * 3, s * y)
	return ans

def calcmin1(n, e, w, s):
	ans = 0
	ans += min(n * x * 3, n * y)
	ans += min(e * 2 * x, e * y * 2)
	ans += min(s * x, s * y * 3)
	return ans
t = int(input())
for jj in range(t):
	nn = int(input())
	a = list(input())
	(x, y) = map(int, input().split())
	(e, w, n, s) = (0, 0, 0, 0)
	(e1, w1, n1, s1) = (a.count('E'), a.count('W'), a.count('N'), a.count('S'))
	ans = float('inf')
	for i in range(nn):
		ans = min(calcmin(n, e, w, s) + calcmin1(n1, e1, w1, s1), ans)
		if a[i] == 'S':
			s += 1
			s1 -= 1
		elif a[i] == 'W':
			w += 1
			w1 -= 1
		elif a[i] == 'E':
			e += 1
			e1 -= 1
		elif a[i] == 'N':
			n += 1
			n1 -= 1
	ans = min(calcmin(n, e, w, s) + calcmin1(n1, e1, w1, s1), ans)
	print(ans)


T = int(input())
for i in range(T):
	clockwise = {'W': (0, 2), 'N': (3, 1), 'E': (2, 0), 'S': (1, 3)}
	anti_clockwise = {'W': (0, 2), 'N': (1, 3), 'E': (2, 0), 'S': (3, 1)}
	N = int(input())
	directions = input()
	(X, Y) = map(int, input().split())
	base_energy = 0
	for direction in directions:
		base_energy += min(clockwise[direction][0] * X, anti_clockwise[direction][0] * Y)
	min_energy = base_energy
	enrg = base_energy
	for direction in directions:
		enrg -= min(clockwise[direction][0] * X, anti_clockwise[direction][0] * Y)
		enrg += min(clockwise[direction][1] * X, anti_clockwise[direction][1] * Y)
		if enrg < min_energy:
			min_energy = enrg
	print(min_energy)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	s = input()
	(x, y) = map(int, input().split())
	e = {'N': [min(y, 3 * x), min(3 * y, x)], 'E': [2 * min(x, y), 0], 'S': [min(x, 3 * y), min(3 * x, y)], 'W': [0, 2 * min(x, y)]}
	c = Counter(s)
	curr = 0
	for d in ('N', 'S', 'E', 'W'):
		curr += c[d] * e[d][0]
	res = curr
	for i in range(len(s)):
		curr = curr - e[s[i]][0] + e[s[i]][1]
		res = min(res, curr)
	print(res)


import math, os, io, heapq
from sys import stdin, stdout
from collections import Counter, deque, defaultdict
from itertools import product
import bisect

def getList(method=int):
	return list(map(method, input().split()))

def getInt():
	return int(input())

def solve():
	n = getInt()
	s = input()
	(x, y) = getList()
	dcost = dirChangeCost(x, y)
	(wpref, epref) = ([0] * n, [0] * n)
	(wpref[0], epref[0]) = (dcost[s[0]]['W'], dcost[s[0]]['E'])
	for i in range(1, n):
		wpref[i] = wpref[i - 1] + dcost[s[i]]['W']
		epref[i] = epref[i - 1] + dcost[s[i]]['E']
	ans = min(wpref[-1], epref[-1])
	for i in range(0, n - 1):
		ans = min(ans, epref[i] + wpref[-1] - wpref[i])
	print(ans)

def dirChangeCost(x, y):
	mp = defaultdict(dict)
	(mp['N']['W'], mp['N']['E']) = (min(y, 3 * x), min(x, 3 * y))
	(mp['S']['W'], mp['S']['E']) = (min(x, 3 * y), min(y, 3 * x))
	(mp['W']['W'], mp['W']['E']) = (0, 2 * min(x, y))
	(mp['E']['W'], mp['E']['E']) = (2 * min(x, y), 0)
	return mp
for _ in range(getInt()):
	solve()


def func(i, X, Y):
	if i == 'N':
		return min(X * 3, Y)
	elif i == 'E':
		return min(X * 2, Y * 2)
	elif i == 'W':
		return 0
	else:
		return min(X * 1, Y * 3)

def func2(i, X, Y):
	if i == 'N':
		return min(X * 1, Y * 3)
	elif i == 'E':
		return 0
	elif i == 'W':
		return min(X * 2, Y * 2)
	else:
		return min(X * 3, Y * 1)
for t in range(int(input())):
	N = int(input())
	S = list(input())
	(X, Y) = map(int, input().split())
	(W, E) = ([], [])
	for i in S:
		W.append(func(i, X, Y))
	for i in S:
		E.append(func2(i, X, Y))
	ans = min(sum(E), sum(W))
	suf = []
	for i in range(len(W) - 1, -1, -1):
		if not suf:
			suf.append(W[i])
		else:
			suf.append(W[i] + suf[-1])
	suf = suf[::-1]
	sm = 0
	for i in range(N - 1):
		sm += E[i]
		ans = min(sm + suf[i + 1], ans)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	(x, y) = map(int, input().split())
	li = []
	E = [min(x, 3 * y), 0, min(3 * x, y), min(2 * x, 2 * y)]
	W = [min(3 * x, y), min(2 * x, 2 * y), min(x, 3 * y), 0]
	data = {'N': 0, 'E': 1, 'S': 2, 'W': 3}
	for i in s:
		li.append([E[data[i]], W[data[i]]])
	res = sum([i[1] for i in li])
	mini = res
	for i in li:
		res = res - i[1] + i[0]
		mini = min(res, mini)
	print(mini)


def min_energy(p):
	if p == 'N':
		return (min(x, 3 * y), min(3 * x, y))
	elif p == 'E':
		return (0, min(2 * x, 2 * y))
	elif p == 'S':
		return (min(3 * x, y), min(x, 3 * y))
	else:
		return (min(2 * x, 2 * y), 0)
t = int(input())
for _ in range(t):
	n = int(input())
	q = list(input())
	a = []
	(x, y) = map(int, input().split())
	for p in q:
		(e, w) = min_energy(p)
		a.append([e, w])
	for i in range(1, n):
		a[i][0] += a[i - 1][0]
	for i in range(n - 2, -1, -1):
		a[i][1] += a[i + 1][1]
	b = min(a[0][1], a[-1][0])
	for i in range(n - 1):
		b = min(b, a[i][0] + a[i + 1][1])
	print(b)


T = int(input())
for i in range(T):
	N = int(input())
	a = input()
	[X, Y] = [int(k) for k in input().split()]
	r = []
	q = 0
	for j in range(N):
		if a[j] == 'S':
			p = min(3 * X, Y)
		if a[j] == 'W':
			p = min(2 * X, 2 * Y)
		if a[j] == 'N':
			p = min(X, 3 * Y)
		if a[j] == 'E':
			p = 0
		q = q + p
		r.append(q)
	l = [0] * N
	q = 0
	for j in range(N - 1, -1, -1):
		if a[j] == 'S':
			p = min(X, 3 * Y)
		if a[j] == 'W':
			p = 0
		if a[j] == 'N':
			p = min(3 * X, Y)
		if a[j] == 'E':
			p = min(2 * X, 2 * Y)
		q = q + p
		l[j] = q
	l = l + [0]
	r = [0] + r
	mx = l[0] + r[0]
	for j in range(N + 1):
		p = l[j] + r[j]
		if p < mx:
			mx = p
	print(mx)


mod = 1000000007
from math import factorial, ceil, pow, sqrt, floor, gcd
from sys import stdin, stdout
from collections import defaultdict, Counter, deque
for _ in range(int(stdin.readline())):
	r = int(stdin.readline())
	s = stdin.readline().strip('\n')
	(x, y) = map(int, stdin.readline().split())
	east = []
	west = []
	e = f = 0
	for i in range(r):
		m = n = 0
		if s[i] == 'W':
			n = min(2 * x, 2 * y)
			m = 0
		elif s[i] == 'E':
			n = 0
			m = min(2 * x, 2 * y)
		elif s[i] == 'N':
			n = min(x, 3 * y)
			m = min(y, 3 * x)
		else:
			n = min(3 * x, y)
			m = min(x, 3 * y)
		e += m
		f += n
		west.append(m)
		east.append(f)
	f = 0
	p = []
	for ele in west[::-1]:
		f += ele
		p.append(f)
	ans = p[-1]
	for i in range(1, r):
		ans = min(ans, east[i - 1] + p[r - i - 1])
	ans = min(ans, east[-1])
	print(ans)


def enToFaceEast(d, X, Y):
	if d == 'E':
		return 0
	elif d == 'N':
		return min(X * 1, Y * 3)
	elif d == 'W':
		return min(X * 2, Y * 2)
	else:
		return min(X * 3, Y * 1)

def enToFaceWest(d, X, Y):
	if d == 'E':
		return min(X * 2, Y * 2)
	elif d == 'N':
		return min(X * 3, Y * 1)
	elif d == 'W':
		return 0
	else:
		return min(X * 1, Y * 3)
T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	(X, Y) = map(int, input().split())
	E = 0
	for d in S:
		E += enToFaceWest(d, X, Y)
	(minE, altE) = (E, E)
	for d in S:
		altE = E - enToFaceWest(d, X, Y) + enToFaceEast(d, X, Y)
		if altE < minE:
			minE = altE
		E = altE
	print(minE)


import sys, io, os, time
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect, math, heapq
alphabet = 'abcdefghijklmnopqrstuvwxyz'

def ceil(num, denom):
	return (num + denom - 1) // denom
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	(x, y) = map(int, input().split())
	to_east = []
	to_west = []
	for i in range(n):
		cost = 0
		if s[i] == 'E':
			cost = 0
		elif s[i] == 'W':
			cost = min(2 * x, 2 * y)
		elif s[i] == 'N':
			cost = min(x, 3 * y)
		elif s[i] == 'S':
			cost = min(3 * x, y)
		to_east.append(cost)
	for i in range(n):
		cost = 0
		if s[i] == 'W':
			cost = 0
		elif s[i] == 'E':
			cost = min(2 * x, 2 * y)
		elif s[i] == 'S':
			cost = min(x, 3 * y)
		elif s[i] == 'N':
			cost = min(3 * x, y)
		to_west.append(cost)
	prefix1 = [0]
	prefix2 = [0]
	for i in range(n):
		prefix1.append(prefix1[-1] + to_east[i])
		prefix2.append(prefix2[-1] + to_west[i])
	ans = min(prefix1[-1], prefix2[-1])
	for i in range(n):
		ans = min(ans, prefix1[i + 1] + prefix2[-1] - prefix2[i + 1])
	print(ans)


import bisect
import math
import sys
sys.setrecursionlimit(10 ** 6)
for t in range(int(input())):
	n = int(input())
	s = input()
	(x, y) = map(int, input().split())
	(east, west) = ([], [])
	dict = {'n': [3, 1], 'e': [2, 0], 's': [1, 3], 'w': [0, 2]}
	for charr in s:
		west.append(min(dict[charr.lower()][0] * x, (4 - dict[charr.lower()][0]) * y))
	westSum = [-1] * n
	ws = 0
	for i in range(n):
		ws += west[n - 1 - i]
		westSum[n - 1 - i] = ws
	for charr in s:
		east.append(min(dict[charr.lower()][1] * x, (4 - dict[charr.lower()][1]) * y))
	eastSum = [-1] * n
	ns = 0
	for i in range(n):
		ns += east[i]
		eastSum[i] = ns
	ans = sys.maxsize
	for i in range(len(s) + 1):
		if i == 0:
			ans = min(ans, westSum[i])
		elif i == n:
			ans = min(ans, eastSum[i - 1])
		else:
			ans = min(ans, westSum[i] + eastSum[i - 1])
	print(ans)


from collections import deque
T = int(input())
for i in range(T):
	n = int(input())
	s = str(input())
	(x, y) = list(map(int, input().split()))
	l = deque()
	l.append(0)
	for i in range(len(s)):
		if s[i] == 'N':
			l.append(l[-1] + min(3 * y, x))
		if s[i] == 'S':
			l.append(l[-1] + min(y, 3 * x))
		if s[i] == 'W':
			l.append(l[-1] + min(2 * y, 2 * x))
		if s[i] == 'E':
			l.append(l[-1])
	res = l[-1]
	sums = 0
	i = n - 1
	while i > -1:
		if s[i] == 'N':
			sums += min(y, 3 * x)
		elif s[i] == 'S':
			sums += min(3 * y, x)
		elif s[i] == 'E':
			sums += min(2 * x, 2 * y)
		res = min(res, sums + l[i])
		i -= 1
	print(min(res, sums))


from collections import defaultdict
import math

def ncr(n, m):
	return math.factorial(n) // (math.factorial(m) * math.factorial(n - m))

def gcd(n, m):
	return math.gcd(n, m)
t = int(input())
for t1 in range(0, t):
	n = int(input())
	s = input()
	(x, y) = map(int, input().split())
	e = []
	for i in range(0, n):
		if s[i] == 'N':
			e.append(min(x, y * 3))
		elif s[i] == 'S':
			e.append(min(x * 3, y))
		elif s[i] == 'W':
			e.append(min(2 * x, 2 * y))
		else:
			e.append(0)
	w = []
	for i in range(0, n):
		if s[i] == 'N':
			w.append(min(x * 3, y))
		elif s[i] == 'S':
			w.append(min(x, y * 3))
		elif s[i] == 'E':
			w.append(min(2 * x, 2 * y))
		else:
			w.append(0)
	ef = e[:]
	for i in range(1, n):
		ef[i] += ef[i - 1]
	er = e[:]
	for i in range(n - 2, -1, -1):
		er[i] += er[i + 1]
	wf = w[:]
	for i in range(1, n):
		wf[i] += wf[i - 1]
	wr = w[:]
	for i in range(n - 2, -1, -1):
		wr[i] += wr[i + 1]
	ans = min(ef[-1], wf[-1])
	for i in range(0, n - 1):
		ans = min(ans, ef[i] + wr[i + 1])
	print(ans)


def find_east(x, clock, anti):
	if x == 'E':
		return 0
	elif x == 'S':
		if anti < clock * 3:
			return anti
		else:
			return clock * 3
	elif x == 'N':
		if anti * 3 < clock:
			return anti * 3
		else:
			return clock
	elif anti < clock:
		return anti * 2
	else:
		return clock * 2

def find_west(x, clock, anti):
	if x == 'W':
		return 0
	elif x == 'S':
		if anti * 3 < clock:
			return anti * 3
		else:
			return clock
	elif x == 'N':
		if anti < clock * 3:
			return anti
		else:
			return clock * 3
	elif anti < clock:
		return anti * 2
	else:
		return clock * 2

def solve(string, clock, anti):
	east = []
	west = []
	for x in string:
		a = find_east(x, clock, anti)
		east.append(a)
		c = find_west(x, clock, anti)
		west.append(c)
	e = 0
	w = sum(west)
	best = w
	for x in range(len(string)):
		e += east[x]
		w -= west[x]
		if e + w < best:
			best = e + w
	print(best)
test = int(input())
for _ in range(test):
	n = int(input())
	string = input()
	(clock, anti) = [int(x) for x in input().split()]
	solve(string, clock, anti)


for _ in range(int(input())):
	n = int(input())
	s = input()
	(x, y) = map(int, input().split(' '))
	curr = 0
	for i in range(n):
		if s[i] == 'S':
			curr = curr + min(x, 3 * y)
		if s[i] == 'E':
			curr = curr + min(2 * x, 2 * y)
		if s[i] == 'N':
			curr = curr + min(3 * x, y)
		if s[i] == 'W':
			curr = curr + 0
	ans = curr
	for i in range(n):
		if s[i] == 'S':
			curr = curr - min(x, 3 * y) + min(y, 3 * x)
		if s[i] == 'E':
			curr = curr - min(2 * x, 2 * y)
		if s[i] == 'N':
			curr = curr - min(3 * x, y) + min(x, 3 * y)
		if s[i] == 'W':
			curr = curr + min(2 * y, 2 * x)
		ans = min(ans, curr)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	S = list(input())
	(X, Y) = map(int, input().split())
	arr = []
	for i in range(n):
		a = [0, 0]
		if S[i] == 'S':
			a[0] = min(3 * X, Y)
			a[1] = min(X, 3 * Y)
		elif S[i] == 'N':
			a[0] = min(X, 3 * Y)
			a[1] = min(3 * X, Y)
		elif S[i] == 'W':
			a[0] = min(2 * X, 2 * Y)
			a[1] = 0
		elif S[i] == 'E':
			a[1] = min(2 * X, 2 * Y)
			a[0] = 0
		arr.append(a)
	a = 0
	b = 0
	for i in range(n):
		arr[i][0] += a
		a = arr[i][0]
		arr[n - i - 1][1] += b
		b = arr[n - i - 1][1]
	ans = min(arr[0][1], arr[-1][0])
	for i in range(n - 1):
		ans = min(ans, arr[i][0] + arr[i + 1][1])
	print(ans)


def helperRight(i, x, y):
	if i == 'N':
		return min(x, 3 * y)
	elif i == 'W':
		return min(2 * x, 2 * y)
	elif i == 'S':
		return min(3 * x, y)
	else:
		return 0

def helperLeft(i, x, y):
	if i == 'N':
		return min(3 * x, y)
	elif i == 'W':
		return 0
	elif i == 'S':
		return min(x, 3 * y)
	else:
		return min(2 * x, 2 * y)
for _ in range(int(input())):
	n = int(input())
	s = input()
	(x, y) = list(map(int, input().split()))
	left = [0] * n
	right = [0] * n
	right[0] = helperRight(s[0], x, y)
	left[n - 1] = helperLeft(s[n - 1], x, y)
	for i in range(1, n):
		right[i] = helperRight(s[i], x, y) + right[i - 1]
		left[n - i - 1] = helperLeft(s[n - i - 1], x, y) + left[n - i]
	ans = left[0]
	for i in range(n - 1):
		ans = min(ans, right[i] + left[i + 1])
	ans = min(ans, right[n - 1])
	print(ans)


from collections import Counter
import string
import math
import bisect
import sys
from fractions import Fraction

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(arrber_of_variables):
	if arrber_of_variables == 1:
		return int(sys.stdin.readline())
	if arrber_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))
testcases = vary(1)
for _ in range(testcases):
	n = vary(1)
	values = list(input())
	(clock, anticlock) = vary(2)
	east = [0] * (n + 1)
	for i in range(n):
		if values[i] == 'E':
			east[i] = east[i - 1]
		elif values[i] == 'W':
			east[i] += east[i - 1] + min(2 * clock, 2 * anticlock)
		elif values[i] == 'S':
			east[i] += east[i - 1] + min(anticlock, 3 * clock)
		else:
			east[i] += east[i - 1] + min(3 * anticlock, clock)
	west = [0] * (n + 1)
	for i in range(n):
		if values[i] == 'W':
			west[i] = west[i - 1]
		elif values[i] == 'E':
			west[i] += west[i - 1] + min(2 * clock, 2 * anticlock)
		elif values[i] == 'N':
			west[i] += west[i - 1] + min(anticlock, 3 * clock)
		else:
			west[i] += west[i - 1] + min(3 * anticlock, clock)
	ans = float('inf')
	for i in range(1, n):
		ans = min(ans, east[i - 1] + (west[n - 1] - west[i - 1]))
	print(min(ans, east[n - 1], west[n - 1]))


for _ in range(int(input())):
	N = int(input())
	S = input()
	(X, Y) = map(int, input().split())
	(to_west, to_east) = ([], [])
	directions = ['N', 'E', 'S', 'W']
	for i in range(N):
		titan = directions.index(S[i])
		clockwise_west = (3 - titan) * X
		counter_clockwise_west = (titan + 1) % 4 * Y
		clockwise_east = (1 - titan) % 4 * X
		counter_clockwise_east = (titan - 1) % 4 * Y
		west_power = min(clockwise_west, counter_clockwise_west)
		east_power = min(clockwise_east, counter_clockwise_east)
		to_west.append(west_power)
		to_east.append(east_power)
	(w, e) = (sum(to_west), 0)
	ans = w + e
	for i in range(N):
		w -= to_west[i]
		e += to_east[i]
		ans = min(ans, w + e)
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	s = str(input())
	(c, a) = map(int, input().split())
	ans = 0
	for i in range(n):
		if s[i] == 'S':
			ans += min(c, 3 * a)
		if s[i] == 'E':
			ans += min(2 * a, 2 * c)
		if s[i] == 'N':
			ans += min(3 * c, a)
	anss = ans
	for i in range(n):
		if s[i] == 'S':
			ans -= min(c, 3 * a)
			ans += min(3 * c, a)
		if s[i] == 'E':
			ans -= min(2 * a, 2 * c)
		if s[i] == 'N':
			ans -= min(3 * c, a)
			ans += min(c, 3 * a)
		if s[i] == 'W':
			ans += min(2 * c, 2 * a)
		anss = min(anss, ans)
	print(anss)


from collections import defaultdict
for i in range(int(input())):
	n = int(input())
	s = input()
	(x, y) = map(int, input().split())
	e = []
	w = []
	for j in range(n):
		te = 0
		if s[j] == 'E':
			te = 0
		elif s[j] == 'W':
			te = min(x, y) * 2
		elif s[j] == 'N':
			te = min(x, 3 * y)
		else:
			te = min(y, 3 * x)
		e.append(te)
		te = 0
		if s[j] == 'W':
			te = 0
		elif s[j] == 'E':
			te = min(x, y) * 2
		elif s[j] == 'S':
			te = min(x, 3 * y)
		else:
			te = min(y, 3 * x)
		w.append(te)
	for j in range(1, n):
		e[j] += e[j - 1]
		w[j] += w[j - 1]
	ans = min(e[-1], w[-1])
	for j in range(n):
		ce = e[j] + w[-1] - w[j]
		ans = min(ans, ce)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	(x, y) = map(int, input().split())
	ei = [0]
	wi = [0]
	e = w = 0
	for i in range(n):
		if s[i] == 'S':
			e = e + min(3 * x, y)
		elif s[i] == 'N':
			e = e + min(x, 3 * y)
		elif s[i] == 'W':
			e = e + min(2 * x, 2 * y)
		ei.append(e)
		if s[n - 1 - i] == 'S':
			w = w + min(x, 3 * y)
		elif s[n - 1 - i] == 'N':
			w = w + min(3 * x, y)
		elif s[n - 1 - i] == 'E':
			w = w + min(2 * x, 2 * y)
		wi.append(w)
	ans = w
	for i in range(n + 1):
		ans = min(ans, ei[i] + wi[n - i])
	print(ans)


from sys import stdin
input = stdin.readline

def answer():
	(prefix, suffix) = ([0] * (n + 1), [0] * (n + 2))
	for i in range(n):
		if s[i] == 'S':
			energy = min(y, 3 * x)
		elif s[i] == 'N':
			energy = min(x, 3 * y)
		elif s[i] == 'W':
			energy = min(2 * x, 2 * y)
		else:
			energy = 0
		prefix[i + 1] = prefix[i] + energy
	for i in range(n - 1, -1, -1):
		if s[i] == 'N':
			energy = min(y, 3 * x)
		elif s[i] == 'S':
			energy = min(x, 3 * y)
		elif s[i] == 'E':
			energy = min(2 * x, 2 * y)
		else:
			energy = 0
		suffix[i + 1] = suffix[i + 2] + energy
	ans = float('inf')
	for i in range(n + 1):
		ans = min(ans, prefix[i] + suffix[i + 1])
	return ans
for T in range(int(input())):
	n = int(input())
	s = input().strip()
	(x, y) = map(int, input().split())
	print(answer())


from sys import stdin, stdout
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
for _ in range(nmbr()):
	n = nmbr()
	s = input()
	(clock, anti) = lst()
	east = {'E': 0}
	east['W'] = 2 * min(clock, anti)
	east['N'] = min(clock, 3 * anti)
	east['S'] = min(3 * clock, anti)
	west = {'W': 0}
	west['E'] = 2 * min(clock, anti)
	west['N'] = min(3 * clock, anti)
	west['S'] = min(clock, 3 * anti)
	pre = [0] * n
	pre[0] = east[s[0]]
	for i in range(1, n):
		pre[i] = pre[i - 1] + east[s[i]]
	suf = [0] * n
	suf[n - 1] = west[s[-1]]
	for i in range(n - 2, -1, -1):
		suf[i] = suf[i + 1] + west[s[i]]
	ans = min(pre[-1], suf[0])
	for i in range(n - 1):
		ans = min(ans, pre[i] + suf[i + 1])
	print(ans)


T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	(x, y) = [int(i) for i in input().split()]
	prefse = [0 for i in range(n + 2)]
	prefsw = [0 for i in range(n + 2)]
	prefsn = [0 for i in range(n + 2)]
	prefss = [0 for i in range(n + 2)]
	sufse = [0 for i in range(n + 2)]
	sufsw = [0 for i in range(n + 2)]
	sufsn = [0 for i in range(n + 2)]
	sufss = [0 for i in range(n + 2)]
	reqd = 4 * x * n
	for i in range(n):
		prefse[i + 1] = prefse[i] + int(s[i] == 'E')
		prefsw[i + 1] = prefsw[i] + int(s[i] == 'W')
		prefsn[i + 1] = prefsn[i] + int(s[i] == 'N')
		prefss[i + 1] = prefss[i] + int(s[i] == 'S')
	for i in range(n - 1, -1, -1):
		sufse[i] = sufse[i + 1] + int(s[i] == 'E')
		sufsw[i] = sufsw[i + 1] + int(s[i] == 'W')
		sufsn[i] = sufsn[i + 1] + int(s[i] == 'N')
		sufss[i] = sufss[i + 1] + int(s[i] == 'S')
	for eren in range(n + 1):
		left = 0
		right = 0
		easttoeast = 0
		westtoeast = min(2 * x, 2 * y) * prefsw[eren]
		northtoeast = min(x, 3 * y) * prefsn[eren]
		southtoeast = min(y, 3 * x) * prefss[eren]
		left = westtoeast + northtoeast + southtoeast
		easttowest = min(2 * x, 2 * y) * sufse[eren]
		northtowest = min(y, 3 * x) * sufsn[eren]
		southtowest = min(x, 3 * y) * sufss[eren]
		right = easttowest + northtowest + southtowest
		reqd = min(reqd, left + right)
	print(reqd)


for _ in range(int(input())):
	n = int(input())
	s = input()
	(y, x) = map(int, input().split())
	(left, reverse, right) = (min(x, 3 * y), min(2 * x, 2 * y), min(3 * x, y))
	dic = {'N': 0, 'S': 0, 'E': 0, 'W': 0}
	for v in s:
		dic[v] += 1
	cost = dic['N'] * left + dic['E'] * reverse + dic['S'] * right
	minim = cost
	for v in s:
		if v == 'N':
			cost = cost - left + right
		elif v == 'E':
			cost -= reverse
		elif v == 'S':
			cost = cost - right + left
		else:
			cost += reverse
		minim = min(minim, cost)
	print(minim)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	n = inp()
	s = st()
	(x, y) = ma()
	pre = [0]
	suf = [0]
	for i in range(n):
		if s[i] == 'N':
			pre.append(pre[-1] + min(x, 3 * y))
		if s[i] == 'S':
			pre.append(pre[-1] + min(x * 3, y))
		if s[i] == 'E':
			pre.append(pre[-1] + min(x, 3 * y, 0))
		if s[i] == 'W':
			pre.append(pre[-1] + min(2 * x, 2 * y))
	for i in range(n - 1, -1, -1):
		if s[i] == 'N':
			suf.append(suf[-1] + min(x * 3, y))
		if s[i] == 'S':
			suf.append(suf[-1] + min(x, y * 3))
		if s[i] == 'E':
			suf.append(suf[-1] + min(2 * x, 2 * y))
		if s[i] == 'W':
			suf.append(suf[-1] + min(2 * x, 2 * y, 0))
	suf = suf[1:][::-1]
	suf.append(0)
	mi = 1000000000000000000000
	for i in range(n + 1):
		mi = min(mi, pre[i] + suf[i])
	print(mi)


for _ in range(int(input())):
	n = int(input())
	a = input()
	(x, y) = map(int, input().split())
	east = [0]
	west = [0] * n + [0]
	for i in range(n):
		if a[i] == 'E':
			east.append(east[-1] + 0)
		elif a[i] == 'W':
			east.append(east[-1] + 2 * min(x, y))
		elif a[i] == 'N':
			east.append(east[-1] + min(x, 3 * y))
		else:
			east.append(east[-1] + min(y, 3 * x))
	for i in range(n - 1, -1, -1):
		if a[i] == 'E':
			west[i] = west[i + 1] + 2 * min(x, y)
		elif a[i] == 'W':
			west[i] = west[i + 1]
		elif a[i] == 'N':
			west[i] = west[i + 1] + min(y, 3 * x)
		else:
			west[i] = west[i + 1] + min(x, 3 * y)
	ans = min(east[-1], west[0])
	for i in range(1, n):
		ans = min(ans, east[i] + west[i])
	print(ans)