폴리곤 게임은 다각형의 꼭지점과 선분을 이용하는 1 인용 게임이다. 처음 다각형의 N 개의 꼭지점과 선분이 주어진다.

아래 그림은 N = 4 일 때의 예이다.

각각의 꼭지점은 임의의 정수를 가지고 있으며 , 선분은 각각 +(덧셈)과 *(곱셈)이라는 정보를 가지고 있다. 모서리는 1 부터 N 까지 번호가 새겨져 있다.

게임을 시작하려면 가장 먼저 꼭지점을 연결하는 선분 중 임의의 하나를 없애야 한다. 다음부터 게임은 아래와 같이 진행된다.

한 선분 E 와 그것을 연결하고 있는 두 꼭지점 v₁,v₂를 선택한다. 다음, 이들을 하나의 꼭지점으로 대체한다. 거기에 들어가는 숫자는 v₁ 과 v₂ 꼭지점이 가진 수를 선분에 들어있던 연산자로 연산을 수행한 결과이다. 게임은 선분이 하나도 남지 않으면 끝난다. 그리고 점수는 마지막에 남은 꼭지점에 든 수이다.

그럼 위 다각형을 예로 들어 게임을 해 보자.

• 3 번 선분을 지우는 것으로 게임을 시작하자. 그러면 다각형은 아래 그림처럼 된다.

  

• 그리고 선분 1 을 잡는다.

  

• 다음은 선분 4,

  

• 마지막으로 선분 2 를 선택하여 게임이 끝났다. 점수는 0 점이다.

  

폴리곤의 정보를 입력으로 받아 게임을 했을 때 낼수 있는 가장 높은 점수를 계산하며, 그 점수를 내기 위해서 처음에 제거해야 하는 선분의 번호로 알맞는 것을 모두 출력하는 프로그램을 작성하라.

입력

• 첫 줄은 꼭지점 N (3 <= N <= 50) 의 개수이며,
• 다음 줄 부터는 선분의 연산자 정보와 선분 사이에 연결된 꼭지점이 가진 숫자가 번갈아 가며 나온다. 선분은 번호가 낮은 순이다. t 는 더하기를 , x 는 곱하기를 의미한다.

출력

• 첫 줄에는 반드시 이 폴리곤에서 낼 수 있는 최고 점수가 들어가야 한다.
• 두 번째 줄에는 최고 점수를 얻기 위해 제일 처음 없애야 하는 선분을 출력한다.

입출력 예

입력 

4
t -7 t 4 x 2 x 5

출력

33
1 2

출처: ioi 기출