시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 75 12 10 50.000%

문제

상근이의 농장은 매우 넓기 때문에, 어떤 곳에 어떤 식물을 심었는지를 기록해 놔야 한다. 상근이는 기록을 위해 인터넷 쇼핑몰에서 고화질 지도를 주문했다. 지도는 매우 크기 때문에, 종이 한 장이 인쇄할 수 없다. 따라서, 지도를 쪼개 종이 여러 장에 인쇄를 해야 한다.

동일한 지도를 어떻게 놓느냐에 따라 필요한 종이의 개수가 달라질 수도 있다. 상근이의 정원의 지도와 종이의 크기가 주어졌을 때, 지도를 인쇄하는데 필요한 종이 개수의 최소값을 구하는 프로그램을 작성하시오.

위의 그림은 텍사스처럼 생긴 지도를 인쇄하는 두 가지 방법이다. 첫 번째 그림은 종이 14개로 인쇄하는 방법이고, 오른쪽은 같은 지도를 동일한 종이 10개로 인쇄하는 방법이다.

종이의 변은 모두 x축과 y축에 평행해야 한다. 또, 종이는 회전시킬 수 없고, 두 종이가 전체 변을 공유하는 경우에만 접할 수 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 Ar, Ac, Tr, Tc가 주어진다. Ar과 Ac는 지도의 픽셀 개수이고, Tr과 Tc는 종이 한 장에 인쇄할 수 있는 픽셀의 개수이다. (1 ≤ Ax ≤ 1000, 1 ≤ Tx ≤ 100) 다음 Ar개 줄에는 Ac개의 문자가 주어진다. 'X'는 상근이의 농장, '.'는 상근이의 농장이 아닌 곳이다.

모든 X를 종이에 인쇄해야 하며, 지도의 'X'는 모두 같은 영역에 속한다.

출력

각 테스트 케이스마다, 모든 'X'를 종이에 인쇄하는데 필요한 종이 개수의 최소값을 출력한다.

예제 입력 1

3 3 2 2
XXX
XXX
XXX
3 3 2 2
XX.
XXX
XXX
17 32 5 9
........XXXXXXXX................
........XXXXXXXX................
........XXXXXXXX................
........XXXXXXXXX...............
........XXXXXXXXXXXXXXX.........
........XXXXXXXXXXXXXXXXXXXX....
........XXXXXXXXXXXXXXXXXXXXX...
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..
..XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.
....XXXXXXXXXXXXXXXXXXXXXXXXXXX.
......XXXXXXXXXXXXXXXXXXXXXXXXX.
........XX..XXXXXXXXXXXXXXXXX...
.............XXXXXXXXXXXXXX.....
...............XXXXXXXXX........
................XXXXXXX.........
.................XXXXX..........
....................XXX.........

예제 출력 1

4
3
10
W3sicHJvYmxlbV9pZCI6IjkyNzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4ODVcdWM3NzQgXHVjOWMwXHViM2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHViMThkXHVjN2E1XHVjNzQwIFx1YjllNFx1YzZiMCBcdWIxMTNcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM1YjRcdWI1YTQgXHVhY2YzXHVjNWQwIFx1YzViNFx1YjVhNCBcdWMyZGRcdWJiM2NcdWM3NDQgXHVjMmVjXHVjNWM4XHViMjk0XHVjOWMwXHViOTdjIFx1YWUzMFx1Yjg1ZFx1ZDU3NCBcdWIxOTRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhZTMwXHViODVkXHVjNzQ0IFx1YzcwNFx1ZDU3NCBcdWM3NzhcdWQxMzBcdWIxMzcgXHVjMWZjXHVkNTUxXHViYWIwXHVjNWQwXHVjMTFjIFx1YWNlMFx1ZDY1NFx1YzljOCBcdWM5YzBcdWIzYzRcdWI5N2MgXHVjOGZjXHViYjM4XHVkNTg4XHViMmU0LiBcdWM5YzBcdWIzYzRcdWIyOTQgXHViOWU0XHVjNmIwIFx1ZDA2Y1x1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1Yzg4NVx1Yzc3NCBcdWQ1NWMgXHVjN2E1XHVjNzc0IFx1Yzc3OFx1YzFjNFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzljMFx1YjNjNFx1Yjk3YyBcdWNhYmNcdWFjMWMgXHVjODg1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWM3YTVcdWM1ZDAgXHVjNzc4XHVjMWM0XHViOTdjIFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNkOVx1Yzc3Y1x1ZDU1YyBcdWM5YzBcdWIzYzRcdWI5N2MgXHVjNWI0XHViNWJiXHVhYzhjIFx1YjE5M1x1YjI5MFx1YjBkMFx1YzVkMCBcdWI1MzBcdWI3N2MgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHViMmVjXHViNzdjXHVjOWM4IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWM4MTVcdWM2ZDBcdWM3NTggXHVjOWMwXHViM2M0XHVjNjQwIFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjOWMwXHViM2M0XHViOTdjIFx1Yzc3OFx1YzFjNFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjODg1XHVjNzc0IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZm1hcC5wbmdcIiBzdHlsZT1cImhlaWdodDoyMTBweDsgbGluZS1oZWlnaHQ6MS42ZW07IG9wYWNpdHk6MC45OyB3aWR0aDo0NTdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNzQwIFx1ZDE0ZFx1YzBhY1x1YzJhNFx1Y2M5OFx1YjdmYyBcdWMwZGRcdWFlMzQgXHVjOWMwXHViM2M0XHViOTdjIFx1Yzc3OFx1YzFjNFx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVhYzAwXHVjOWMwIFx1YmMyOVx1YmM5NVx1Yzc3NFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjODg1XHVjNzc0IDE0XHVhYzFjXHViODVjIFx1Yzc3OFx1YzFjNFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzRcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1Yzc0MCBcdWFjMTlcdWM3NDAgXHVjOWMwXHViM2M0XHViOTdjIFx1YjNkOVx1Yzc3Y1x1ZDU1YyBcdWM4ODVcdWM3NzQgMTBcdWFjMWNcdWI4NWMgXHVjNzc4XHVjMWM0XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODg1XHVjNzc0XHVjNzU4IFx1YmNjMFx1Yzc0MCBcdWJhYThcdWI0NTAgeFx1Y2Q5NVx1YWNmYyB5XHVjZDk1XHVjNWQwIFx1ZDNjOVx1ZDU4OVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHVjODg1XHVjNzc0XHViMjk0IFx1ZDY4Y1x1YzgwNFx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNWM2XHVhY2UwLCBcdWI0NTAgXHVjODg1XHVjNzc0XHVhYzAwIFx1YzgwNFx1Y2NiNCBcdWJjYzBcdWM3NDQgXHVhY2Y1XHVjNzIwXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjljYyBcdWM4MTFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBBPHN1Yj5yPFwvc3ViPiwgQTxzdWI+YzxcL3N1Yj4sIFQ8c3ViPnI8XC9zdWI+LCBUPHN1Yj5jPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIEE8c3ViPnI8XC9zdWI+XHVhY2ZjIEE8c3ViPmM8XC9zdWI+XHViMjk0IFx1YzljMFx1YjNjNFx1Yzc1OCBcdWQ1M2RcdWMxNDAgXHVhYzFjXHVjMjE4XHVjNzc0XHVhY2UwLCBUPHN1Yj5yPFwvc3ViPlx1YWNmYyBUPHN1Yj5jPFwvc3ViPlx1YjI5NCBcdWM4ODVcdWM3NzQgXHVkNTVjIFx1YzdhNVx1YzVkMCBcdWM3NzhcdWMxYzRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ1M2RcdWMxNDBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiAoMSAmbGU7IEE8c3ViPng8XC9zdWI+ICZsZTsgMTAwMCwgMSAmbGU7IFQ8c3ViPng8XC9zdWI+ICZsZTsgMTAwKSBcdWIyZTRcdWM3NGMgQXJcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IEFjXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICYjMzk7WCYjMzk7XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWIxOGRcdWM3YTUsICYjMzk7LiYjMzk7XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWIxOGRcdWM3YTVcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YWNmM1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFhcdWI5N2MgXHVjODg1XHVjNzc0XHVjNWQwIFx1Yzc3OFx1YzFjNFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1YzljMFx1YjNjNFx1Yzc1OCAmIzM5O1gmIzM5O1x1YjI5NCBcdWJhYThcdWI0NTAgXHVhYzE5XHVjNzQwIFx1YzYwMVx1YzVlZFx1YzVkMCBcdWMxOGRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQsIFx1YmFhOFx1YjRlMCAmIzM5O1gmIzM5O1x1Yjk3YyBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVjNzc4XHVjMWM0XHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM4ODVcdWM3NzQgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTI3NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZvbGRlZCBNYXAiLCJkZXNjcmlwdGlvbiI6IjxwPkZyZWRkeSZyc3F1bztzIGdhcmRlbiBiZWNhbWUgc28gbGFyZ2UgdGhhdCBoZSBuZWVkcyBhIG1hcCB0byBrZWVwIGV2aWRlbmNlIG9mIHdoaWNoIHZlZ2V0YWJsZXMgYXJlIHBsYW50ZWQgaW4gd2hhdCBhcmVhLiBIZSBvcmRlcmVkIGEgaGlnaC1xdWFsaXR5IG1hcCBmcm9tIHRoZSBJbnRlcm5hdGlvbmFsIENhcnRvZ3JhcGhpYyBQdWJsaXNoaW5nIENvbXBhbnkgKElDUEMpLiBTaW5jZSB0aGUgbWFwIGhhcyBhIGxhcmdlIHNjYWxlLCBpdCBkb2VzIG5vdCBcdWZiMDF0IG9udG8gYSBzaW5nbGUgcGFnZSBhbmQgaXQgaGFzIHRvIGJlIHNwbGl0IGludG8gc2V2ZXJhbCByZWN0YW5ndWxhciB0aWxlcy48XC9wPlxyXG5cclxuPHA+RXZlbiB3aXRoIGEgXHVmYjAxeGVkIHRpbGUgc2l6ZSAoZGV0ZXJtaW5lZCBieSBhIHBhZ2Ugc2l6ZSkgYW5kIG1hcCBzY2FsZSwgdGhlIG51bWJlciBvZiB0aWxlcyBtYXkgc3RpbGwgZGlcdWZiMDBlciBieSBhZGp1c3RpbmcgdGhlIHBvc2l0aW9uIG9mIHRoZSB0aWxlIGdyaWQuIFlvdXIgdGFzayBpcyB0byBcdWZiMDFuZCB0aGUgbWluaW1hbCBudW1iZXIgb2YgdGlsZXMgbmVjZXNzYXJ5IHRvIGNvdmVyIHRoZSB3aG9sZSByZWdpb24gb2YgRnJlZGR5JnJzcXVvO3MgZ2FyZGVuLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZtYXAucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjEwcHg7IHdpZHRoOjQ1N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlR3byBvZiBtYW55IHBvc3NpYmxlIHdheXMgb2YgdGlsaW5nIFRleGFzLXNoYXBlZCByZWdpb248XC9wPlxyXG5cclxuPHA+TGV0JnJzcXVvO3MgaGF2ZSBhIGxvb2sgYXQgYW4gZXhhbXBsZS4gVGhlIFx1ZmIwMWd1cmUgb24gdGhlIGxlZnQgc2hvd3MgMTQgbWFwIHRpbGVzIGNvdmVyaW5nIGEgcmVnaW9uLiBCeSBhZGp1c3RpbmcgdGhlIGdyaWQgcG9zaXRpb24gYSBsaXR0bGUgYml0LCB3ZSBtYXkgY292ZXIgdGhlIHNhbWUgcmVnaW9uIHdpdGggb25seSAxMCB0aWxlcywgd2l0aG91dCBjaGFuZ2luZyB0aGVpciBzaXplIG9yIG9yaWVudGF0aW9uLjxcL3A+XHJcblxyXG48cD5Ob3RlIHRoYXQgdGhlIHRpbGVzIG11c3QgYmUgcGFydCBvZiBhIHJlY3Rhbmd1bGFyIGdyaWQgYWxpZ25lZCB3aXRoIHRoZSB4LWF4aXMgYW5kIHktYXhpcy4gVGhhdCBpcywgdGhleSB0b3VjaCBlYWNoIG90aGVyIG9ubHkgd2l0aCB0aGVpciB3aG9sZSBzaWRlcyBhbmQgY2Fubm90IGJlIHJvdGF0ZWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLiBUaGUgXHVmYjAxcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgZm91ciBpbnRlZ2VyIG51bWJlcnM6IEE8c3ViPnI8XC9zdWI+LCBBPHN1Yj5jPFwvc3ViPiwgVDxzdWI+cjxcL3N1Yj4sIGFuZCBUPHN1Yj5jPFwvc3ViPi4gQTxzdWI+cjxcL3N1Yj4gYW5kIEE8c3ViPmM8XC9zdWI+IGdpdmUgdGhlIGlucHV0IGltYWdlIHJlc29sdXRpb24gaW4gcGl4ZWxzICgxICZsZTsgQTxzdWI+eDxcL3N1Yj4gJmxlOyAxMDAwKSwgd2hpbGUgVDxzdWI+cjxcL3N1Yj4gYW5kIFQ8c3ViPmM8XC9zdWI+IGlzIHRoZSBzaXplIG9mIG9uZSB0aWxlIGluIHBpeGVscyAoMSAmbGU7IFQ8c3ViPng8XC9zdWI+ICZsZTsgMTAwKS4gVGhlIG5leHQgQTxzdWI+cjxcL3N1Yj4gbGluZXMgZWFjaCBjb250YWluIEE8c3ViPmM8XC9zdWI+IGNoYXJhY3RlcnMsIGVhY2ggb2YgdGhlbSBiZWluZyBlaXRoZXIgJmxkcXVvO1gmcmRxdW87ICh0aGUgcGl4ZWwgY29ycmVzcG9uZHMgdG8gYSBwYXJ0IG9mIHRoZSBnYXJkZW4gdG8gYmUgY292ZXJlZCBieSBhIHRpbGUpIG9yICZsZHF1bzsuJnJkcXVvOyAodGhlIGNvcnJlc3BvbmRpbmcgcGl4ZWwgaXMgb3V0c2lkZSB0aGUgZ2FyZGVuIGFuZCBkb2VzIG5vdCBuZWVkIHRvIGJlIGNvdmVyZWQpLiBUaGUgcmVnaW9uIHBpeGVscyBmb3JtIG9uZSBjb25uZWN0ZWQgcmVnaW9uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgb25lIGludGVnZXIgbnVtYmVyICZtZGFzaDsgdGhlIG1pbmltYWwgbnVtYmVyIG9mIHRpbGVzIG5lY2Vzc2FyeSB0byBjb3ZlciBhbGwgcGl4ZWxzIHJlcHJlc2VudGVkIGJ5ICZsZHF1bztYJnJkcXVvOy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=