忍者と忍者, または忍者と壁に挟まれた連続する\(k\)個の空きマスのことを, 「長さ\(k\)の隙間」と呼ぶことにします. 例えば ..#...#.##..という入力には, 長さが順に\(2,3,1,2\)の隙間があるものとします.

忍者どうしに挟まれた長さ\(k\)の隙間があるとき, この隙間に忍者を配置するためには「タイプA」の操作と「タイプB」の操作を合わせて\(k\)回以上行う必要があります. すなわち, \(x+y \geq k\)という制約が得られます. この形の制約は隙間の数だけ得られますが, そのうち最も厳しい(つまり\(k\)の値が大きい)ものだけを記録すれば十分です.

左端の壁と忍者の間に長さ\(l\)の隙間があるとき, この隙間は「タイプA」の操作でしか埋めることができません. 従って「タイプA」の操作が\(l\)回必要なので, \(x \geq l\)という制約が得られます. 右端に長さ\(r\)の隙間があるとき, 左端のパターンと同様にして\(y \geq r\)という制約が得られます.

以上より, 与えられた問題を以下の形に帰着させることができました.

\(x, y\)はともに非負整数であり, \(x \geq l, y \geq r, x+y \geq k\)を満たさなくてはならない. \(x+y\)が最小となる\((x, y)\)の組を1つ求めよ.

\((x, y) = (l, r)\)が条件を満たすとき, これが答えです. そうでないときは, \(x+y = k\)になるまで\(x\)または\(y\)を増やせばよくて, 例えば\((x, y) = (l, k-l)\)が答えです.