Dương Qua là một người rất thông minh. Anh đã xuất sắc hoàn thành tốt phần thi của mình trong trò chơi mà ban tổ chức trường THPT Chuyên đề ra. Để quyết định giá trị phần thưởng của mình, ban tổ chức quyết định tạo ra một trò chơi phụ dành cho Qua. Trò chơi của Qua có tên là XOADAY. Trò chơi sẽ có một dãy nhị phân \(s\) gồm \(n\) phần tử và một dãy số \(D\) gồm \(n\) phần tử. Nhiệm vụ của Qua đó là xoá dãy nhị phân trên theo quy luật sau:

• Tại mỗi bước chơi, chọn xoá \(x\) phần tử liền kề giống nhau trong dãy nhị phân \(s\) ( \(x < |s|\)) Ví dụ : 1001101 => 11101.
• Số điểm nhận được là \(D[x]\).
• Trò chơi sẽ tiếp tục cho đến khi dãy \(s\) hết phần tử.
• Điểm càng cao thì giá trị phần thưởng càng lớn

Qua thực sự đã rất mệt trong phần thi trước đấy của mình nhưng anh cũng muốn giành được số điểm cao nhất để lấy có được phần thưởng lớn nhất. Dương Qua rất cần đến sự giúp đỡ của các bạn học sinh. Hãy giúp đỡ Duong Qua nhé!

Yêu cầu:

• In ra số điểm cao nhất mà Qua có thể đạt được sau phần chơi.

Dữ liệu vào:

• Dòng thứ nhất là số \(n\).
• Dòng thứ hai là dãy nhị phần có \(n\) phần tử gồm các số \(0\) và \(1\).
• Dòng thứ ba là dãy số \(D\).

Output:

• In ra kết quả bài toán.

Scoring:

• Subtask \(1\) (\(6\) tests, bao gồm test đề):​ \(n ≤ 9\)
• Subtask \(2\) (\(10\) tests):​ \(n ≤ 100\)
• Subtask \(3\):​ \(n ≤ 1000\), cả dãy s chỉ bao gồm 1 giá trị

5
10101
3 10 15 15 15

23