Taco Grid Health Path

In this problem, you are given a grid of size (n \times m) where each cell can be one of the following characters:

• .: an empty space
• #: a wall, which cannot be traversed
• T: a trap cell that deals extra damage
• H: a health cell that restores some health

You start at the top-left cell (position \((0,0)\)) with an initial health value. Each move to an adjacent cell (up, down, left, or right) costs you 1 unit of health. Additionally, if you step on a trap cell, your health is reduced by a further \(trap\_damage\) units; if you step on a health cell, your health is increased by \(health\_restored\) units. Walls cannot be passed. Your goal is to determine whether it is possible to reach the bottom-right cell (position \((n-1, m-1)\)) with a strictly positive health value at all times.

Formally, given integers (n) and (m), a grid (G) of (n) rows and (m) columns (each cell (G_{i,j}) being one of the characters {'.', '#', 'T', 'H'}), and three integers: initial health (H_0), trap damage (D), and health restored (R), determine if there exists a path from ((0,0)) to ((n-1, m-1)) such that at every step the health remains positive.

The problem involves concepts from grid traversal and state management, and you are encouraged to use efficient search algorithms (like breadth-first search) to solve it.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains two integers (n) and (m), representing the number of rows and columns of the grid.
   
2. The next (n) lines each contain a string of length (m) representing the grid row. The characters in the string are among '.', '#', 'T', and 'H'.
   
3. The last line contains three integers: health (the initial health), trap_damage (the additional damage incurred on a trap cell), and health_restored (the health gained when stepping on a health cell).

outputFormat

The output is written to stdout. Print a single line containing either "YES" if it is possible to reach the bottom-right cell with positive health, or "NO" otherwise.## sample

4 4
...#
.#..
.T.#
H...
10 2 3

YES