Cho một biểu thức chỉ gồm các kí tự (, ), [, ], {, }. Một biểu thức đúng là một biểu thức khi xóa từng cặp dấu ngoặc tương ứng ta thu được một xâu rỗng.

Yêu cầu:

Nhập vào một biểu thức gồm nhiều kí tự (chứa ~6~ loại kí tự nêu trên) và tìm cách thêm một số ít nhất các kí tự thuộc một trong ~6~ loại kí tự nêu trên để nhận được biểu thức đúng.

Ví dụ:( ] ) ( { ( } ) ( là biểu thức không đúng. Biểu thức đúng là: ( [ ] ) ( { ( ) } ) ( )

Dữ liệu vào:

Một xâu thể hiện biểu thức gồm ~n~ kí tự (~n \leq 5000~).

Kết quả ra:

Một số nguyên chứa số lượng ít nhất các kí tự cần phải thêm vào để được một biểu thức đúng.

Sample Input

( ] ) ( { ( } ) (

Sample Output

3

Nguồn: Đề thi HSG cấp tỉnh năm học 2014 - 2015