A. 军争 (war)

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

「因形而措胜于众,众不能知,人皆知我所以胜之形,而莫知吾所以制胜之形;故其战胜不复,而应形于无穷。」
—— 《孙子兵法·虚实》

话说春秋战国之际,楚国将以公输般制造的云梯攻宋,墨子听说这件事后,连夜赶赴楚国面见楚王制止战争。

墨子同两人一番唇枪舌剑,终于令楚王认识到了发动战争的不义,楚王诚恳认错,并表示:「你想怎样?」(「虽然,公输盘为我为云梯,必取宋。」)。

这令墨子意识到:不给他们 can 点好 can 的是不能摆平这茬了。于是他决定和公输般 van 个宽衣解带的小游戏,让楚王瞧瞧公输般的云梯到底能否攻下宋国王城。

墨子解下衣带置于地上,用手将其绕成一个想象中的环形城郭。他把城郭上的一些点指给公输般看,并约定只在这些地方进行攻防。同时,他也请楚王拿了宫中的一些木片给公输般,公输般可以用这些木片自由选择进攻的区域。最后,墨子规定:为了模拟战争迷雾,双方都只有一次做决策的机会,并在决策做出之前都不知道对方的决策。一旦双方决策都完成,便以决策既定的布局进行攻城的推演。

楚王听完规则后点了点头,游戏正式开始。公输般知道墨子善于守城,于是十分紧张地思考着应对策略:

城郭是一个环,把城郭上的关键点按照顺时针顺序以 编号,其中 与 互为相邻点。以他对城池结构的了解,他知道第 个点的防守价值是 。不过这是单独而言的:如果有一段连续的点同时被布防,将只有防守价值最大的那个点发挥其防守价值。 由于人力等限制,墨子将只能从 个城郭中至多选择 个进行布防,公输般知道墨子一定会选择一个防守价值和最大的防御方案,但是得到方案需要的计算量太大了,公输般还没来得及想完便草草决策,并在墨子的防守面前快速落败。

不过,由于某种阴差阳错,你穿越到了他们开始推演之前,身为究极乐子人,你能帮助公输般算出墨子布防的方案从而击败墨子吗?

输入格式

从标准输入读入数据。

第一行一个数 ,表示输出类型。

第二行两个正整数 , ,含义如题。

第三行 个整数,表示 ,含义如题。

输出格式

输出到标准输出中。

第一行一个整数,表示墨子布防方案的防御价值总和。

(如果 )第二行若干个整数,以空格分隔,表示墨子的布防点编号,如果有多种方案,输出任何一种。

样例

样例输入

0
3 2
1 1 -1

样例输出

1

数据范围与提示

对于前 的数据,。

对于前 的数据,。

对于所有数据,,,保证输入中的所有数据在 int 范围内。