Byteasar là một hacker có nhiều năng lực đã lọt vào kì thi Olympiad Hacking quốc tế năm nay (IHO). Một trong các bài toán của kỳ thi này liên quan tới việc thi đấu giữa hacker với nhà điều hành hệ thống: Có máy tính được đánh số từ đến , nối với nhau theo mạch vòng, nghĩa là máy tính và nối với nhau và máy tính nối với máy . Việc thi đấu được thực hiện như một trò chơi giữa hacker và nhà điều hành hệ thống:
Byteasar được đi trước. Sau đó là nhà điều hành và Byteasar luân phiên nhau.
Trong bước đầu tiên, Byteasar chọn một máy tính và hack nó.
Trong bước đầu tiên, nhà điều hành hệ thống chọn một máy tính chưa bị hack và bảo vệ nó.
Trong mọi bước đi tiếp theo, Byteasar hoặc là:
không làm gì, hoặc là
chọn một máy tính chưa bị hack và chưa được bảo vệ, đồng thời phải liên kết trực tiếp tới một máy tính đã bị hack để hack nó.
Trong mọi bước đi tiếp theo, nhà điều hành hoặc là:
không làm gì, hoặc là
chọn một máy tính chưa bị hack và chưa được bảo vệ, đồng thời phải liên kết trực tiếp tới một máy tính đã được bảo vệ để bảo vệ nó.
Trò chơi kết thúc ngay khi cả hai không làm gì trong hai bước liên tiếp.
Ban đầu, không có máy tính nào bị hack hoặc được bảo vệ. Mỗi máy tính có một giá trị là xác định giá trị của dữ liệu chứa trong nó. Khi máy tính bị hack, Byteasar chiếm được điểm.
Byteasar là một hacker rất khá, nhưng nó không có ý tưởng về thuật toán. Vì thế nó muốn bạn viết giúp một chương trình tính số điểm lớn nhất có thể chiếm được, giả sử nhà điều hành chơi tối ưu.
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên , là số máy tính ;
Dòng thứ hai chứa dãy số nguyên ; số xác định giá trị dữ liệu chứa trên máy tính .
Dữ liệu ra:
In ra điểm lớn nhất mà Byteasar đạt được khi nhà điều hành chơi tối ưu.
Ví dụ:
Dữ liệu vào:
4
7 6 8 4
Dữ liệu ra:
13
Dữ liệu vào:
5
1 1 1 1 1
Dữ liệu ra:
3
Giải thích:
Trong ví dụ thứ nhất, đầu tiên Byteasar hack máy tính (được điểm). Nhà điều hành sẽ bảo vệ máy tính . Bước tiếp theo Byteasar hack máy tính (được thêm điểm). Cuối cùng nhà điều hành bảo vệ máy tính .
Giới hạn:
Subtask ;
Subtask ;
Subtask , hack máy là bước đi tối ưu của Byteasar;
