#include <stdio.h>

#define opSum 't'
#define opPro 'x'
#define maxVert 50

typedef struct {
    char vert[maxVert];
    int side[maxVert];
    int numVert;
  } polygonT;

typedef struct {
    int maxVal, minVal;
  } maxminT;

typedef maxminT memoryT[maxVert][maxVert];

typedef struct {
    int scor[maxVert], numVert, highScor, firstVertHS;
  } scoresT;


void ReadPolygon (FILE *F, polygonT *P)
{ int i;

  fscanf(F, "%d", &P->numVert);
  for (i = 0; i < P->numVert; i++)
    fscanf(F, "%1s %d", &P->vert[i], &P->side[i]);
}


void Evaluate (char Op, maxminT E1, maxminT E2, maxminT *MM)
{ int values[4], i, indMax, indMin;

  switch (Op)
    {  case opSum: MM->maxVal = E1.maxVal + E2.maxVal;
                   MM->minVal = E1.minVal + E2.minVal;
		   break;
       case opPro: values[0] = E1.maxVal * E2.maxVal;
                   values[1] = E1.maxVal * E2.minVal;
		   values[2] = E1.minVal * E2.maxVal;
		   values[3] = E1.minVal * E2.minVal;
		   indMax = indMin = 0;
		   for (i = 1; i < 4; i++)
		     if (values[i] > values[indMax])
		       indMax = i;
		     else if (values[i] < values[indMin])
		       indMin = i;
		   MM->maxVal = values[indMax];
		   MM->minVal = values[indMin];
		   break;
     }
}


void CompScores (polygonT *P, memoryT M)
{ int line, inf, infRight, dimLeft;
  maxminT mmTemp, mmAux;

  /* Line 0 --- expressions with one integer */
  for (inf = 0; inf < P->numVert; inf++)
    M[0][inf].maxVal = M[0][inf].minVal = P->side[inf];

  /* Line 1 --- expressions with two integers */
  for (inf = 0; inf < P->numVert; inf++)
    {  infRight = (inf + 1) % P->numVert;
       if (P->vert[infRight] == opSum)
         M[1][inf].maxVal = M[0][inf].maxVal + M[0][infRight].maxVal;
       else
         M[1][inf].maxVal = M[0][inf].maxVal * M[0][infRight].maxVal;
       M[1][inf].minVal = M[1][inf].maxVal;
    }

  /* Line 2 ... Line P->numVert - 1 */
  for (line = 2; line < P->numVert; line++)
    for (inf = 0; inf < P->numVert; inf++)
      { infRight = (inf + 1) % P->numVert;
        Evaluate(P->vert[infRight], M[0][inf], M[line-1][infRight], &mmTemp);
	for (dimLeft = 2; dimLeft <= line; dimLeft++)
	  { infRight = (inf + dimLeft) % P->numVert;
	    Evaluate(P->vert[infRight],
	    M[dimLeft-1][inf], M[line-dimLeft][infRight], &mmAux);
	    if (mmAux.maxVal > mmTemp.maxVal)
	      mmTemp.maxVal = mmAux.maxVal;
	    if (mmAux.minVal < mmTemp.minVal)
	      mmTemp.minVal = mmAux.minVal;
	  }
	M[line][inf] = mmTemp;
      }
}


void CompHighScores (polygonT *P, scoresT *S)
{ memoryT mem;
  int i, lastVert, maxScor, fstVert;

  CompScores(P, mem);
  lastVert = P->numVert - 1;
  maxScor = S->scor[0] = mem[lastVert][0].maxVal;
  fstVert = 0;
  for (i = 1; i < P->numVert; i++)
    if ((S->scor[i] = mem[lastVert][i].maxVal) > maxScor)
      { maxScor = S->scor[i];
        fstVert = i;
      }
  S->numVert = P->numVert;
  S->highScor = maxScor;
  S->firstVertHS = fstVert;
}


void WriteResults (FILE *F, scoresT *S)
{ int i;

  fprintf(F, "%d\n", S->highScor);
  fprintf(F, "%d", S->firstVertHS + 1);
  for (i = S->firstVertHS + 1; i < S->numVert; i++)
    if (S->scor[i] == S->highScor)
      fprintf(F, " %d", i + 1);
  fprintf(F, "\n");
}


void main()
{ FILE *fileIn, *fileOut;
  polygonT polygon;
  scoresT  scores;

  fileIn = fopen("POLYGON.IN", "r");
  ReadPolygon(fileIn, &polygon);
  fclose(fileIn);
  CompHighScores(&polygon, &scores);
  fileOut = fopen("POLYGON.OUT", "w");
  WriteResults(fileOut, &scores);
  fclose(fileOut);
}