TopCoder

User's AC Ratio

100.0% (9/9)

Submission's AC Ratio

50.0% (15/30)

Description

“啊~ 撞到人了!!” “對不起!!!你沒有受傷吧~?”少女緊張的問 “哇啊啊!!!我被妁艷妹妹撞倒了!”妤嬌哭著說
“欸? 是妤嬌葛葛耶!!!” 妁艷妹妹驚覺 “妁艷妹妹你知道你哥哥怎麼了嗎? 為甚麼他今天沒來上學...?” “哥哥被壞人抓走了...我要去救他!!!” “恩...我也要去!!!”
妤嬌立刻衝回家準備,因為他想幫妁艷妹妹救出哥哥。然後到家後... “姊姊我跟你說”
“不要跟我說”妤嬌姊姊回答 “姊姊的...”
“好好吃!!!!!!”妤嬌哥哥吃著香腸,突然冒出一句
妤嬌姊姊氣到嘟著嘴說“哥哥你那香腸看起來就不好吃!!!” 哥哥回答”可是桌上這些香腸不但聞起來很香而且還很好吃喔~ 啊妤嬌你也 來
幫我一個忙吧~” 現在桌上有好多彎彎的香腸,有向右彎的香腸“(”,也有向左彎的香腸”)” 還有一些不知道該向左彎還向右彎的香腸,他們先用”?”代表。
這些香腸由左到右排成一排。現在哥哥希望,從最左邊第一個香腸往右數到任何 一個香腸時,都能保證向左彎的香腸數量不比向右彎的香腸數量多。而且哥哥還 希望在所有香腸中,向右彎的數量和向左彎的數量一樣。
然後對於由左到右第 i 個不知道該往哪彎的香腸,如果往右彎變成”(”,會損失 Li 的香味,如果往左彎變成”)”,會損失 Ri 的香味
現在妤嬌哥哥告訴你(妤嬌)原本香腸的排列方法( 由(、)、?組成 ),以及所有的 L 及 R,希望你能求出最少損失的香味。

Input Format

第一行有一個正整數 T 代表有 T 筆資料要你回答(1 ≤ T ≤ 5)
每筆資料會先有一行字串代表原本的排列方式(1 ≤ 長度 ≤ 500000)
再來會有 N 行,第 i 行會有兩個數字 Li 、 Ri 如題目敘述意思。
(其中 1≤i≤N , N 為字串中”?”的數目) (L、R 是 int 範圍)

Output Format

對於每一筆資料輸出一行答案,代表最少的總共損失的香味
但如果不管香腸怎麼排,都不符合哥哥的希望,則輸出”QAQ”(不含雙引號)

Sample Input

4
(())
(??)
1 10
10 100
?????)))))
2 1
2 1
2 1
2 1
2 1
(((((?
2147483647 -2147483648

Sample Output

0
20
10
QAQ

Hints

Problem Source

原TIOJ1788 / problem setter: lnsuyn; source: 2011 TOI 4模; source of source: CF-3D

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144
3 10000 65536 262144
4 10000 65536 262144
5 10000 65536 262144
6 10000 65536 262144
7 10000 65536 262144
8 10000 65536 262144
9 10000 65536 262144