I. Irritating Interruption II
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output
The high-quality multi-army version of the game, sporting many polygons and at least one texture that is definitely not a rendering artefact.

Tonias has successfully determined that the last mobile game ad he looked at was a total scam. He has managed to get back on track with his thesis, and is determined to not get distracted again.

He will just take a 5-minute break.

...

Do you know those mobile game ads where you control an army that must repeatedly choose between different gates, each applying a mathematical operation to the army's strength (such as $$$\times 3$$$, $$$+10$$$ or $$$-4$$$)?

Tonias is now stuck playing the multi-army version: He starts with $$$k$$$ armies, each with a strength of $$$1$$$. In each round, a mathematical operation ($$$+$$$ or $$$\times$$$) is given, along with $$$k$$$ gates displaying their corresponding integers.

Each of the armies must go through a different gate. When an army goes through a gate with value $$$a$$$, the army's strength is either increased or multiplied by $$$a$$$ (depending on the operation of that round). Your objective is to help Tonias maximize the sum of strengths of all his armies after all rounds, so he can get back to his thesis.

Input

The input consists of:

  • One line with two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n\cdot k \leq {10^4}$$$), the number of rounds and the number of armies.
  • $$$n$$$ lines, each containing an operator (either '+' or '*') and $$$k$$$ integers $$$a$$$ ($$${0} \leq a \leq {10^{12}}$$$), the value of each gate in this round.
It is guaranteed that, for any given input, no army strength can ever exceed $$${10^{12}}$$$.
Output

Output the maximum achievable sum of strengths of the armies.

Examples
Input
3 1
+ 3
* 10
+ 2
Output
42
Input
3 3
+ 1 2 3
* 3 2 2
+ 7 6 7
Output
42