D. Least Cost Bracket Sequencetime limit per test1 secondmemory limit per test64 megabytesinputstandard inputoutputstandard outputThis is yet another problem on regular bracket sequences.A bracket sequence is called regular, if by inserting "+" and "1" into it we get a correct mathematical expression. For example, sequences "(())()", "()" and "(()(()))" are regular, while ")(", "(()" and "(()))(" are not. You have a pattern of a bracket sequence that consists of characters "(", ")" and "?". You have to replace each character "?" with a bracket so, that you get a regular bracket sequence.For each character "?" the cost of its replacement with "(" and ")" is given. Among all the possible variants your should choose the cheapest.InputThe first line contains a non-empty pattern of even length, consisting of characters "(", ")" and "?". Its length doesn't exceed 5·104. Then there follow m lines, where m is the number of characters "?" in the pattern. Each line contains two integer numbers ai and bi (1 ≤ ai,  bi ≤ 106), where ai is the cost of replacing the i-th character "?" with an opening bracket, and bi — with a closing one.OutputPrint the cost of the optimal regular bracket sequence in the first line, and the required sequence in the second.Print -1, if there is no answer. If the answer is not unique, print any of them. ExamplesInput(??)1 22 8Output4()()
Input(??)1 22 8
Output4()()
['greedy', '*2600']