Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3835
Nuclear Reactor

Time Limit: 6 Seconds      Memory Limit: 65536 KB

After choosing the city for building the nuclear power plant, Darkgy wants you estimate the security of the nuclear reactor of the nuclear power plant.

The nuclear reactor has N×M grids. Each grid can be empty, uranium cell, integrated heat dispenser, cooling cell or upgrade cell.

Uranium cell: Uranium cell can works for T ticks. At the beginning of each tick, an uranium cell will generate (1 + k) times uranium impulses (k is the amount of uranium cells whose Manhattan distance to this unranium cell is 1). An uranium impulses will generate 24 units heat, which means, if there are k uranium cells adjecent to an uranium cell, it will generate (1+k) ×24 units heat per tick.

The heat will be transmited to integrated heat dispensers and cooling cells immediately (the weight is the reciprocal of the length of the shortest path from the uranium cell to integrated heat dispensers or cooling cells which didn't go through any other integrated heat dispensers or cooling cells), if the heat cannot transmit to any integrated heat dispensers or cooling cells, the nuclear reactor will exploded and destroy the city.

Integrated heat dispenser: integrated heat dispenser will make itself and adjacent integrated heat dispensers and cooling cells (which Manhattan distance to it is 1) has equivalent heat at once after the transmition of the heat from uranium cell finished. At any time, if an integrated heat dispenser has more than Q units heat, it (include its heat) will disappear at once.

Cooling cell: Every tick after integrated heat dispenser worked, cooling cell will dissipate at most (8 + 2k) units heat of itself (k is the amount of upgrade cells which Manhattan distance to it is 1). At any time, if a cooling cell has more than Q units heat, it (include its heat) will disappear at once.

Upgrade Cell: can upgrade the ability of the adjacent cooling cell.

In a word, the whole process of each tick can be divided into three steps: Firstly, uranium cell generate heat and transmit to Integrated heat dispenser and cooling cell. Secondly, Integrated head dispenser swap the heat. At last, cooling cell dissipate the heat.

Input

Input will consist of multiple test cases.

The first line of each test case contains four integers N, M, T, Q(0 ≤ N,M ≤ 20,0 ≤ T ≤ 105,0 ≤ Q ≤ 109).

The next N lines, each line contains M characters, which means the designs of nuclear reactor ('.' indicates empty, 'U' indicates uranium cell, 'I' indicates integrated heat dispensers, 'C' indicates cooling cell and 'X' indicates upgrade cell).

Output

For each case output one line contains one integer, the ticks of the nuclear reactor can do uranium pulses.

Sample Input

3 5  100000 10000
UU.CC
U.CIC
....X

Sample Output

346

Hint:

For the sample input, at tick 0: the Uranium cell at (0,0) generates 3 times uranium impulses, and make 72 units heat. The Uranium cell at (1,0) and (0,1) generates 2 times uranium impulses each, and make 48 units heat each. The Uranium cell at (0,0) transmit the 72 units to Cooling Cell (0,3),(1,2),(1,4) and integrated heat dispensers (1,3) with the weight 1/3,1/3,1/7,1/6. Then integrated heat dispensers (1,3) will make (1,3) and Cooling Cell (0,3),(1,2),(1,4) have the same heat. At the end of tick, Cooling Cell decrease the heat, Cooling Cell (0,3),(0,4),(1,2) can decrease at most 8 units heat each and Cooling Cell (1,4) can decrease at most 10units heat with the help of Upgrade Cell at (2,4).

Nuclear2 Sample

Author: LU, Yi
Source: ZOJ Monthly, November 2014
Submit    Status