#QY0002. 打翻的健胃消食片

打翻的健胃消食片

题目背景

小核桃挑选了一部分健胃消食片,一不小心手滑,打翻了。

题目描述

健胃消食片打翻了,散落在桌子上。现在需要找到一对平行线(可以是横着,竖着),使得这两条平行线之间的区域中,正面向上的健胃消食片数量最多且不包含反面向上的健胃消食片,并且这两条平行线不经过任何健胃消食片。

输入输出描述

输入

第一行一个正整数n,代表 n×nn \times n的范围。 接下来n行,每行n个字符,以空格隔开。表示健胃消食片的正反面情况。

输出

一个正整数,代表某两条平行线之间的区域中,最多的正面向上的健胃消食片数量

样例

3
u u d
u u d
u u u
6

样例说明

image

红色的两条平行线包含正面向上的健胃消食片最多。

数据规模与约定

对于100%的数据,保证 1n1001 \leq n \leq 100 。 所有数据均保证正确。