Long Distance Racing

Bessie is training for her next race by running on a path that includes hills, so she will be ready for any terrain. She has chosen a single straight path and wants to run as far from the farm as she can, but she must be back at the farm within $M$ seconds ($1 \le M \le 10{,}000{,}000$).

The chosen path is $T$ units long ($1 \le T \le 100{,}000$) and is split into equal-length segments, each of which is uphill, flat, or downhill. Segment $i$ is given by a single character $S_i$, where u means uphill, f means flat, and d means downhill.

Bessie takes $U$ seconds to run one unit of uphill ($1 \le U \le 100$), $F$ seconds for one unit of flat ($1 \le F \le 100$), and $D$ seconds for one unit of downhill ($1 \le D \le 100$). On the way home, every uphill segment becomes downhill and every downhill segment becomes uphill (flat stays flat).

If Bessie runs to the end of segment $k$ and returns, she passes segments $1$ through $k$ in order on the way out and the same segments in reverse on the way back. Find the greatest distance (number of units) she can reach from the farm and still return within $M$ seconds.

• Line 1: Five space-separated integers $M$, $T$, $U$, $F$, and $D$.
• Lines 2 through $T+1$: line $i+1$ contains a single character $S_i$ describing segment $i$.

• A single integer: the greatest distance (number of units) Bessie can reach from the farm and still return within $M$ seconds.