CUTSEG - Rút gọn đoạn

Giới hạn
  • Thời gian: 0.429s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 7000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Cho một dãy gồm N chữ số thuộc đoạn 0..9 (N<=200). Ở mỗi bước, ta có thể lấy ra từ dãy này một đoạn liên tiếp các chữ số giống nhau và nhận được một số tiền bằng bình phương độ dài của đoạn được lấy ra. Nếu sau khi lấy, dãy đã cho bị tách làm 2 dãy con, 2 dãy con này lập tức được sát nhập lại thành 1 ( giữ nguyên thứ tự ).
Hãy tính số lượng tiền lớn nhất có thể thu được.

Input

Dòng đầu ghi số N. Dòng thứ hai ghi N chữ số thể hiện dãy.

Output

Ghi ra số lượng tiền lớn nhất có thể thu được.

Example 

Input:
6
100011

Output:
18

  • Người up: beo_map
  • Nguồn bài: Một bài của đội tuyển Ðà Nẵng