问题描述

Polygon 是一个单人游戏，初始时有一个由 $N$ 个顶点组成的多边形（例如图1中 $N=4$ 的情况）。每个顶点标有一个整数，每条边标有符号 $+$（加法）或 $*$（乘法）。边的编号为 $1$ 到 $N$。

编写一个程序，给定一个多边形，计算可能的最高得分，并列出所有在第一步移除后能导致该得分的边。

输入

程序从标准输入读取数据。输入描述一个 $N$ 个顶点的多边形，包含两行：

• 第一行是顶点数 $N$。
• 第二行按顺序交替给出边的符号和顶点的数值（先给出边 $1$ 和边 $2$ 之间的顶点数值，然后是边 $2$ 和边 $3$ 之间的顶点数值，依此类推，最后是边 $N$ 和边 $1$ 之间的顶点数值），所有值用空格分隔。边的符号用字母 t（代表 $+$）或 x（代表 $*$）表示。

约束条件：

• $3 \leq N \leq 50$
• 顶点的数值范围在 $[-32768, 32767]$ 之间。

输出

程序输出到标准输出：

1. 第一行输出该多边形能获得的最高得分。
2. 第二行输出所有在第一步移除后能导致该最高得分的边的编号，按升序排列，用空格分隔。

示例输入 1

4
t -7 t 4 x 2 x 5

示例输出 1

33
1 2

数学表示

• 多边形的边和顶点交替排列，例如，输入 t -7 t 4 x 2 x 5 表示：

  • 边 $1$：t（$+$）
  • 顶点 $1$：$-7$
  • 边 $2$：t（$+$）
  • 顶点 $2$：$4$
  • 边 $3$：x（$*$）
  • 顶点 $3$：$2$
  • 边 $4$：x（$*$）
  • 顶点 $4$：$5$

• 游戏规则：每次移除一条边，并按边的运算符合并相邻的两个顶点，直到只剩一个顶点，该顶点的值即为得分。目标是找到所有可能的移除顺序，使得最终得分最大。

示例解释

在示例中，最高得分为 $33$，可以通过第一步移除边 $1$ 或边 $2$ 实现。因此输出：

33
1 2