Додека трае Македонската Олимпијада по информатика, на Факултетот за информатички науки и компјутерско инженерство (ФИНКИ) се спроведуваат колоквиуми по различни предмети. Притоа, разни професори, асистенти и демонстратори ги чуваат студентите додека тие ги полагаат предметите кои што сметаат дека ги научиле доволно добро.

Еден од најчудните професори на ФИНКИ е професорот Перо. Денес, кај него се спроведува испит по предметот Математика 11. Интересно, Перо толку добро може да ги процени студентите, што тој однапред знае како се наредени студентите во просторијата според нивното ниво на знаење (дали еден студент знае доволно за да го положи предметот или не).

На пример, нека иницијално студентите се сместени во 5 реда и 4 колони. На следната слика, студентите кои, според Перо, се доволно спремни за да го положат испитот се означени со црвена боја и ѕвездичка (*).

Перо сака да ги распореди учениците во просторијата така што, на одредено место во просторијата со правоаголна форма (поврзани соседни делови од редици и колони), ќе постои група од студенти доволно подготвени за да го положат испитот (сите во групата), и таквата група ќе содржи максимален можен број студенти. Така Перо ќе може подобро да внимава дали препишува некој од другите, помалку сигурни, студенти.

За да го постигне тоа, Перо пред почетокот на испитот може да направи промени од следниот вид: одбира две колони, и им наредува на сите студенти од едната колона да си ги заменат местата со сите студенти од другата колона (како целина, без преместување на редоследот на студентите во колоната - тој што седел во прв ред пак ќе седи во прв ред, итн). Перо може да прави неограничен број на вакви операции на преместување и смее да преместува одредени колони студенти и по повеќе пати.

Влез

Во првиот ред се запишани два цели броја R (4 ≤ R ≤ 10000) и C (4 ≤ C ≤ 2048), кои го означуваат бројот на редови и колони, соодветно.

Во секој од следните R редови се запишани по C знаци Sij, кои означуваат дали натпреварувачот кој седи во i-тиот ред и j-тата колона е доволно спремен за да го положи испитот (Sij='D'), или не (Sij='N').

(Забелешка: Поради големината на влезните податоци, доколку користите C++, потребно е да ставите ios::sync_with_stdio(false); на почетокот на вашата main() функција).

Излез

Отпечатете го бараниот максимален број на студенти.

Ограничувања

Временско ограничување: 450 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
5 4
NNND
DDDD
DDND
DDND
DDNN

излез
9

влез
4 6
NNNNNN
DDNNDD
DDNNDD
DDNNDD

излез
12

Објаснување за првиот пример: Доколку ја замениме првата (најлевата) колона со третата колона, ќе го добиеме распоредот прикажан на сликата.