Problem D
Rock Climbing

Peter is attempting to deep-water solo a rock climbing cliff over the ocean. Deep-water soloing (DWS) is a form of solo rock climbing that relies solely upon the presence of water at the base of the climb to protect against injury from falling.
Rock climbing is very exhausting and takes lots of energy.
Since Peter is not very flexible, he can only move
If Peter’s energy is negative, he will fall into the water.
Peter doesn’t want to get wet, so he asks you to compute the minimum amount of energy he needs to complete the climb, assuming he takes an optimal route.
Input
The first line of the input will contain two integers,
Next, there will be
Output
Output a single integer, the minimum initial amount of energy necessary to complete the climb without falling.
Sample Input 1 | Sample Output 1 |
---|---|
5 5 E E E E E 1 2 3 4 5 5 4 3 2 1 -2 -2 -2 -2 -2 8 8 8 8 8 9 9 9 9 9 S S S S S |
17 |
Sample Input 2 | Sample Output 2 |
---|---|
13 5 E E E E E 1 1 1 1 1 1 1 1 2 1 9 9 9 9 1 1 1 1 9 1 1 9 1 1 1 1 9 9 9 9 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 9 6 7 8 9 -5 9 -7 9 -5 6 0 7 0 5 S S S S S |
32 |