D. Хамгийн бага үнэтэй зөв хаалт

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 64 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Дахиад л нэг зөв хаалттай холбоотой бодлого байна.

Зөв хаалт гэдэг нь хаалтнуудын хооронд "$1$" эсвэл "$+$" тэмдэг тавихад зөв математик илэрхийлэл гардаг хаалт юм. Жишээ нь "(())()", "()", "(()(()))" нь зөв хаалт бөгөөд ")(", "(()", "(()))(" нь зөв хаалт биш. Танд "(", ")" ба "?" тэмдэгтүүдээс тогтох хаалт өгөгдсөн бөгөөд "?" тэмдгийг нээх, эсвэл хаах хаалтаар солих юм.

Бүх "?" тэмдгийн хувьд нээх буюу хаах хаалтаар солигдох үнэ нь өгөгдсөн бол зөв хаалт үүсгэх хамгийн хямд үнийг ол.

Оролт

Оролтын эхний мөрөнд "(", ")", "?" тэмдэгтүүдээс тогтох хоосон биш тэмдэгт мөр өгөгдөнө. Уг тэмдэгт мөрийн урт $5·10^4$-с хэтрэхгүй. Үүний дараа нийт "?" тэмдгийн тоотой тэнцүү $m$ ширхэг мөр байна. Мөр бүрд $i$-р хаалтыг нээх хаалтаар солих үнэ $a_i$ ба хаах хаалтаар солих үнэ $b_i$ ($1 ≤ a_i, b_i ≤ 10^6$) байна.

Гаралт

Гаралтын эхний мөрөнд хамгийн бага өртөг, дараагийн мөрөнд үүсэх зөв хаалтыг хэвлэ.

Хэрэв хариу байхгүй бол "-1"-г хэвлэнэ. Олон хариутай бол алийг нь ч гаргаж болно.

Орчуулсан: zoloogg

Жишээ тэстүүд

Оролт
(??)
1 2
2 8
Гаралт
4
()()
Сэтгэгдлүүдийг ачааллаж байна...