TRIKA - Training for final
Abotrika is a famous player who plays in a good team. His team is going to play the final match next week and he have to train hard because all his fans are expecting that Abotrika will score more than one goal, so his team-mates suggested helping him in training given that Abotrika will play alone against all his friends in the training.
Input
Given two integers N,M (length and width of the training court) 2 <= N, M <= 20 and X,Y the starting point of Abotrika on the court where X is number of row and Y is number of column 1 <= X <= N, 1 <= Y <= M then P[i][j], where P is the power of each of his friends 0 < P[i][j] <100, and P[X][Y] is the power of Abotrika.
Output
The output must be one line either "N" or "Y" then the maximum power "Abotrika can get when he pass from his friends to reach the (the goal who is at the cell P[N][M] in the court ).
NOTE: Abotrika's power decreases by the power of his team-mate whom Aboutrika succeeded to get through on his way to score a goal. "Y" means that he had scored a goal with power at least 0 and "N" if he couldn't reach the goal with zero power at least. Also, Abotrika can only move in two directions -- right and down -- to reach the goal.
Example
Input: 4 4 1 1 100 55 10 2 20 10 90 1 60 20 22 4 1 30 70 5 Output: Y 23
Explanation: The maximum power Abotrika can get after reaching goal : 100 - (55+10+2+1+4+5) = 23
Input: 2 2 1 1 1 55 20 10 Output: N
Explanation: The maximum power Abotrika can get after reaching goal : 1 - (20+10) = -29 so it will be N.
Added by: | Kawmia Institutes |
Date: | 2010-08-22 |
Time limit: | 0.107s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 BF |
Resource: | Own problem |