Popular among the most traditional coders, the Summer Camp is famous for its fancy parties. After each party all attendees must return to their homes, but the way back home is not always easy: mildly drunk coders walk weird and often find or lose money along the way. However, MaratonIME always has a sober member in the group, who assures no one will lose money, except when they are robbed.
On its way back MaratonIME knows that they can call their coach, Renzo, who will pick them up immediately. Instead of doing that right after the party, they want to know what is the maximum amount of money they can carry back to their homes.
Your task is to write a program that solves this problem. Consider the following facts:
The first line of the input contains two integers N and M (1 ≤ N, M ≤ 103), respectively, the number of rows and columns of the grid. Then follows N lines, each containing M characters, representing the city map. Each cell of the city map can be either:
The output must contain a single integer: the maximum amount of money MaratonIME can carry back home.
In the example above, MaratonIME follows the following path: (1, 1) (1, 2) (1, 3) (2, 3) (2, 2) (2, 1) (3, 1) (3, 2) (3, 3). When they reach (2, 2) or (2, 1) they will have 2 coins, and that is the highest value they can get before calling Renzo.
## Input
The first line of the input contains two integers N and M (1 ≤ N, M ≤ 103), respectively, the number of rows and columns of the grid. Then follows N lines, each containing M characters, representing the city map. Each cell of the city map can be either: , meaning there is nothing at this cell of the grid; , meaning there is a coin worth 1 unit of money at this cell; , meaning there is a burglar at that cell.
## Output
The output must contain a single integer: the maximum amount of money MaratonIME can carry back home.
[samples]
## Note
In the example above, MaratonIME follows the following path: (1, 1) (1, 2) (1, 3) (2, 3) (2, 2) (2, 1) (3, 1) (3, 2) (3, 3). When they reach (2, 2) or (2, 1) they will have 2 coins, and that is the highest value they can get before calling Renzo.
**Definitions**
Let $ N \in \mathbb{Z} $ with $ 2 \leq N \leq 300 $ be the number of terms.
Let $ A = (a_1, a_2, \dots, a_N) $ be a sequence of integers with $ 1 \leq a_i \leq 300 $.
Let $ o_i \in \{+, -\} $ for $ i = 1, \dots, N-1 $ be the operator between $ a_i $ and $ a_{i+1} $, initially given.
Define the evaluated value of the equation as:
$$
S = a_1 \oplus_1 a_2 \oplus_2 a_3 \oplus_3 \cdots \oplus_{N-1} a_N
$$
where $ \oplus_i $ is the operator at position $ i $.
Let $ S_{\text{target}} = 0 $ (the equation is correct if it evaluates to zero).
**Constraints**
- The first term $ a_1 $ has no preceding operator.
- Each operator $ \oplus_i $ can be flipped from its initial value at a cost of 1.
- Operators cannot be removed or inserted; only replaced.
**Objective**
Find the minimum number of operator flips required such that $ S = 0 $.
If impossible, return $ -1 $.