Bracket Repair Budget

A log sanitizer receives bracket templates. Each template contains fixed opening brackets, fixed closing brackets, and repair slots marked with ?. For every repair slot, the platform knows the cost of turning it into an opening bracket and the cost of turning it into a closing bracket. A repaired log is accepted only if the whole bracket string is balanced and no prefix has more closing brackets than opening brackets. For each template, report the minimum possible repair cost, or -1 if acceptance is impossible. Input Format: The first line contains t. Each case starts with the template string. For every ? in the template, in left-to-right order, one line follows with openCost and closeCost. Output Format: For each case, print the minimum total repair cost, or -1 if the template cannot become valid.