# Tiny Forest

Difficulty : Medium

Community success rate: 72%

Approved by Timinator llllllllllllllllllllllllllllll FredericLocquet

A higher resolution is required to access the IDE

- 40

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Statement

## Goal

You have just inherited of a small plot of land of width`W`and height

`H`with some trees on it. You want to grow a forest, but you have only

**Rules:**

-Seeds need 10 years to grow into a tree.

-Trees produce 4 seeds around them after one year.

-Trees may already be present on your land. They will also produce seeds after one year.

**Year 0**: X is your one and only seed and Y is a tree already present.

. . . . .

. X . . .

. . . . .

. . . . .

. . . . Y

**Year 1**: Trees produce seeds after one year.

. . . . .

. X . . .

. . . . .

. . . . X

. . . X Y

**Year 10**: Your seed is now a tree. Congratulations!

. . . . .

. Y . . .

. . . . .

. . . . X

. . . X Y

**Year 11**: Your new tree starts to produce seeds after a year.

. X . . .

X Y X . .

. X . . .

. . . . Y

. . . Y Y

**Year 12**: The old trees in the corner also keep spreading.

. X . . .

X Y X . .

. X . . X

. . . X Y

. . X Y Y

**Year 33**: Finally you have a tiny forest of 21 trees!

Y Y Y X .

Y Y Y Y Y

Y Y Y Y Y

X Y Y Y Y

. Y Y Y Y

Maybe if you plant the seed at another place you can get a bigger forest in the end.

When you will find the best place, you will need to give the number of trees you get after 33 years.

Input

**Line 1**: an integer

`W`for the width of the parcel.

**Line 2**: an integer

`H`for the height of the parcel.

**Next**: each line of the land, with trees (

`H`linesOutput

**Line 1**: an integer

`N`for the number of trees you can have on your land after

Constraints

1 <=

1 <=

`W`<= 401 <=

`H`<= 40Example

Input

5 5 ..... ..... ..... ..... .....

Output

13

A higher resolution is required to access the IDE