You desperately need to build some string t. For that you've got n more strings s_1, s_2, ..., s_{n}. To build string t, you are allowed to perform exactly |t| (|t| is the length of string t) operations on these strings. Each operation looks like that:  choose any non-empty string from strings s_1, s_2, ..., s_{n};  choose an arbitrary character from the chosen string and write it on a piece of paper;  remove the chosen character from the chosen string. 

Note that after you perform the described operation, the total number of characters in strings s_1, s_2, ..., s_{n} decreases by 1. We are assumed to build string t, if the characters, written on the piece of paper, in the order of performed operations form string t.

There are other limitations, though. For each string s_{i} you know number a_{i} — the maximum number of characters you are allowed to delete from string s_{i}. You also know that each operation that results in deleting a character from string s_{i}, costs i rubles. That is, an operation on string s_1 is the cheapest (it costs 1 ruble), and the operation on string s_{n} is the most expensive one (it costs n rubles).

Your task is to count the minimum amount of money (in rubles) you will need to build string t by the given rules. Consider the cost of building string t to be the sum of prices of the operations you use.


-----Input-----

The first line of the input contains string t — the string that you need to build.

The second line contains a single integer n (1 ≤ n ≤ 100) — the number of strings to which you are allowed to apply the described operation. Each of the next n lines contains a string and an integer. The i-th line contains space-separated string s_{i} and integer a_{i} (0 ≤ a_{i} ≤ 100). Number a_{i} represents the maximum number of characters that can be deleted from string s_{i}.

All strings in the input only consist of lowercase English letters. All strings are non-empty. The lengths of all strings do not exceed 100 characters.


-----Output-----

Print a single number — the minimum money (in rubles) you need in order to build string t. If there is no solution, print -1.


-----Examples-----
Input
bbaze
3
bzb 2
aeb 3
ba 10

Output
8

Input
abacaba
4
aba 2
bcc 1
caa 2
bbb 5

Output
18

Input
xyz
4
axx 8
za 1
efg 4
t 1

Output
-1



-----Note-----

Notes to the samples:

In the first sample from the first string you should take characters "b" and "z" with price 1 ruble, from the second string characters "a", "e" и "b" with price 2 rubles. The price of the string t in this case is 2·1 + 3·2 = 8.

In the second sample from the first string you should take two characters "a" with price 1 ruble, from the second string character "c" with price 2 rubles, from the third string two characters "a" with price 3 rubles, from the fourth string two characters "b" with price 4 rubles. The price of the string t in this case is 2·1 + 1·2 + 2·3 + 2·4 = 18.

In the third sample the solution doesn't exist because there is no character "y" in given strings.

Difficulty: HARD
Tags: Graph algorithms

Flows and cuts

Starter code:

Solutions:
class Edge:

	def __init__(self, to, cost, capacity, next_edge):
		self.to = to
		self.cost = cost
		self.origin_cost = cost
		self.capacity = capacity
		self.next_edge = next_edge
		self.pair = None

class MinCostMaxFlow:

	def __init__(self, max_node):
		self.null = Edge(0, 0, 0, None)
		self.max_node = max_node + 3
		self.total_cost = 0
		self.current_cost = 0
		self.visited = [False] * self.max_node
		self.arc_list = []
		self.edge_head = [self.null] * self.max_node
		self.source = max_node + 1
		self.sink = max_node + 2

	def AddArcWithCapacityAndUnitCost(self, start_node, end_node, capacity, cost):
		self.edge_head[start_node] = Edge(end_node, cost, capacity, self.edge_head[start_node])
		self.edge_head[end_node] = Edge(start_node, -cost, 0, self.edge_head[end_node])
		self.edge_head[start_node].pair = self.edge_head[end_node]
		self.edge_head[end_node].pair = self.edge_head[start_node]
		if start_node != self.source and start_node != self.sink and (end_node != self.source) and (end_node != self.sink):
			self.arc_list.append(self.edge_head[end_node])

	def NumArcs(self):
		return len(self.arc_list)

	def Tail(self, index):
		return self.arc_list[index].to

	def Head(self, index):
		return self.arc_list[index].pair.to

	def UnitCost(self, index):
		return self.arc_list[index].pair.origin_cost

	def Flow(self, index):
		return self.arc_list[index].capacity

	def OptimalFlow(self):
		edge = self.edge_head[self.sink]
		total_flow = 0
		while id(edge) != id(self.null):
			total_flow += edge.capacity
			edge = edge.next_edge
		return total_flow

	def OptimalCost(self):
		return self.total_cost

	def SetNodeSupply(self, node, supply):
		if supply > 0:
			self.AddArcWithCapacityAndUnitCost(self.source, node, supply, 0)
		elif supply < 0:
			self.AddArcWithCapacityAndUnitCost(node, self.sink, -supply, 0)

	def aug(self, node_id, total_flow):
		if node_id == self.sink:
			self.total_cost += self.current_cost * total_flow
			return total_flow
		self.visited[node_id] = True
		flow = total_flow
		edge = self.edge_head[node_id]
		while id(edge) != id(self.null):
			if edge.capacity > 0 and edge.cost == 0 and (not self.visited[edge.to]):
				delta = self.aug(edge.to, min(flow, edge.capacity))
				edge.capacity -= delta
				edge.pair.capacity += delta
				flow -= delta
				if flow == 0:
					return total_flow
			edge = edge.next_edge
		return total_flow - flow

	def modify_label(self):
		min_cost = 1 << 63
		for node_id in range(0, self.max_node):
			if not self.visited[node_id]:
				continue
			edge = self.edge_head[node_id]
			while id(edge) != id(self.null):
				if edge.capacity > 0 and (not self.visited[edge.to]) and (edge.cost < min_cost):
					min_cost = edge.cost
				edge = edge.next_edge
		if min_cost == 1 << 63:
			return False
		for node_id in range(0, self.max_node):
			if not self.visited[node_id]:
				continue
			edge = self.edge_head[node_id]
			while id(edge) != id(self.null):
				edge.cost -= min_cost
				edge.pair.cost += min_cost
				edge = edge.next_edge
		self.current_cost += min_cost
		return True

	def Solve(self):
		while True:
			while True:
				self.visited = [False] * self.max_node
				if self.aug(self.source, 1 << 63) == 0:
					break
			if not self.modify_label():
				break
		return self.total_cost

def main():
	s = input()
	n = int(input())
	source = 0
	sink = n + 26 + 1
	mcmf = MinCostMaxFlow(n + 28)
	length = len(s)
	num = [0] * 29
	for i in range(0, length):
		num[ord(s[i]) - ord('a') + 1] += 1
	for i in range(1, 27):
		if num[i] > 0:
			mcmf.AddArcWithCapacityAndUnitCost(i, sink, num[i], 0)
	for i in range(1, n + 1):
		(s, used) = input().split(' ')
		mcmf.AddArcWithCapacityAndUnitCost(source, 26 + i, int(used), 0)
		num = [0] * 29
		for j in range(0, len(s)):
			num[ord(s[j]) - ord('a') + 1] += 1
		for j in range(1, 27):
			if num[j] > 0:
				mcmf.AddArcWithCapacityAndUnitCost(26 + i, j, num[j], i)
	mcmf.SetNodeSupply(source, 1 << 63)
	mcmf.SetNodeSupply(sink, -(1 << 63))
	mcmf.Solve()
	if mcmf.OptimalFlow() != length:
		print('-1')
	else:
		print(mcmf.OptimalCost())

def __starting_point():
	main()
__starting_point()


from heapq import heappush, heappop

class MinCostFlow:
	INF = 10 ** 18

	def __init__(self, N):
		self.N = N
		self.G = [[] for i in range(N)]

	def add_edge(self, fr, to, cap, cost):
		G = self.G
		G[fr].append([to, cap, cost, len(G[to])])
		G[to].append([fr, 0, -cost, len(G[fr]) - 1])

	def flow(self, s, t, f):
		N = self.N
		G = self.G
		INF = MinCostFlow.INF
		res = 0
		H = [0] * N
		prv_v = [0] * N
		prv_e = [0] * N
		while f:
			dist = [INF] * N
			dist[s] = 0
			que = [(0, s)]
			while que:
				(c, v) = heappop(que)
				if dist[v] < c:
					continue
				for (i, (w, cap, cost, _)) in enumerate(G[v]):
					if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w]:
						dist[w] = r = dist[v] + cost + H[v] - H[w]
						prv_v[w] = v
						prv_e[w] = i
						heappush(que, (r, w))
			if dist[t] == INF:
				return -1
			for i in range(N):
				H[i] += dist[i]
			d = f
			v = t
			while v != s:
				d = min(d, G[prv_v[v]][prv_e[v]][1])
				v = prv_v[v]
			f -= d
			res += d * H[t]
			v = t
			while v != s:
				e = G[prv_v[v]][prv_e[v]]
				e[1] -= d
				G[v][e[3]][1] += d
				v = prv_v[v]
		return res
T = input()
need = [0] * 30
for t in T:
	need[ord(t) - ord('a')] += 1
have = [[0] * 30 for _ in range(110)]
N = int(input())
a = [0] * 110
for i in range(N):
	v = input().split()
	S = v[0]
	a[i] = int(v[1])
	for s in S:
		have[i][ord(s) - ord('a')] += 1
V = 30 + N + 10
flow = MinCostFlow(V)
start = 30 + N + 5
target = 30 + N + 6
for c in range(26):
	flow.add_edge(start, c, need[c], 0)
	for j in range(N):
		flow.add_edge(c, 30 + j, have[j][c], 0)
for i in range(N):
	flow.add_edge(30 + i, target, a[i], i + 1)
ans = flow.flow(start, target, len(T))
print(ans)