내가 더 잘하겠다

문제

당신은 인기 모바일 게임 라스트 워의 플레이어이다. 현재 당신의 부대에는 단 1명의 병사가 있다.

앞으로 당신은 $N$개의 게이트를 순서대로 통과해야 한다. 각 게이트 앞에는 두 개의 선택지가 주어지며, 당신은 두 선택지 중 하나를 골라 현재 부대원 수를 변화시킬 수 있다. 선택지는 다음 두 가지 형태 중 하나이다.

• +A: 현재 부대원 수에 $A$명을 더한다.
• xB: 현재 부대원 수에 $B$를 곱한다. 이때 x는 알파벳 소문자이다.

게이트를 통과할 때마다 선택한 연산이 즉시 현재 부대원 수에 적용된다.

$N$개의 게이트 정보가 주어질 때, 모든 게이트를 순서대로 통과한 뒤 얻을 수 있는 최대 부대원 수를 구하라.

입력

첫째 줄에 게이트의 수 $N$이 주어진다. $(1 \le N \le 100,000)$

둘째 줄부터 $N$개의 줄에 걸쳐 각 게이트의 두 선택지가 공백 하나로 구분되어 주어진다.

각 선택지는 +A 또는 xB 형태의 문자열이다. $A$와 $B$는 앞에 불필요한 0이 붙지 않은 10진수 정수이다.

모든 선택을 최적으로 했을 때의 최종 부대원 수는 항상 $10^{18}$ 이하이다.

출력

모든 게이트를 통과한 뒤 얻을 수 있는 최대 부대원 수를 정수로 출력한다.

예제 입력 1

4
+10 x3
+50 x2
x3 +100
+1 +2

예제 출력 1

185

힌트

예제에서는 다음과 같이 선택하는 것이 최적이다.

1. 첫 번째 게이트에서 +10을 선택하여 부대원 수가 $1 + 10 = 11$이 된다.
2. 두 번째 게이트에서 +50을 선택하여 부대원 수가 $11 + 50 = 61$이 된다.
3. 세 번째 게이트에서 x3을 선택하여 부대원 수가 $61 \times 3 = 183$이 된다.
4. 네 번째 게이트에서 +2를 선택하여 부대원 수가 $183 + 2 = 185$가 된다.

따라서 최대로 얻을 수 있는 부대원 수는 $185$명이다.