B'Andrew loves the sea. That 's why, at the height of the summer season, he decided to go to the beach, taking a sunbed with him to sunbathe. The beach is a rectangular field with n rows and m columns. Some cells of the beach are free, some have roads, stones, shops and other non-movable objects. Some of two adjacent along the side cells can have sunbeds located either horizontally or vertically. Andrew hopes to put his sunbed somewhere, but that 's a bad luck, there may no longer be free places for him! That 's why Andrew asked you to help him to find a free place for his sunbed. Andrew 's sunbed also should be places on two adjacent cells. If there are no two adjacent free cells, then in order to free some place for a sunbed, you will have to disturb other tourists. You can do the following actions: In any moment each sunbed occupies two adjacent free cells. You cannot move more than one sunbed at a time. Help Andrew to free a space for his sunbed, causing the minimum possible number of units of discomfort to other tourists, or detect that it is impossible. The first line contains two integers n and m ( 1 <= n, m <= 300 ,000 , 1 <= n cdot m <= 300 ,000 ) -- the number of rows and columns in rectangle. The second line contains two integers p and q ( 1 <= p, q <= 10^9 ) -- the number of units of discomfort caused by rotation and shift of a sunbed, respectively. Each of the following n lines contains m characters, describing cells of the rectangle. Each lines consists of characters "L", "R", "D", "U", "." and "#", denoting the type of the cell. Characters "L", "R", "D" and "U" denote a half of a sunbed placed in the cell -- left, right, bottom and top half, respectively. Character "." denotes a free cell and character "#" -- a cell, occupied by some non-movable object. Print one integer -- the minimum possible number of units of discomfort, caused to other tourists, to free a space for'...