33099번 - Narrow Passageway 다국어

문제

You are a strategist of The ICPC Kingdom. You received an intel that there will be monster attacks on a narrow passageway near the kingdom. The narrow passageway can be represented as a grid with 2ドル$ rows (numbered from 1ドル$ to 2ドル$) and $N$ columns (numbered from 1ドル$ to $N$). Denote $(r, c)$ as the cell in row $r$ and column $c$. Each cell can be empty, which is represented by the character .; or blocked, which is represented by the character #.

There are three types of heroes that can be deployed to defend the passageway: swordsman, wizard, and defender. Currently, the kingdom has $C_s$ swordsmen, $C_w$ wizards, and $C_d$ defenders. Each swordsman, wizard, and defender has a power of $P_s,ドル $P_w,ドル and $P_d,ドル respectively.

You can only deploy at most one hero on an empty cell, while no heroes can be deployed on a blocked cell. Furthermore, there should not be two cells sharing a side and both contain a swordsman; and there should not be two cells sharing a corner and both contain a wizard. Formally,

• if $(r, c)$ contains a swordsman, then $(r - 1, c),ドル $(r, c + 1),ドル $(r + 1, c),ドル and $(r, c - 1)$ should not contain a swordsman; and
• if $(r, c)$ contains a wizard, then $(r - 1, c - 1),ドル $(r - 1, c + 1),ドル $(r + 1, c + 1),ドル and $(r + 1, c - 1)$ should not contain a wizard.

Determine the maximum total power that can be deployed to defend the narrow passageway from the monster attacks.

입력

The first line consists of an integer $N$ (1ドル ≤ N ≤ 1000$).

The second line consists of three integers $C_s$ $C_w$ $C_d$ (0ドル ≤ C_s, C_w, C_d ≤ 1000$).

The third line consists of three integers $P_s$ $P_w$ $P_d$ (1ドル ≤ P_s, P_w, P_d ≤ 100,円 000$).

Each of the next 2ドル$ lines consists of a string with $N$ characters. They represent the narrow passageway as a grid. The $c$^th character of the $r$^th string represents $(r, c)$. Each character can only be either . or #.

출력

Output a single integer representing the maximum total power that can be deployed to defend the narrow passageway.

제한

힌트