003-D.md

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

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

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

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

Оролт

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

Гаралт

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

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

-- zoloogg