Nếu A là một xâu biểu diễn một biểu thức ngoặc đúng thì (A) cũng là biểu diễn một biểu thức ngoặc đúng;
Nếu hai A, B là xâu biểu diễn biểu thức ngoặc đúng thì AB cũng là biểu diễn một biểu thức ngoặc đúng.
Thầy Alice muốn tạo một biểu thức ngoặc đúng, có vị trí có thể đặt ngoặc. Các vị trị được đánh số từ đến từ trái sang phải, bắt đầu với giá trị , tại mỗi vị trí thầy Alice có ba lựa chọn:
Đặt ví trí này là dấu ( và thay ;
Đặt ví trí này dấu ) và thay ;
Bỏ qua vị trí này.
Sau khi lựa chọn xong, lấy các kí tự từ trái sang phải ở các vị trí đặt dấu ( hoặc ) để tạo được biểu thức ngoặc đúng mà đạt giá trị lớn nhất.
Dữ liệu:
Dòng thứ nhất chứa số nguyên dương ;
Dòng thứ hai chứa số nguyên .
Kết quả:
Ghi ra một số nguyên duy nhất là giá trị lớn nhất có thể chọn được.
Ví dụ:
Dữ liệu:
4
0 -5 1 2
Kết quả:
5
Dữ liệu:
9
5 -2 2 3 -4 -4 -1 -2 9
Kết quả:
21
Giới hạn:
Có số test ứng với số điểm của bài có ;
Có số test khác ứng với số điểm của bài có ;
Có số test khác ứng với số điểm của bài có và có không quá giá trị khác ;
