{"code":"perbracket","name":"Bài toán chi phí với dãy ngoặc đúng","description":"Một dãy ngoăc đơn được gọi là dãy ngoặc đúng nếu ta thêm dấu `+` và số `1` vào nó thì ta được một biểu thức toán học đúng.\r\n\r\n**Ví dụ:** `\"(())()\", \"()\"` là các dãy ngoặc đúng , còn `\")(\", \"(()\" and \"(()))(\"` không phải là dãy ngoặc đúng.\r\n\r\n**Yêu cầu:**\r\n\r\n- Cho một chuỗi $S$ chỉ gồm các kí tự `?`, `)` và `(`. Hãy thay tất cả các dấu `?` có trong $S$ bằng các kí tự `(` hoặc `)` với chi phí cho trước, sao cho $S$ là một dãy ngoặc đúng và chi phí thay thế là nhỏ nhất.\r\n \r\n

Input

\r\n\r\n- Dòng thứ nhất chứa xâu $S$ có độ dài không quá $5.10^4$\r\n\r\n- $m$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $a_i,b_i(1\\le a_i,b_i\\le 10^6)$ - Trong đó: $m$ là số lượng dấu `?` có trong xâu $S$, $a_i$ là chi phí thay thế dấu `?` thứ $i$ bởi dấu `(` còn $b_i$ là chi phí thay thế dấu `?` thứ $i$ bởi `)`\r\n\r\n\r\n

Output

\r\n\r\n- Dòng thứ nhất chứa chi phí tối thiểu cần dùng\r\n\r\n- Dòng thứ hai, in ra dãy ngoặc đúng tương ứng với chi phí trên. \r\n\r\n**Chú ý:** Nếu có nhiều đáp án thoả mãn yêu cầu bài toán, in ra bất kì, ngược lại nếu không có cách thay thế nào thoả mãn, in ra `-1`\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n ((??()))??\r\n 1 2\r\n 2 3\r\n 3 4\r\n 4 1\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 8\r\n (()(()))()\r\n ```","points":580.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}