TopCoder

AA 競程
AA 競程是最強的!

User's AC Ratio

94.5% (52/55)

Submission's AC Ratio

34.8% (116/333)

Tags

Description

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

Input Format

第一行有一個正整數 $T$ 代表有 $T$ 筆資料要你回答($1 \le T \le 5$)
每筆資料會先有一行字串代表原本的排列方式($1 \le$ 長度 $\le 500000$)
再來會有 $N$ 行,第 $i$ 行會有兩個數字 $L_i, R_i$ 如題目敘述意思。
(其中 $1 \le i \le N$,$N$ 為字串中 ? 的數目)($L_i, R_i$ 在 int 範圍內)

Output Format

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

Sample Input 1

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

Sample Output 1

0
20
10
QAQ

Hints

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10