唔西迪西现在正处在一个冰火迷宫中，迷宫由  个格子组成，每个格子要么是冰之格，要么是火之格，唔西迪西刚开始可以选择从迷宫中任意一个开始走，走到第  个位置时会得到值为  的积分。（注意：唔西迪西也可以选择一个格子都不走）

如果唔西迪西当前在冰之格，那么她可以选择一个编号大于当前格子的冰之格，跳到那里。如果唔西迪西当前在火之格，那么她可以选择一个编号大于当前格子的火之格，跳到那里。如果唔西迪西目前没有格子可以走，那么结束。同时，即使存在可以跳过去的格子，唔西迪西也可以选择在任意时刻结束。

唔西迪西想最大化她的得分，于是她学会了一个超能力，她能在比赛开始的时候改变最多  个格子的状态，即将一个格子从冰之格变成火之格或从火之格变成冰之格，改变第  个格子的状态会让唔西迪西的得分减少  。（唔西迪西改变格子的状态后才开始挑选起点开始行动，也就是说，得分分成两部分，一部分是改变格子状态的得分，一部分是走格子的得分）