#P1792. [国家集训队] 种树

[国家集训队] 种树

题目描述

A城市有一个巨大的圆形广场,为了绿化环境和净化空气,市政府决定沿圆形广场外圈种一圈树。

园林部门得到指令后,初步规划出 nn 个种树的位置,顺时针编号 11nn。并且每个位置都有一个美观度 AiA_i,如果在这里种树就可以得到这 AiA_i 的美观度。但由于 AA 城市土壤肥力欠佳,两棵树决不能种在相邻的位置(ii 号位置和 i+1i+1 号位置叫相邻位置。值得注意的是 11 号和 nn 号也算相邻位置)。

最终市政府给园林部门提供了 mm 棵树苗并要求全部种上,请你帮忙设计种树方案使得美观度总和最大。如果无法将 mm 棵树苗全部种上,给出无解信息。

输入格式

输入的第一行包含两个正整数 nnmm

第二行 nn 个整数,第 ii 个代表 AiA_i

输出格式

输出一个整数,表示最佳植树方案可以得到的美观度。如果无解输出 Error!

7 3
1 2 3 4 5 6 7
15
7 4
1 2 3 4 5 6 7
Error!

提示

数据编号 nn 的大小 数据编号 nn 的大小
11 3030 1111 200200
22 3535 1212 20072007
33 4040 1313 20082008
44 4545 1414 20092009
55 5050 1515 20102010
66 5555 1616 20112011
77 6060 1717 20122012
88 6565 1818 199999199999
99 200200 1919
1010 2020 200000200000

对于全部数据:mnm\le n1000Ai1000-1000\le A_i\le1000