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.