{"code":"olp4ck1c2b","name":"Vòng tròn số","description":"Đan mới tạo ra một trò chơi trên một vòng tròn số như sau: Ban đầu máy tính sẽ tạo ngẫu nhiên $n$ số nguyên $a_{0}, a_{1}, \\ldots, a_{n - 1}$ và xếp lần lượt từng số lên vòng tròn theo chiều kim đồng hồ (xem ví dụ dưới đây cho vòng tròn 8 số). \r\n\r\n![enter image description here][1]\r\n\r\nNgười chơi sẽ vào vai là một chú thỏ và thực hiện các hành động:\r\n\r\nBan đầu chú thỏ sẽ chọn một vị trí $s\\ (0 \\leq s < n)$ để xuất phát. \r\n\r\nSau đó, chú thỏ sẽ thực hiện $k$ lần nhảy $123$ bắt đầu từ $s$ theo chiều kim đồng hồ trên vòng tròn. Các vị trí tương ứng với bước nhảy $1, 3$ chú thỏ sẽ được cộng điểm là số tại vị trí đó, các vị trí tương ứng với bước nhảy $2$ chú thỏ bị trừ điểm là số tương ứng tại vị trí đó. Chú thỏ cần tìm cách nhảy để đạt được nhiều điểm nhất.\r\n\r\nVí dụ, trong hình trên, với $s = 1$ và $k = 2$, ba số được tô màu đỏ $(a_{1}, a_{3}, a_{4})$ tương ứng với lần nhảy $123$ thứ nhất, ba số được tô màu xanh $(a_{5}, a_{7}, a_{0})$ tương ứng lần nhảy thứ hai. \r\n\r\nTổng điểm chú thỏ nhận được là: $(a_{1} - a_{3} + a_{4}) + (a_{5} - a_{7} + a_{0})$.\r\n\r\nMột cách hình thức: Nếu tạo dãy gồm $n$ số bắt đầu từ phần tử thứ $s$ theo chiều kim đồng hồ ta nhận được dãy $b_{0}, b_{1}, \\ldots, b_{n - 1}$, trong đó $b_{0} = a_{s}, b_{1} = a_{(s + 1) \\% n}, \\ldots, b_{n - 1} = a_{(s + n - 1) \\% n}$. Khi đó, cần tìm các chỉ số $0 \\leq x_{1} < y_{1} < z_{1} < x_{2} < y_{2} < z_{2} < \\ldots < x_{k} < y_{k} < z_{k} \\leq n - 1$ để tổng: $(b_{x_{1}} - b_{y_{1}} + b_{z_{1}}) + (b_{x_{2}} - b_{y_{2}} + b_{z_{2}}) + \\ldots + (b_{x_{k}} - b_{y_{k}} + b_{z_{k}})$ đạt giá trị lớn nhất.\r\n\r\n**Yêu cầu:** Cho vòng tròn số và số nguyên dương $k$, tính điểm lớn nhất có thể đạt được.\r\n\r\n## Input\r\n\r\n- Dòng đầu chứa hai số nguyên dương $n, k$ $(3 \\times k \\leq n)$.\r\n- Dòng thứ hai chứa $n$ số nguyên $a_{0}, a_{1}, \\ldots, a_{n - 1}$ $(|a_{i}| \\leq 10^{9}$ với $0 \\leq i \\leq n - 1)$.\r\n \r\n## Output \r\n- Ghi ra thiết bị ra chuẩn một số nguyên là giá trị tổng điểm lớn nhất đạt được.\r\n\r\n## Scoring\r\n- Subtask $1$ ($20\\%$ số điểm): $n \\leq 20, k = 1$.\r\n- Subtask $2$ ($20\\%$ số điểm): $n \\leq 20$.\r\n- Subtask $3$ ($20\\%$ số điểm): $n \\leq 2000, k = 1$.\r\n- Subtask $4$ ($20\\%$ số điểm): $n \\leq 200$.\r\n- Subtask $5$ ($20\\%$ số điểm): $n \\leq 2000$.\r\n\r\n## Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        8 2\r\n        1 1 0 -1 1 1 0 -1\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        6\r\n        ```\r\n\r\n  [1]: https://i.imgur.com/EcM89Re.png","points":1300.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}