Tý có một xâu độ dài \(N\) gồm các ký tự \((, ), [, ], {, }\). Bạn có thể xóa một số ký tự (không đổi thứ tự) để thu được xâu ngoặc đúng. Tìm độ dài lớn nhất của xâu ngoặc đúng có thể tạo thành.

#

Định dạng đầu vào

• Một dòng duy nhất chứa xâu ngoặc \(S\) gồm các ký tự ( và ) (\(1 \le |S| \le 500\)).

Định dạng đầu ra

• In ra số lượng dấu ngoặc tối thiểu cần thêm vào để \(S\) trở thành dãy ngoặc đúng.

Ví dụ

Input:

())

Output:

1

Giải thích: Thêm một dấu ( vào đầu để được (()).

Ràng buộc & Subtasks