A. Advertere Augmento
time limit per test
0.5 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, Alice has come across an interesting game advertisement when scrolling through social media. The game involves a squad of soldiers going through gates with arithmetic operations that would apply to their fighting power.

The game advertisement.

Once she downloaded the game, she realized that the advertisement was fake and the actual gameplay was nowhere like what was portrayed in the ads. "What a pity!" She thought, "It would make a good mathematical game." Hence she decides to recreate one on her own.

The game she created is as follows:

  • The character starts with a Power Level of $$$0$$$.
  • There are $$$N$$$ stages. Each stage has a pair of Magic Gates.
  • The character needs to pass through the $$$N$$$ stages in order by choosing 1 of the 2 gates to pass through at each stage.
  • Each Magic Gate is associated with an arithmetic operation, for example, $$$+2$$$, $$$-(-3)$$$, $$$*7$$$. The operator must be one of add ($$$+$$$), subtract ($$$-$$$), or multiply ($$$*$$$), followed by an integer operand.
  • Passing through the magic gate would apply the operation onto the character's current Power Level, for example, a character with Power Level $$$7$$$ passing through a $$$+2$$$ magic gate would turn his Power Level into $$$7 + 2 = 9$$$.

It should be noted that different from the original game, the character is allowed to have a negative Power Level.

Given the configurations of all Magic Gates, could you figure out what is the maximum final Power Level that can be achieved after passing through all $$$N$$$ gates when selecting optimally?

Input

The first line consists of an integer, $$$N$$$, the number of stages the character has to pass through.

The following $$$N$$$ lines each denote the pair of Magic Gates at a stage, given in increasing distance from the starting position. The $$$i^{th}$$$ of the $$$N$$$ lines contains $$$4$$$ space-separated variables, $$$C_{i, 1}$$$, $$$V_{i, 1}$$$, $$$C_{i, 2}$$$ and $$$V_{i, 2}$$$.

$$$C_i$$$ is one of the following symbols + (addition), - (subtraction), * (multiplication), while $$$V_i$$$ is an integer. $$$C_{i, 1}$$$ $$$V_{i, 1}$$$ and $$$C_{i, 2}$$$ $$$V_{i, 2}$$$ represent the arithmetic operations on the two gates respectively.

The input guarantees that the Power Level of the character would not exceed the 32-bit integer range at any point in time no matter which gate is selected.

$$$1 \leq N \leq 10^5$$$, $$$-10^9 \leq V_{i, 1}, V_{i, 2} \leq 10^9$$$

Output

Output a single integer, the maximum final Power Level that can be achieved.

Examples
Input
3
+ 2 + 7
- 1 - 4
* 2 + 5
Output
12
Input
5
+ 1 + 1
* -1 * 2
+ -2 + 5
+ 5 - 3
* 1 * 3
Output
36
Input
2
- 1 - 1
+ 2 + 5
Output
4