#pragma region /* \(^o^)/ import sys 私は人間です. 吾輩はやれば出来る子である.     ∩ ∩    (´・ω・)    _| ⊃/(___  / └-(____/   ̄ ̄ ̄ ̄ ̄ ̄ ̄  やる気はまだない.    ⊂⌒/ヽ-、__  /⊂_/____ /   ̄ ̄ ̄ ̄ ̄ ̄ ̄ */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; struct Init{Init(){std::cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(20) << fixed;}}init; using ll = long long; using ull = unsigned long long; using ld = long double; #define all(x) begin((x)), end((x)) #define pb push_back #define mp make_pair #define mt make_tuple #define uq(v) v.erase(unique(begin(v), end(v)), end(v)) #define _overload4(_1,_2,_3,_4,name,...) name #define _overload3(_1,_2,_3,name,...) name #define _rep1(n) for(int i=0;i=0;i--) #define _rrep2(i,n) for(int i=(n)-1;i>=0;i--) #define _rrep3(i,a,b) for(int i=(b)-1;i>=(a);i--) #define _rrep4(i,a,b,c) for(int i=a+(b-a-1)/c*c;i>=a;i-=c) #define rrep(...) _overload4(__VA_ARGS__,_rrep4,_rrep3,_rrep2,_rrep1)(__VA_ARGS__) template using pq = priority_queue; template using pq_g = priority_queue, greater>; template bool chmax(T &a, const T &b){if(a < b){a = b; return 1; } return 0;} template bool chmin(T &a, const T &b){if(a > b){a = b; return 1; } return 0;} template auto min(const T& a){ return *min_element(all(a)); } template auto max(const T& a){ return *max_element(all(a)); } constexpr ull INF = (1ULL << 61) + (1ULL << 30); constexpr int inf = (1 << 30); constexpr ld EPS = 1e-9; constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}; constexpr int dy[] = {0, 1 ,0, -1, 1, -1, 1, -1}; #pragma endregion template struct LambdaActedMonoid{ using S = S2; using F = F2; S op(const S &a, const S &b) const {return _op(a, b);} S e() const {return _e();} S mapping(const S &x, const F &f) const {return _mapping(x, f);} F composition(const F &f, const F &g) const {return _composition(f, g);} F id() const {return _id();} LambdaActedMonoid(Op _op, E _e, Mapping _mapping, Composition _composition,Id _id): _op(_op), _e(_e), _mapping(_mapping), _composition(_composition), _id(_id){} private: Op _op; E _e; Mapping _mapping; Composition _composition; Id _id; }; template LambdaActedMonoid(Op _op, E _e, Mapping _mapping, Composition _composition, Id _id) -> LambdaActedMonoid; template struct LazySegmentTree{ using S = typename ActedMonoid::S; using F = typename ActedMonoid::F; private: ActedMonoid m; int n{}, sz{}, height{}; vector dat; vector lazy; inline void update(int k){ dat[k] = m.op(dat[2 * k + 0], dat[2 * k + 1]); } inline void all_apply(int k, const F &x){ dat[k] = m.mapping(dat[k], x); if(k < sz) lazy[k] = m.composition(lazy[k], x); } inline void propagate(int k){ if(lazy[k] != m.id()){ all_apply(2 * k + 0, lazy[k]); all_apply(2 * k + 1, lazy[k]); lazy[k] = m.id(); } } public: LazySegmentTree() = default; explicit LazySegmentTree(ActedMonoid m, int n): m(m), n(n){ sz = 1; height = 0; while(sz < n) sz <<= 1, ++height; dat.assign(2 * sz, m.e()); lazy.assign(2 * sz, m.id()); } explicit LazySegmentTree(ActedMonoid m, const vector &v): LazySegmentTree(m, v.size()){ build(v); } void build(const vector &v){ assert(n == (int)v.size()); for(int k = 0; k < n; ++k) dat[k + sz] = v[k]; for(int k = sz - 1; k > 0; --k) update(k); } void set(int k, const S &x){ k += sz; for(int i = height; i > 0; --i) propagate(k >> i); dat[k] = x; for(int i = 1; i <= height; ++i) update(k >> i); } S get(int k){ k += sz; for(int i = height; i > 0; --i) propagate(k >> i); return dat[k]; } S operator[](int k){return get(k);} S query(int l, int r){ if(l >= r) return m.e(); l += sz; r += sz; for(int i = height; i > 0; --i){ if(((l >> i) << i) != l) propagate(l >> i); if(((r >> i) << i) != r) propagate((r - 1) >> i); } S L = m.e(), R = m.e(); for(; l < r; l >>= 1, r >>= 1){ if(l & 1) L = m.op(L, dat[l++]); if(r & 1) R = m.op(dat[--r], R); } return m.op(L, R); } S all_query() const {return dat[1];} void apply(int k, const F &f){ k += sz; for(int i = height; i > 0; --i) propagate(k >> i); dat[k] = m.mapping(dat[k], f); for(int i = 1; i <= height; ++i) update(k >> i); } void apply(int l, int r, const F &f){ if(l >= r) return; l += sz; r += sz; for(int i = height; i > 0; --i){ if(((l >> i) << i) != l) propagate(l >> i); if(((r >> i) << i) != r) propagate((r - 1) >> i); } int l2 = l, r2 = r; for(; l < r; l >>= 1, r >>= 1){ if(l & 1) all_apply(l++, f); if(r & 1) all_apply(--r, f); } l = l2, r = r2; for(int i = 1; i <= height; ++i){ if(((l >> i) << i) != l) update(l >> i); if(((r >> i) << i) != r) update((r - 1) >> i); } } template int find_first(int l, const C &check){ if(l >= n) return n; l += sz; for(int i = height; i > 0; --i) propagate(l >> i); S sum = m.e(); do{ while((l & 1) == 0) l >>= 1; if(check(m.op(sum, dat[l]))){ while(l < sz){ propagate(l); l <<= 1; auto nxt = m.op(sum, dat[l]); if(not check(nxt)){ sum = nxt; ++l; } } return l + 1 - sz; } sum = m.op(sum, dat[l++]); }while((l & -l) != l); return n; } template int find_last(int r, const C &check){ if(r <= 0) return -1; r += sz; for(int i = height; i > 0; --i) propagate((r - 1) >> i); S sum = m.e(); do{ --r; while(r > 1 && (r & 1)) r >>= 1; if(check(m.op(dat[r], sum))){ while(r < sz){ propagate(r); r = (r << 1) + 1; auto nxt = m.op(dat[r], sum); if(not check(nxt)){ sum = nxt; --r; } } return r - sz; } sum = m.op(dat[r], sum); }while((r & -r) != r); return -1; } }; auto op1 = [](ll a, ll b){return min(a, b); }; auto e1 = []() { return (ll)INF; }; auto mapping1 = [](ll x, ll f){return x + f;}; auto composition1 = [](ll f, ll g){return f + g;}; auto id1 = [](){return 0LL;}; int main(){ int N; cin >> N; string S; cin >> S; ll R, M; cin >> R >> M; if(N & 1){ cout << "-1\n"; return 0; } ll ans = INF; LazySegmentTree seg(LambdaActedMonoid(op1, e1, mapping1, composition1, id1), 2 * N); int cutkari = 0; rep(i, N){ if(S[i] == '(') ++cutkari; else --cutkari; seg.set(N + i, cutkari); } int cur1 = max((-seg.query(N, N * 2) + 1) / 2, 0LL); ans = (cur1 + (seg[2 * N - 1] + cur1 * 2) / 2) * M; rep(i, 1, N){ seg.apply(N - i, 2 * N - i, (S[N - i] == '(' ? 1 : -1)); int cur = max((-seg.query(N - i, N * 2 - i) + 1) / 2, 0LL); ans = min(ans, R * i + (cur + (seg[2 * N - 1] + cur * 2) / 2) * M); } cout << ans << "\n"; }