Killgrave wants to use his mind control powers to get money from the Justice League superheroes living in $N$ houses in Happy Harbor that are numbered sequentially from $1$ to $N$. There are $\mbox{M}$ roads, and each road $j$ connects two different houses, $A_j$ and $B_j$. Each superhero house $\boldsymbol{i}$ (where $1\leq i\leq N$) has $C_i$ dollars stashed away for a rainy day.

As long as a superhero is home at house $\boldsymbol{i}$, Killgrave knows they will hand over all of their saved money, $C_i$. Once he gets money from them, he moves on to the next house. However, the superheroes are cunning; when Killgrave comes to house $\mbox{X}$, every neighbor immediately connected to house $\mbox{X}$ by a single road skips town for a couple of days (making it impossible for Killgrave to get money from them). In other words, after Killgrave visits all the superheroes he wants, there will be no road in which he was able to get money from both houses on either end of the road.

What is the maximum amount of money Killgrave can collect from the superheroes, and how many different ways can Killgrave get that amount of money? Two ways are considered to be different if the sets of visited houses are different.

Note: Killgrave can start at an arbitrary house and doesn't have to only use the roads.

Input Format

The first line contains two space-separated integers, $N$ (the number of houses) and $\mbox{M}$ (the number of roads), respectively. 

The second line contains $N$ space-separated integers, where each integer $\boldsymbol{i}$ describes the amount of money, $C_i$, at house $\boldsymbol{i}$. 

Each line $j$ of the $\mbox{M}$ subsequent lines contains two space-separated integers defining a road connecting houses $A_j$ and $B_j$. Every road connects a different pair of houses.

Constraints

$1\leq N\leq34$
$0\leq M\leq N\cdot\frac{(N-1)}{2}$
$0\leq C_i\leq100$
$1\leq A_j,B_j\leq N$, where $A_j\neq B_j$
No unordered pair $(A_j,B_j)$ will appear more than once.

Output Format

Print two space-separated integers:

The first integer must denote the maximum amount of money Killgrave can get out of the Justice League.
The second integer must denote the number of different ways he can collect that amount of money.

Sample Input
3 2
6 8 2
1 2
3 2

Sample Output
8 2

Explanation

Killgrave has two possible courses of action:

Visit house $2$ and get $8$ dollars.
Visit houses $1$ and $3$ and get $2+6=8$ dollars. 

Both of these options result in $8$ dollars, so we know that this is maximal. Thus, we print the maximum amount of money ($8$) followed by the number of ways he can get that amount of money ($2$) as two space-separated values on a single line.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Graph algorithms


Solutions:
def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import sys

def dfs(i):
	for j in conn[i]:
		if not visited[j]:
			visited[j] = True
			conn_comp[-1].append(j)
			dfs(j)

def find_comp_max(comp):
	if len(comp) == 1:
		return (money[comp[0]], 1) if money[comp[0]] else (0, 2)
	elif len(comp) == 0:
		return (0, 1)
	(v1, c1) = find_comp_max([node for node in comp[1:] if node not in conn[comp[0]]])
	v1 += money[comp[0]]
	(v2, c2) = find_comp_max(comp[1:])
	if v1 == v2:
		return (v1, c1 + c2)
	elif v1 > v2:
		return (v1, c1)
	else:
		return (v2, c2)
(n, m) = [int(_) for _ in input().strip().split(' ')]
money = [int(_) for _ in input().strip().split(' ')]
conn = [set() for _ in range(n)]
for _ in range(m):
	(i, j) = [int(_) - 1 for _ in input().strip().split(' ')]
	conn[i].add(j)
	conn[j].add(i)
visited = [False] * n
conn_comp = []
for i in range(n):
	if not visited[i]:
		visited[i] = True
		conn_comp.append([i])
		dfs(i)
result = 0
count = 1
for comp in conn_comp:
	(v, c) = find_comp_max(comp)
	result += v
	count *= c
print(result, count)


def readints():
	return [int(fld) for fld in input().strip().split()]

def getgraph():
	(nvert, nedge) = readints()
	values = readints()
	nbrs = [[] for _ in values]
	for _ in range(nedge):
		(a, b) = readints()
		nbrs[a - 1].append(b - 1)
		nbrs[b - 1].append(a - 1)
	return (values, nbrs)

def solve(case):
	(values, nbrs) = case
	priority = [(-len(nbr), i) for (i, nbr) in enumerate(nbrs)]
	order = [i for (n, i) in sorted(priority)]
	return besttheft(order, values, nbrs, {(1 << len(values)) - 1: (0, 1)}, 0)

def besttheft(order, values, nbrs, memo, current, forbidden=0):
	if forbidden in memo:
		return memo[forbidden]
	vnum = None
	while current < len(values):
		vnum = order[current]
		if forbidden & 1 << vnum == 0:
			break
		current += 1
	newforbidden = forbidden | 1 << vnum
	(v0, c0) = besttheft(order, values, nbrs, memo, current + 1, newforbidden)
	for nbr in nbrs[vnum]:
		newforbidden |= 1 << nbr
	(v1, c1) = besttheft(order, values, nbrs, memo, current + 1, newforbidden)
	v1 += values[vnum]
	if v1 > v0:
		ans = (v1, c1)
	elif v1 < v0:
		ans = (v0, c0)
	else:
		ans = (v1, c0 + c1)
	memo[forbidden] = ans
	return ans
print('%d %d' % solve(getgraph()))


import sys
(n, m) = tuple((int(x) for x in sys.stdin.readline().split()))
c = tuple((int(x) for x in sys.stdin.readline().split()))
edges = tuple(([] for i in range(n)))
for i in range(m):
	(a, b) = tuple((int(x) for x in sys.stdin.readline().split()))
	a -= 1
	b -= 1
	edges[a].append(b)
	edges[b].append(a)
current_cc_id = 0
cc_id = [None] * n
cc_list = []
for i in range(n):
	if cc_id[i] is None:
		cc_list.append([])
		todo = [i]
		while len(todo) > 0:
			i = todo.pop()
			cc_id[i] = current_cc_id
			cc_list[current_cc_id].append(i)
			for j in edges[i]:
				if cc_id[j] is None:
					todo.append(j)
		current_cc_id += 1
cc_len = len(cc_list)
cc_score = [None] * cc_len
cc_count = [None] * cc_len
for cc in range(cc_len):
	valid_picked = []
	todo = [[]]
	while len(todo) > 0:
		picked = todo.pop()
		valid_picked.append(picked)
		pickable = set(cc_list[cc])
		for i in picked:
			if i in pickable:
				pickable.remove(i)
		for i in picked:
			for j in edges[i]:
				if j in pickable:
					pickable.remove(j)
		if len(pickable) > 0:
			if len(picked) > 0:
				min_pickable = max(picked) + 1
			else:
				min_pickable = 0
			for i in pickable:
				if i >= min_pickable:
					next_picked = list(picked)
					next_picked.append(i)
					todo.append(next_picked)
	top_score = -1
	top_count = -1
	for picked in valid_picked:
		score = 0
		for i in picked:
			score += c[i]
		if score > top_score:
			top_score = score
			top_count = 1
		elif score == top_score:
			top_count += 1
	cc_score[cc] = top_score
	cc_count[cc] = top_count
score = 0
count = 1
for cc in range(cc_len):
	score += cc_score[cc]
	count *= cc_count[cc]
print(score, count)


from sys import stderr
from heapq import heappop, heappush

def read(f):
	return f(input())

def readlist(f):
	return [f(x) for x in input().split()]
(N, M) = readlist(int)
C = readlist(int)
V = [[] for _ in range(N)]
Vmask = [0] * N
for _ in range(M):
	(u, v) = readlist(int)
	V[u - 1].append(v - 1)
	V[v - 1].append(u - 1)
	Vmask[u - 1] |= 1 << v - 1
	Vmask[v - 1] |= 1 << u - 1

def splitComponents(V):
	unvisited = set(range(len(V)))
	while unvisited:
		component = [unvisited.pop()]
		i = 0
		while i < len(component):
			v = component[i]
			i += 1
			for u in V[v]:
				if u in unvisited:
					unvisited.remove(u)
					component.append(u)
		yield component

def solveComponent(component):
	houses = [(1 << v, C[v], Vmask[v]) for v in component]
	worstBalance = 0
	worstSets = set([0])
	testedSets = set()
	H = [(0, 0, 0)]
	while H:
		(heroBalance, heroesVisited, goneFishing) = heappop(H)
		atHome = ~(heroesVisited | goneFishing)
		collectable = sum((cash for (hero, cash, neighbors) in houses if hero & atHome))
		if heroBalance - collectable > worstBalance:
			continue
		for (hero, cash, neighbors) in houses:
			if hero & atHome:
				v = hero | heroesVisited
				if v in testedSets:
					continue
				b = heroBalance - cash
				f = goneFishing | neighbors
				heappush(H, (b, v, f))
				if b <= worstBalance:
					if b < worstBalance:
						worstBalance = b
						worstSets.clear()
					worstSets.add(v)
				testedSets.add(v)
	return (-worstBalance, len(worstSets))
totalCollected = 0
totalSets = 1
for component in splitComponents(V):
	(maxCollected, numSets) = solveComponent(component)
	totalCollected += maxCollected
	totalSets *= numSets
print('%s %s' % (totalCollected, totalSets))


def decompose(G):
	if len(G) <= 1:
		return [G]
	else:
		v = next(iter(G))
		visited = {v}
		stack = [v]
		while stack:
			v = stack.pop()
			for u in G[v]:
				if u not in visited:
					stack.append(u)
					visited.add(u)
		if len(visited) == len(G):
			return [G]
		else:
			unvisited = set(iter(G)) - visited
			component = subtract(G, unvisited)
			subgraph = subtract(G, visited)
			components = decompose(subgraph)
			components.append(component)
			return components

def subtract(G, vs):
	return dict(map(lambda x: (x[0], x[1] - vs), filter(lambda x: x[0] not in vs, G.items())))

def subgraph(G, vs):
	sg = {}
	for v in vs:
		sg[v] = G[v] & vs
	return sg

def compose(results):
	w = 0
	c = 1
	for (w1, c1) in results:
		w += w1
		c *= c1
	return (w, c)

def solve_small_0(G, ws):
	return (0, 1)

def solve_small_1(G, ws):
	if len(G) < 1:
		return solve_small_0(G, ws)
	(v,) = iter(G)
	if ws[v] == 0:
		return (0, 2)
	else:
		return (ws[v], 1)

def solve_small_2(G, ws):
	if len(G) < 2:
		return solve_small_1(G, ws)
	Gs = decompose(G)
	if len(Gs) > 1:
		res = [solve_small_2(g, ws) for g in Gs]
		return compose(res)
	(v, u) = G
	if ws[u] > ws[v]:
		return (ws[u], 1)
	elif ws[v] > ws[u]:
		return (ws[v], 1)
	elif ws[u] > 0:
		return (ws[u], 2)
	else:
		return (ws[u], 3)

def solve_small_3(G, ws):
	if len(G) < 3:
		return solve_small_2(G, ws)
	Gs = decompose(G)
	if len(Gs) > 1:
		res = [solve_small_3(g, ws) for g in Gs]
		return compose(res)
	(u, v, w) = iter(G)
	if v in G[u] and w in G[v] and (u in G[w]):
		if ws[u] == ws[v] and ws[v] == ws[w]:
			if ws[u] > 0:
				return (ws[u], 3)
			else:
				return (0, 4)
		else:
			x = min(u, v, w, key=lambda t: ws[t])
			return solve_small_2(subtract(G, {x}), ws)
	else:
		if G[w] == {u, v}:
			(u, w) = (w, u)
		elif G[v] == {u, w}:
			(u, v) = (v, u)
		if ws[u] == 0 and ws[v] == 0 and (ws[w] == 0):
			return (0, 5)
		elif ws[u] > ws[v] + ws[w]:
			return (ws[u], 1)
		elif ws[u] == ws[v] + ws[w]:
			return (ws[u], 1 + solve_small_2(subtract(G, {u}), ws)[1])
		else:
			return solve_small_2(subtract(G, {u}), ws)

def solve_choice(G, v, f, ws):
	(w1, c1) = f(subtract(G, {v}), ws)
	(w2, c2) = f(subtract(G, G[v] | {v}), ws)
	w2 += ws[v]
	if w1 > w2:
		return (w1, c1)
	elif w2 > w1:
		return (w2, c2)
	else:
		return (w1, c1 + c2)

def solve_degree_2(G, ws):
	if len(G) <= 3:
		return solve_small_3(G, ws)
	Gs = decompose(G)
	if len(Gs) > 1:
		res = [solve_degree_2(g, ws) for g in Gs]
		return compose(res)
	v = min(G.keys(), key=lambda x: len(G[x]))
	if len(G[v]) < 2:
		(last, v) = (v, next(iter(G[v])))
		for _ in range(len(G) // 2):
			(last, v) = (v, next(iter(G[v] - {last})))
	return solve_choice(G, v, solve_degree_2, ws)

def solve_degree_3(G, ws):
	if len(G) <= 3:
		return solve_small_3(G, ws)
	Gs = decompose(G)
	if len(Gs) > 1:
		res = [solve_degree_3(g, ws) for g in Gs]
		return compose(res)
	v = max(G.keys(), key=lambda x: len(G[x]))
	if len(G[v]) <= 2:
		return solve_degree_2(G, ws)
	hood = G[v] | {v}
	connectihood = {}
	for u in G[v]:
		for w in G[u]:
			if w not in hood:
				connectihood.add(u)
				break
	if len(connectihood) == 1:
		conn = connectihood.pop()
		(u, w) = G[v] - {conn}
		r1 = solve_degree_3(subtract(G, hood), ws)
		r2 = solve_small_3(subgraph(G, {v, u, w}), ws)
		(w1, c1) = combine([r1, r2])
		r1 = solve_degree_3(subtract(G, hood | G[conn]), ws)
		r2 = solve_small_2(subgraph(G, {u, w} - G[conn]), ws)
		(w2, c2) = combine([r1, r2])
		w2 += ws[conn]
		if w1 > w2:
			return (w1, c1)
		elif w1 < w2:
			return (w2, c2)
		else:
			return (w1, c1 + c2)
	else:
		return solve_choice(G, v, solve_degree_3, ws)

def solve(G, ws):
	if len(G) <= 3:
		return solve_small_3(G, ws)
	Gs = decompose(G)
	if len(Gs) > 1:
		res = [solve(g, ws) for g in Gs]
		return compose(res)
	v = max(G.keys(), key=lambda x: len(G[x]))
	return solve_choice(G, v, solve, ws)

def main():
	(N, M) = map(int, input().split())
	ws = list(map(int, input().split()))
	G = dict([(i, set()) for i in range(N)])
	for _ in range(M):
		(u, v) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		G[u].add(v)
		G[v].add(u)
	(w, c) = solve(G, ws)
	print(w, c)
main()


import sys
(n, m) = map(int, input().split())
c = list(map(int, input().split()))
assert len(c) == n
adj = [[] for _ in range(n)]
inM = [False] * n
M = []
for _ in range(m):
	(a, b) = map(lambda s: int(s) - 1, input().split())
	adj[a].append(b)
	adj[b].append(a)
	if not (inM[a] or inM[b]):
		M.append((a, b))
		inM[a] = True
		inM[b] = True
k = len(M)
from collections import defaultdict
collect = defaultdict(int)
chosen = [False] * n

def chosenneighbor(u):
	for v in adj[u]:
		if chosen[v]:
			return True
	return False

def tryall(i, loot):
	if i < k:
		(a, b) = M[i]
		tryall(i + 1, loot)
		if not chosenneighbor(a):
			chosen[a] = True
			tryall(i + 1, loot + c[a])
			chosen[a] = False
		if not chosenneighbor(b):
			chosen[b] = True
			tryall(i + 1, loot + c[b])
			chosen[b] = False
	else:
		ways = 1
		for u in range(n):
			if not (inM[u] or chosenneighbor(u)):
				loot += c[u]
				if c[u] == 0:
					ways *= 2
		collect[loot] += ways
tryall(0, 0)
maxloot = max(collect.keys())
print(maxloot, collect[maxloot])


cache = {}

def maximal_paths(nodes: {}, edges):
	cache_key = str(sorted(nodes.keys()))
	if cache_key in cache:
		return cache[cache_key]
	if len(nodes) == 0:
		rval = (0, 1)
		cache[cache_key] = rval
		return rval
	(index, amount) = list(nodes.items())[0]
	rest = {x: y for (x, y) in list(nodes.items())[1:]}
	(weight1, count1) = maximal_paths(rest, edges)
	if edges[index] == []:
		rval = (weight1 + amount, count1)
		cache[cache_key] = rval
		return rval
	rest = {key: amt for (key, amt) in rest.items() if key not in edges[index]}
	(weight2, count2) = maximal_paths(rest, edges)
	weight2 = weight2 + amount
	if weight1 > weight2:
		rval = (weight1, count1)
		cache[cache_key] = rval
		return rval
	elif weight1 == weight2:
		rval = (weight1, count1 + count2)
		cache[cache_key] = rval
		return rval
	else:
		rval = (weight2, count2)
		cache[cache_key] = rval
		return rval
(n, m) = [int(x) for x in input().strip().split()]
money = {index + 1: int(x) for (index, x) in enumerate(input().strip().split())}
neighbors = {i: set() for i in range(1, n + 1)}
for i in range(m):
	(v1, v2) = [int(x) for x in input().strip().split()]
	neighbors[v1].add(v2)
	neighbors[v2].add(v1)
(weight, count) = maximal_paths(money, neighbors)
print(weight, count)


toParse = input().strip().split(' ')
(num_of_houses, num_of_roads) = [int(i) for i in toParse]
house_values = input().strip().split(' ')
house_values = [int(i) for i in house_values]
roads = []
for i in range(num_of_roads):
	toParse = input().strip().split(' ')
	(a, b) = [int(i) for i in toParse]
	roads.append((a, b))
house_connections = [[] for i in range(num_of_houses)]
for (a, b) in roads:
	house_connections[a - 1].append(b - 1)
	house_connections[b - 1].append(a - 1)
memoize = {}

def search(unvisited_houses):
	if not unvisited_houses:
		return (0, 1)
	if tuple(unvisited_houses) in memoize:
		(a, b) = memoize[tuple(unvisited_houses)]
		return (a, b)
	max_money = 0
	max_ways = 1
	for h in unvisited_houses:
		new_unvisited_houses = unvisited_houses[:]
		for x in new_unvisited_houses[:]:
			if x < h:
				new_unvisited_houses.remove(x)
		new_unvisited_houses.remove(h)
		for x in house_connections[h]:
			if x in new_unvisited_houses:
				new_unvisited_houses.remove(x)
		(a, b) = search(new_unvisited_houses)
		memoize[tuple(new_unvisited_houses)] = (a, b)
		a += house_values[h]
		if a == max_money:
			max_ways += b
		if a > max_money:
			max_money = a
			max_ways = b
	return (max_money, max_ways)
(a, b) = search([i for i in range(num_of_houses)])
print(str(a) + ' ' + str(b))


from collections import Counter

def read_line():
	return (int(x) for x in input().split())

def process_component(c, component, index, used, cur_sum, result):
	if index == len(component):
		result[cur_sum] += 1
		return
	v = component[index]
	process_component(c, component, index + 1, used, cur_sum, result)
	if used[v]:
		return
	used[v] = 1
	for n in g[v]:
		used[n] += 1
	process_component(c, component, index + 1, used, cur_sum + c[v], result)
	for n in g[v]:
		used[n] -= 1
	used[v] = 0
(n, m) = read_line()
c = [0] + list(read_line())
g = {i: [] for i in range(1, n + 1)}
ways = 1
max_result = 0
for _ in range(m):
	(u, v) = read_line()
	g[u].append(v)
	g[v].append(u)
found = set()
for v in g:
	if v in found:
		continue
	stack = [v]
	found.add(v)
	component = []
	while stack:
		v = stack.pop()
		component.append(v)
		for n in g[v]:
			if n in found:
				continue
			found.add(n)
			stack.append(n)
	result = Counter()
	process_component(c, component, 0, Counter(), 0, result)
	(c_max, c_ways) = max(result.items())
	max_result += c_max
	ways *= c_ways
print(max_result, ways)


from collections import Counter

def collectMoney(graph, counter):
	for v in graph:
		adjanced = graph[v]['adjanced']
		disconnected = []
		connected = []
		for path in counter:
			if not path & adjanced:
				disconnected.append(path)
			else:
				connected.append(path)
		cost = graph[v]['c']
		counter[1 << v] = cost
		for c in connected:
			mask = 1 << v | c & ~adjanced
			counter[mask] = counter[c & ~adjanced] + cost
		for d in disconnected:
			mask = d | 1 << v
			counter[mask] = counter[d] + cost
(nHouses, nRoads) = [int(x) for x in input().split()]
graph = {}
money = [int(x) for x in input().split()]
for i in range(1, nHouses + 1):
	graph[i] = {'c': money[i - 1], 'adjanced': 0}
for i in range(nRoads):
	(a, b) = [int(x) for x in input().split()]
	graph[a]['adjanced'] |= 1 << b
	graph[b]['adjanced'] |= 1 << a
counter = Counter()
result0 = 0
disconnected = []
disconnectedNulls = 0
for v in graph:
	if not graph[v]['adjanced']:
		result0 += graph[v]['c']
		disconnectedNulls += graph[v]['c'] == 0
		disconnected.append(v)
for v in disconnected:
	del graph[v]
if not graph:
	print(result0, 2 ** disconnectedNulls)
else:
	collectMoney(graph, counter)
	values = list(counter.values())
	result = max(values)
	ways = values.count(result)
	if result == 0:
		ways += 1
	print(result + result0, ways * 2 ** disconnectedNulls)


def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
c = list(map(int, input().split()))
g = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
a1 = 0
a2 = 1
vis = [0] * n
col = [0] * n
l1 = []
l2 = []

def getinfo(idx):
	if idx == len(l1):
		out = 0
		for i in l1:
			if col[i]:
				out += c[i]
		return (out, 1)
	for i in g[l1[idx]]:
		if col[i]:
			return getinfo(idx + 1)
	(p1, p2) = getinfo(idx + 1)
	col[l1[idx]] = 1
	(q1, q2) = getinfo(idx + 1)
	col[l1[idx]] = 0
	if p1 == q1:
		return (p1, p2 + q2)
	return max((p1, p2), (q1, q2))
for i in range(n):
	if not vis[i]:
		l1 = [i]
		l2 = [i]
		vis[i] = 1
		while l2:
			u = l2.pop(-1)
			for v in g[u]:
				if not vis[v]:
					l1.append(v)
					l2.append(v)
					vis[v] = 1
		(b1, b2) = getinfo(0)
		a1 += b1
		a2 *= b2
print('%s %s' % (a1, a2))


def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


from collections import deque
from sys import stdin

def sp(neighbors, values):
	possible = []
	no_value_and_no_neighbor = 0
	min_max_val = 0
	for i in range(len(neighbors)):
		if neighbors[i]:
			possible.append(i)
			continue
		if values[i] > 0:
			min_max_val += values[i]
			continue
		no_value_and_no_neighbor += 1
	possible = tuple(possible)
	cache = {possible: 0}
	q = deque([(possible, 0)])
	max_val = 0
	max_val_covers = 0
	while q:
		(possible, value) = q.pop()
		if not possible:
			continue
		set_possible = set(possible[1:])
		set_possible.difference_update(neighbors[possible[0]])
		new_possible = tuple(sorted(list(set_possible)))
		new_value = value + values[possible[0]]
		if new_value > max_val:
			max_val = new_value
			max_val_covers = 1
		elif new_value == max_val:
			max_val_covers += 1
		other_new_possible = tuple(list(possible)[1:])
		if new_possible not in cache or cache[new_possible] <= new_value:
			cache[new_possible] = new_value
			q.append((new_possible, new_value))
		if other_new_possible not in cache or cache[other_new_possible] <= value:
			cache[other_new_possible] = value
			q.append((other_new_possible, value))
	if max_val == 0 and max_val_covers > 0:
		max_val_covers += 1
	if max_val_covers == 0:
		max_val_covers = 1
	max_val += min_max_val
	max_val_covers *= 2 ** no_value_and_no_neighbor
	print(max_val, max_val_covers)
(n, m) = [int(c) for c in stdin.readline().split()]
values = []
neighbors = [[] for i in range(n)]
values = [int(c) for c in stdin.readline().split()]
for i in range(m):
	(v1, v2) = [int(c) - 1 for c in stdin.readline().split()]
	neighbors[v1].append(v2)
	neighbors[v2].append(v1)
sp(neighbors, values)


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(Z, G):
	mLost = {}

	def getMLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in mLost:
			return mLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMLost(housesToVisit)
		lost += Z[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((Z[b] for b in lostHouses))
		(losta, nba) = getMLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		mLost[key] = (lost, nb)
		return mLost[key]
	(amount, number) = getMLost(set(range(len(Z))))
	return (sum(Z) - amount, number)
(N, M) = map(int, input().split())
Z = tuple(map(int, input().split()))
G = {a: set() for a in range(len(Z))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(Z, G))))


def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import math
import os
import random
import re
import sys

def demandingMoney(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, demandingMoney(C, G))))


import math
import os
import random
import re
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import math
import os
import random
import re
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import math
import os
import random
import re
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))


import os
import sys

def solve(C, G):
	minLost = {}

	def getMinLost(housesToVisit):
		if not housesToVisit:
			return (0, 1)
		key = frozenset(housesToVisit)
		if key in minLost:
			return minLost[key]
		a = housesToVisit.pop()
		(lost, nb) = getMinLost(housesToVisit)
		lost += C[a]
		lostHouses = set((b for b in G[a] if b in housesToVisit))
		lostMoney = sum((C[b] for b in lostHouses))
		(losta, nba) = getMinLost(housesToVisit - lostHouses)
		losta += lostMoney
		housesToVisit.add(a)
		if losta < lost:
			(lost, nb) = (losta, nba)
		elif losta == lost:
			nb += nba
		minLost[key] = (lost, nb)
		return minLost[key]
	(amount, number) = getMinLost(set(range(len(C))))
	return (sum(C) - amount, number)
(N, M) = map(int, input().split())
C = tuple(map(int, input().split()))
G = {a: set() for a in range(len(C))}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].add(b - 1)
	G[b - 1].add(a - 1)
print(' '.join(map(str, solve(C, G))))