Given a cost matrix (may contain negative values) and a man has some non-negative initial strength, he starts from zero(start) position and complete his journey at (n-1)th position with some non-negative power. matrix[i][j]>0 denotes he lost his strength from moving city i to j and matrix[i][j]<0 denotes he gain his strength by matrix[i][j]. he has to cover all the cities from 1 to n-2 and during his journey path his power may become negative but at the (n-1)th pos(destination) his power must be non-negative. we have to find whether he able to complete his journey or not.

test case-

         initial strength=1
         cost matrix = [0 2 2 -1]
                       [4 0 2 -1]
                       [4 2 0 -1]
                       [4 2 2 0]
         ans=YES 
         path is- 
         (0 -> 3 -> 1 -> 3 -> 2 -> 3)
         strength during its journey
         (1 -> 2 -> 0 -> 1 -> -1 ->0)

i have no idea how to solve this question please help.