# CFR 3 D. Least Cost Bracket Sequence ( Greedy )

Problem - D - Codeforces

O( N lg N ) / O( N )

```string seq;
vi A, B;

vi qid;

void init(){
cin >> seq;
for( int i = 0; i < seq.size(); ++i ){
if( seq[ i ] == '?' ){
qid.emplace_back( i );
}
}
A = B = vi( seq.size() );
for( int i = 0; i < qid.size(); ++i ){
int a, b; cin >> a >> b;
A[ qid[ i ] ] = a;
B[ qid[ i ] ] = b;
}
}

ll ans = 0;

void preprocess(){
vi r2l_cost( seq.size(), INF );
for( int i = 0; i < seq.size(); ++i ){
if( seq[ i ] != '?' ) continue;
seq[ i ] = ')';
ans += B[ i ];
r2l_cost[ i ] = A[ i ] - B[ i ];
}
priority_queue< pii, vp, greater< pii > > minheap;
for( int i = 0, lcnt = 0; i < seq.size(); ++i ){
if( seq[ i ] == '(' ){
++lcnt;
} else{
--lcnt;
}
if( r2l_cost[ i ] != INF ){
minheap.emplace( r2l_cost[ i ], i );
}
if( lcnt < 0 ){
if( minheap.empty() ){
cout << -1 << endl;
exit( 0 );
}
int c, id; tie( c, id ) = minheap.top(); minheap.pop();
seq[ id ] = '(';
ans += c;
lcnt += 2;
}
if( i + 1 == seq.size() and lcnt ){
cout << -1 << endl;
exit( 0 );
}
}
}

void solve(){
cout << ans << endl;
cout << seq << endl;
}
```