C. Captains Mode
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Костя — профессиональный киберспортсмен, специализирующийся на дисциплине Dota 2. Недавно компания Valve, разработчик этой игры, выпустила новый патч, перевернувший баланс игры с ног на голову. Костя, являясь капитаном команды, понимает, что наибольшая ответственность лежит на нем, поэтому он хочет прибегнуть к анализу нововведений патча с математической точки зрения, чтобы выбирать наилучших героев для своей команды в каждом матче.

В матче Dota 2 участвуют две команды, каждая из которых должна взять для себя некоторых героев, за которых впоследствии будут играть члены этой команды, причем запрещено выбирать одного и того же героя несколько раз, даже разными командами. На крупных киберспортивных турнирах, таких, в которых собирается участвовать команда Кости, матчи проходят в режиме Captains Mode. В этом режиме для выбора героев капитаны команд в определенном, заранее установленном порядке совершают одно из двух возможных действий: пик (pick) или бан (ban).

  • Пик — это выбор героя для своей команды. После того, как капитан команды сделал пик, герой, которого он выбрал, отправляется в его команду (за него впоследствии будет играть один из членов команды) и больше не может быть выбран ни одной из команд.
  • Бан — это запрет героя. После бана герой не отправляется ни в одну из команд, однако он также больше не может быть выбран ни одной из команд.

Капитан команды может пропустить пик или бан. В случае пропуска пика в его команду добавляется случайный герой из тех, что были доступны на данный момент, а в случае пропуска бана не запрещается ни один герой, как будто этого бана и не было.

Костя уже определил силу всех героев с учетом исправлений нового патча. Разумеется, Костя знает и порядок пиков и банов. Сила команды равна сумме сил входящих в нее героев, и обе команды, участвующие в матче, стремятся максимизировать разницу в силе в свою сторону. Помогите Косте определить, у какой команды в матче — у первой или у второй — преимущество, и насколько оно велико.

Входные данные

В первой строке записано единственное целое число n (2 ≤ n ≤ 100) — количество героев в Dota 2.

Во второй строке записаны n целых чисел s1, s2, ..., sn (1 ≤ si ≤ 106) — силы всех героев.

В третьей строке записано единственное целое число m (2 ≤ m ≤ min(n, 20)) — количество действий, которые должны выполнить капитаны команд.

Следующие m строк имеют вид «action team», где action — действие, которое необходимо выполнить: пик (обозначающийся символом «p») или бан (обозначающийся символом «b»), а team — номер команды, которой предстоит выполнить это действие (число 1 или 2).

Гарантируется, что каждая команда делает хотя бы один пик. Кроме того, количество пиков, совершаемых каждой командой, совпадает, и количество банов, совершаемых каждой командой, совпадает.

Выходные данные

Выведите единственное целое число — разность между силой первой команды и силой второй команды, если капитаны обоих команд будут действовать оптимально.

Примеры
Входные данные
2
2 1
2
p 1
p 2
Выходные данные
1
Входные данные
6
6 4 5 4 5 5
4
b 2
p 1
b 1
p 2
Выходные данные
0
Входные данные
4
1 2 3 4
4
p 2
b 2
p 1
b 1
Выходные данные
-2