לפרות יש מערכת לייזר חדשה לשיחות מזדמנות במרעה, המיוצג כסריג של $W \times H$ נקודות ($1 \le W \le 100; 1 \le H \le 100$).

המערכת דורשת מעין חיבור בקו ראייה כדי לקיים תקשורת. סלעים ועצים מפריעים לה, אך הפרות קנו מראות אלכסוניות (/ ו-\ להלן) המסיטות את קרן הלייזר ב-$90$ מעלות. המפה הבאה ממחישה את הבעיה.

במפה זו $H=8$ ו-$W=7$. שתי הפרות המתקשרות מסומנות $C$; סלעים ומכשולים אחרים מסומנים *:

7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . \-------/ .
  0 1 2 3 4 5 6           0 1 2 3 4 5 6

מצאו את המספר המזערי של מראות $M$ שיש להתקין כדי לקיים תקשורת לייזר בין שתי הפרות. בנתוני הבדיקה הנתונים הדבר תמיד אפשרי.

קלט

• שורה 1: שני שלמים המופרדים ברווח: $W$ ו-$H$.
• שורות $2,\ldots,H+1$: המרעה כולו.

פלט

• שורה 1: שלם יחיד $M$.

דוגמאות

קלט 1

7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

פלט 1

3

קרדיט לבעיה: Rob Kolstad, 2008