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

hide comments
2016-07-22 09:02:37
Even 0 power at the end would suffice. Ignore all A's.
2016-06-20 14:32:18 surayans tiwari(http://bit.ly/1EPzcpv)
easy
2016-05-23 18:00:24
the "A"s in the sample input are just plain garbage. They are not part of the testcases. Solution by normal integer calculations gives AC
2016-01-03 21:47:41 उत्कर्ष
easy dp. my 100th! :)
2015-09-01 16:23:49 Shivang Badola
DP......

Last edit: 2015-09-01 16:28:21
2015-07-22 10:28:52 :.Mohib.:
Ignore all 'A' while reading input and output....just read as an int...
2015-07-15 22:45:03
This Problem should be rewritten. First things are the annoying A^ scattered all over the text and input(!). And another problem is that the input description is written very poorly. What's the difference between length and width? That's hard to guess from the description. If only the sample input wasn't a square always( 4 x 4, 2 x 2) it would be easy to determine which one is the length or the width. But no. Sample input is written that you have to literally guess what the author meant by writing length or width. Besides, it's a nice problem though quite easy.
2015-07-04 10:29:48 Piyush Kumar
Are there A^ in the test cases?
2015-06-15 01:02:30 prodijig
just ignore all these A^ that are shown ! after this you might try
http://www.spoj.com/problems/AMR11A/
2013-10-24 23:47:50 Unknown
nice one!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.