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
2017-08-11 16:30:34
guys anyone know the 8th test case,i am getting WA in that

Last edit: 2017-08-11 16:30:51
2017-07-31 16:31:08
4 WA's a year ago, returned today to find the bug ....finally -_-
2017-06-10 21:54:38
just write extra 4-5 lines while taking input....then get ans in O(1) time
2017-05-30 12:28:43
Easy..!!
2017-05-27 16:51:12
AC in one go ! Rock Climbing DP ! :D
2017-05-23 10:53:12
two methods
recursion+memo,bfs ;)

Last edit: 2017-05-23 12:05:46
2017-05-19 03:32:08 Vk rocks
Beginner DP problem :)
2017-05-17 17:21:21
Why use DP, when you can go greedy, djikstra
2017-04-18 18:34:35
sh1tty input, waste of time

Last edit: 2017-04-18 18:35:01
2016-10-13 12:47:33
DP..:)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.